Submit Info #66185

Problem Lang User Status Time Memory
Associative Array cpp Nachia AC 825 ms 70.15 MiB

ケース詳細
Name Status Time Memory
2_powers_00 AC 650 ms 70.09 MiB
example_00 AC 1 ms 0.45 MiB
many_0set_00 AC 825 ms 27.85 MiB
many_0set_sparse_00 AC 102 ms 2.25 MiB
max_random_00 AC 768 ms 29.57 MiB
max_random_01 AC 727 ms 32.70 MiB
max_random_02 AC 801 ms 36.68 MiB
random_00 AC 241 ms 18.73 MiB
random_01 AC 331 ms 21.59 MiB
random_02 AC 399 ms 31.04 MiB
sparse_keys_00 AC 111 ms 3.82 MiB
sparse_keys_01 AC 130 ms 4.49 MiB
unordered_map_killer_00 AC 617 ms 70.15 MiB
unordered_map_killer_01 AC 617 ms 70.09 MiB
unordered_map_killer_02 AC 626 ms 70.07 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 i = -1; // 配列の index // int black_height = 0; int is_black = 0; KeyType key = 0; // 検索のキー ValType val = 0; }; using pNode = unique_ptr<Node>; pNode pNIL; Node *NIL = nullptr; vector<pNode> A; Node *R = nullptr; RedBlackTree(){ if (!pNIL){ pNIL = make_unique<Node>(); NIL = pNIL.get(); NIL->l = NIL->r = NIL->p = NIL; NIL->is_black = 1; } R = NIL; } 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){ //cout << "fix type 0 at " << c->key << endl; 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->is_black == 0){ cout << "fix_colors error : pp is not black" << endl; exit(1); } if (pp->l->is_black == 0 && pp->r->is_black == 0){ // cout << "fix type 1 at " << c->key << endl; pp->l->is_black = pp->r->is_black = 1; pp->is_black = 0; c = pp; continue; } if (pp->l == p){ //cout << "fix type 2 at " << c->key << endl; if (p->l == c){ rotR(p); } else{ rotL(c); p = c; rotR(p); } p->is_black = 1; p->r->is_black = 0; } else{ //cout << "fix type 3 at " << c->key << endl; if (p->r == c){ rotL(p); } else{ rotR(c); p = c; rotL(p); } 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){ pNode pnx = std::make_unique<Node>(*NIL); Node* nx = pnx.get(); nx->is_black = 0; nx->key = key; nx->i = A.size(); if (A.empty()){ 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; } } A.push_back(std::move(pnx)); 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); } 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); } }; 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.access(k)->val << "\n"; } } /* while (true){ string in_str; cin >> in_str; if (in_str == "EXIT") break; if (in_str == "INSERT"){ int key; cin >> key; rbtree.insert(key); rbtree.print_inorder(); } if (in_str == "UPPER_BOUND"){ int key; cin >> key; auto node = rbtree.upper_bound(key); cout << node->key << endl; } if (in_str == "LOWER_BOUND"){ int key; cin >> key; auto node = rbtree.lower_bound(key); cout << node->key << endl; } if (in_str == "ACCESS"){ int key; cin >> key; int val; cin >> val; auto p = rbtree.access(key); p->val = val; rbtree.print_inorder(); } } */ return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;