Submission #1080837

#TimeUsernameProblemLanguageResultExecution timeMemory
1080837GrayGame (IOI13_game)C++17
63 / 100
2550 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{ map<ll, Node*> con; ll gcd; Node(){ 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 (!con.count(0)) con[0]=new Node(); con[0]->update(tl, tm, i, x, leaves); }else{ if (!con.count(1)) con[1]=new Node(); con[1]->update(tm+1, tr, i, x, leaves); } gcd=0; if(con.count(0)) gcd=__gcd(con[0]->gcd, gcd); if (con.count(1)) gcd=__gcd(con[1]->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 (con.count(0) and l<=min(r, tm)) ret=__gcd(ret, con[0]->query(tl, tm, l, min(r, tm))); if (con.count(1) and max(l, tm+1)<=r) ret=__gcd(ret, con[1]->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.count(ind)) return 0; return leaves[ind]->gcd; } }; struct SegTree2D{ struct mNode{ map<ll, mNode*> con; SegTree1D *val; ll csz; mNode(ll _csz){ csz=_csz; 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 (!con.count(0)) con[0]=new mNode(csz); con[0]->update(tl, tm, i, j, x); }else{ if (!con.count(1)) con[1]=new mNode(csz); con[1]->update(tm+1, tr, i, j, x); } val->update(j, __gcd((con.count(0)?con[0]->val->getval(j):0), (con.count(1)?con[1]->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 (con.count(0) and li<=min(ri, tm)) ret=__gcd(ret, con[0]->query(li, min(ri, tm), lj, rj, tl, tm)); if (con.count(1) and max(li, tm+1)<=ri) ret=__gcd(ret, con[1]->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...