Submission #1136888

#TimeUsernameProblemLanguageResultExecution timeMemory
1136888mychecksedadGame (IOI13_game)C++20
100 / 100
2281 ms62712 KiB
#include "game.h" #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 10000, M = 1e5+10, K = 52, MX = 30; ll gcd(ll x, ll y) { return !y ? x : gcd(y, x % y); } int rnd() { return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15)); } struct Node{ Node *L, *R; ll key; int Y; ll val, ans=0ll; int l, r; Node() : Y(rand()), key(0), val(0ll), L(nullptr), R(nullptr) {} Node(int key): key(key), Y(rnd()), val(0ll), L(nullptr), R(nullptr), l(key), r(key) {} Node(int key, ll val): key(key), Y(rnd()), val(val), ans(val), L(nullptr), R(nullptr), l(key), r(key) {} void update(){ ans = val; l = r = key; if(L) ans = gcd(ans, L->ans), l = min(l, L->l), r = max(r, L->r); if(R) ans = gcd(ans, R->ans), l = min(l, R->l), r = max(r, R->r); } }; typedef Node* Nodep; struct Treap{ Nodep root; Treap(){ root = nullptr; srand(rnd()); } pair<Nodep, Nodep> split(Nodep v, int pos){ if(!v) return {v, v}; if(v->key >= pos){ auto p = split(v->L, pos); v->L = p.ss; v->update(); return {p.ff, v}; }else{ auto p = split(v->R, pos); v->R = p.ff; v->update(); return {v, p.ss}; } } Nodep merge(Nodep l, Nodep r){ if(!l || !r){ return !l ? r : l; } if(l->Y > r->Y){ auto p = merge(l->R, r); l->R = p; l->update(); return l; }else{ auto p = merge(l, r->L); r->L = p; r->update(); return r; } } bool find(int pos){ Nodep t = root; while(t){ if(t->key == pos) return true; if(t->key > pos) t = t->L; else t = t->R; } return false; } void insert(int pos, ll val){ if(find(pos)) update(root, pos, val); else{ auto p = split(root, pos); root = merge(merge(p.ff, new Node(pos, val)), p.ss); } } void update(Nodep t, int pos, ll val){ if(t->key == pos){ t->val = val; t->update(); }else{ if(t->key > pos) update(t->L, pos, val); else update(t->R, pos, val); t->update(); } } ll query(Nodep v, int l, int r){ if(!v || l > v->r || v->l > r) return 0ll; if(l <= v->l && v->r <= r) return v->ans; ll ans = (v->key >= l && v->key <= r ? v->val : 0ll); return gcd(ans, gcd(query(v->L, l, r), query(v->R, l, r))); } ll query(int l, int r){ if(!root) return 0ll; return query(root, l, r); } }; struct SegTree{ Treap treap; SegTree *l, *r; int lo, hi; SegTree(){l=r=nullptr;} SegTree(int st, int hii){l=r=nullptr; lo=st, hi=hii;} void new_left(){ if(!l){ l = new SegTree(lo, (lo+hi)>>1); } } void new_right(){ if(!r){ r = new SegTree((lo+hi>>1)+1, hi); } } void calc(int pos){ ll val = 0; if(l) val = gcd(val, l->treap.query(pos, pos)); if(r) val = gcd(val, r->treap.query(pos, pos)); treap.insert(pos, val); } void upd(int x, int y, ll val){ if(lo > x || x > hi) return; if(lo == hi){ treap.insert(y, val); return; } if(x <= (lo+hi)/2){ new_left(); l->upd(x, y, val); }else{ new_right(); r->upd(x, y, val); } calc(y); } ll query(int t, int b, int x, int y){ if(lo > b || t > hi) return 0ll; if(t <= lo && hi <= b){ return treap.query(x, y); } ll ans = 0; if(l) ans = gcd(ans, l->query(t, b, x, y)); if(r) ans = gcd(ans, r->query(t, b, x, y)); return ans; } }; int n, m; SegTree seg; void init(int R, int C) { srand(12341234); n = R; m = C; seg = SegTree(1, n); } void update(int P, int Q, long long K) { ++P, ++Q; seg.upd(P, Q, K); } long long calculate(int P, int Q, int U, int V) { ++P, ++Q, ++U, ++V; return seg.query(P, U, Q, V); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...