Submission #1080823

#TimeUsernameProblemLanguageResultExecution timeMemory
1080823GrayGame (IOI13_game)C++17
63 / 100
875 ms256000 KiB
#include<bits/stdc++.h> #include "game.h" #define ll long long #define ff first #define ss second #define ln "\n" using namespace std; struct SegTree1D{ struct Node{ Node *left, *right; ll gcd; Node(){ left=right=nullptr; gcd=0; } void update(ll tl, ll tr, ll i, ll x, map<ll, Node*> &leaves){ if (tl==tr){ gcd=x; leaves[tl]=this; }else{ ll tm = (tl+tr)/2; if (i<=tm) { if (!left) left=new Node(); left->update(tl, tm, i, x, leaves); }else{ if (!right) right=new Node(); right->update(tm+1, tr, i, x, leaves); } gcd=0; if(left) gcd=__gcd(left->gcd, gcd); if (right) gcd=__gcd(right->gcd, gcd); } } ll query(ll tl, ll tr, ll l, ll r){ if (tl==l and tr==r){ return gcd; }else if (l>r) return 0; else{ ll tm = (tl+tr)/2; ll ret=0; if (left and l<=min(r, tm)) ret=__gcd(ret, left->query(tl, tm, l, min(r, tm))); if (right and max(l, tm+1)<=r) ret=__gcd(ret, right->query(tm+1, tr, max(l, tm+1), r)); return ret; } } }; map<ll, Node*> leaves; Node * root; ll rsz; SegTree1D(ll N){ rsz=N; root=new Node(); } void update(ll i, ll x){ root->update(0, rsz-1, i, x, leaves); } ll query(ll l, ll r){ return root->query(0, rsz-1, l, r); } ll getval(ll ind){ if (leaves[ind]==nullptr) return 0; return leaves[ind]->gcd; } }; struct SegTree2D{ struct mNode{ mNode *left, *right; SegTree1D *val; ll csz; mNode(ll _csz){ csz=_csz; left=right=nullptr; val = new SegTree1D(csz); } void update(ll tl, ll tr, ll i, ll j, ll x){ if (tl==tr){ val->update(j, x); }else{ ll tm = (tl+tr)/2; if (i<=tm){ if (!left) left=new mNode(csz); left->update(tl, tm, i, j, x); }else{ if (!right) right=new mNode(csz); right->update(tm+1, tr, i, j, x); } val->update(j, __gcd((left?left->val->getval(j):0), (right?right->val->getval(j):0))); } } ll query(ll li, ll ri, ll lj, ll rj, ll tl, ll tr){ if (tl==li and tr==ri){ return val->query(lj, rj); }else if (li>ri) return 0; else{ ll ret=0; ll tm = (tl+tr)/2; if (left and li<=min(ri, tm)) ret=__gcd(ret, left->query(li, min(ri, tm), lj, rj, tl, tm)); if (right and max(li, tm+1)<=ri) ret=__gcd(ret, right->query(max(li, tm+1), ri, lj, rj, tm+1, tr)); return ret; } } }; mNode * root; ll csz, rsz; void init(ll R, ll C){ rsz=R; csz=C; root = new mNode(csz); } void update(ll i, ll j, ll x){ root->update(0, rsz-1, i, j, x); } ll query(ll li, ll ri, ll lj, ll rj){ return root->query(li, ri, lj, rj, 0, rsz-1); } } DS; void init(int R, int C) { DS.init(R, C); } void update(int P, int Q, long long K) { DS.update(P, Q, K); } long long calculate(int P, int Q, int U, int V) { /* ... */ return DS.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...