Submit Info #66459

Problem Lang User Status Time Memory
Associative Array cpp Nachia AC 718 ms 31.93 MiB

ケース詳細
Name Status Time Memory
2_powers_00 AC 531 ms 31.84 MiB
example_00 AC 1 ms 0.45 MiB
many_0set_00 AC 638 ms 20.28 MiB
many_0set_sparse_00 AC 103 ms 2.32 MiB
max_random_00 AC 658 ms 22.13 MiB
max_random_01 AC 630 ms 23.13 MiB
max_random_02 AC 718 ms 24.44 MiB
random_00 AC 221 ms 10.80 MiB
random_01 AC 293 ms 12.55 MiB
random_02 AC 410 ms 16.75 MiB
sparse_keys_00 AC 113 ms 3.94 MiB
sparse_keys_01 AC 131 ms 4.50 MiB
unordered_map_killer_00 AC 495 ms 31.89 MiB
unordered_map_killer_01 AC 496 ms 31.82 MiB
unordered_map_killer_02 AC 495 ms 31.93 MiB

#include <iostream> #include <vector> #include <algorithm> #include <string> #include <cassert> #include <memory> using namespace std; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) struct RedBlackTree{ using KeyType = i64; using ValType = i64; struct Node{ Node *l = 0, *r = 0, *p = 0; int is_black = 0; KeyType key = 0; ValType val = 0; }; static Node *NIL; Node *R = nullptr; RedBlackTree(){ if (!NIL){ NIL = new Node(); NIL->l = NIL->r = NIL->p = NIL; NIL->is_black = 1; } R = NIL; } ~RedBlackTree(){ if(R == NIL) return; std::vector<Node*> to_delete; to_delete.push_back(R); while (to_delete.size()){ Node* c = to_delete.back(); to_delete.pop_back(); if (c->l != NIL) to_delete.push_back(c->l); if (c->r != NIL) to_delete.push_back(c->r); delete(c); } } Node*& parentchild(Node* p){ if (p->p == NIL) return R; if (p->p->l == p) return p->p->l; else return p->p->r; } // 左回転 void rotL(Node* c){ Node* p = c->p; parentchild(p) = c; c->p = p->p; p->p = c; if (c->l != NIL) c->l->p = p; // 子が NIL かもしれない p->r = c->l; c->l = p; } // 右回転 void rotR(Node* c){ Node* p = c->p; parentchild(p) = c; c->p = p->p; p->p = c; if (c->r != NIL) c->r->p = p; // 子が NIL かもしれない p->l = c->r; c->r = p; } void fix_colors(Node* c){ while (true){ Node* p = c->p; if (p == NIL){ c->is_black = 1; return; } if (c->is_black != 0 || p->is_black != 0) return; Node* pp = p->p; if (pp == NIL){ p->is_black = 1; return; } if (pp->l->is_black == 0 && pp->r->is_black == 0){ pp->l->is_black = pp->r->is_black = 1; pp->is_black = 0; c = pp; continue; } if (pp->l == p){ if (p->l == c){ rotR(p); } else{ if(c->r != NIL) c->r->p = pp; if(c->l != NIL) c->l->p = p; parentchild(pp) = c; p->r = c->l; p->p = c; pp->l = c->r; c->r = pp; c->l = p; c->p = pp->p; pp->p = c; p = c; } p->is_black = 1; p->r->is_black = 0; } else{ if (p->r == c){ rotL(p); } else{ if(c->l != NIL) c->l->p = pp; if(c->r != NIL) c->r->p = p; parentchild(pp) = c; p->l = c->r; p->p = c; pp->r = c->l; c->l = pp; c->r = p; c->p = pp->p; pp->p = c; p = c; } p->is_black = 1; p->l->is_black = 0; } } } Node* lower_bound(KeyType key){ Node* p = R; Node* res = NIL; while (p != NIL){ if (key <= p->key){ res = p; p = p->l; } else{ p = p->r; } } return res; } Node* upper_bound(KeyType key){ Node* p = R; Node* res = NIL; while (p != NIL){ if (key < p->key){ res = p; p = p->l; } else{ p = p->r; } } return res; } Node* insert(KeyType key){ Node* nx = new Node(*NIL); nx->is_black = 0; nx->key = key; if (R == NIL){ R = nx; } else{ Node* p = R; while (true){ if (p->r != NIL) if (!(key < p->key)){ p = p->r; continue; } if (p->l != NIL) if (key < p->key){ p = p->l; continue; } break; } nx->p = p; if (key < p->key){ p->l = nx; } else{ p->r = nx; } } fix_colors(nx); return nx; } Node* access(KeyType key){ auto res = lower_bound(key); if (res == NIL) return insert(key); if (res->key == key) return res; return insert(key); } ValType read_at(KeyType key){ auto res = lower_bound(key); if (res == NIL) return 0; if (res->key == key) return res->val; return 0; } void print_inorder(Node* p, int depth = 0){ if (p == NIL) return; print_inorder(p->l, depth + 1); rep(i, depth) cout << " "; cout << p->key << "(" << p->val << ")"; if (p->is_black) cout << " black"; else cout << " red"; cout << endl; print_inorder(p->r, depth + 1); } void print_inorder(){ print_inorder(R); } }; RedBlackTree::Node* RedBlackTree::NIL = nullptr; int main(){ RedBlackTree rbtree; int Q; cin >> Q; for (int i = 0; i < Q; i++){ int t; cin >> t; if (t == 0){ i64 k, v; cin >> k >> v; rbtree.access(k)->val = v; } if (t == 1){ i64 k; cin >> k; cout << rbtree.read_at(k) << "\n"; } } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;