Submission #587256

#TimeUsernameProblemLanguageResultExecution timeMemory
587256yutabiGame (IOI13_game)C++14
63 / 100
2677 ms256000 KiB
#include "game.h" #define gcd gcd2 #include <bits/stdc++.h> using namespace std; #define pb push_back typedef long long ll; typedef pair <int,int> ii; long long gcd2(long long X, long long Y) { long long tmp; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } struct nodex; struct nodey { nodey* L=0; nodey* R=0; nodey* par=0; nodex* parx=0; ll val=0; }; struct nodex { nodex* L=0; nodex* R=0; nodex* par=0; nodey* Y=0; ll val=0; }; int r; int c; nodex* segment_tree; void check() { vector <pair <nodex*,ii> > processx; processx.pb(make_pair(segment_tree,ii(0,r-1))); while(processx.size()) { nodex* currx=processx.back().first; int Lx=processx.back().second.first; int Rx=processx.back().second.second; processx.pop_back(); printf("%lld %d %d\n",currx->val,Lx,Rx); vector <pair <nodey*,ii> > processy; if(currx->Y!=0) { processy.pb(make_pair(currx->Y,ii(0,c-1))); } while(processy.size()) { nodey* curry=processy.back().first; int Ly=processy.back().second.first; int Ry=processy.back().second.second; processy.pop_back(); printf("%lld %d %d\n",curry->val,Ly,Ry); if(curry->L!=0) { processy.pb(make_pair(curry->L,ii(Ly,(Ly+Ry)/2))); } if(curry->R!=0) { processy.pb(make_pair(curry->R,ii((Ly+Ry)/2+1,Ry))); } } printf("\n"); if(currx->L!=0) { processx.pb(make_pair(currx->L,ii(Lx,(Lx+Rx)/2))); } if(currx->R!=0) { processx.pb(make_pair(currx->R,ii((Lx+Rx)/2+1,Rx))); } } printf("\n"); } void init(int R, int C) { r=R; c=C; segment_tree=new nodex; } void update(int P, int Q, long long K) { nodex* currx=segment_tree; int Lx=0; int Rx=r-1; while(1) { if(Lx==Rx) { if(currx->Y==0) { currx->Y=new nodey; currx->Y->parx=currx; } nodey* curry=currx->Y; int Ly=0; int Ry=c-1; while(1) { if(Ly==Ry) { curry->val=K; break; } int My=(Ly+Ry)/2; if(Q<=My) { if(curry->L==0) { curry->L=new nodey; curry->L->par=curry; } curry=curry->L; Ry=My; } else { if(curry->R==0) { curry->R=new nodey; curry->R->par=curry; } curry=curry->R; Ly=My+1; } } while(1) { if(curry->par==0) { break; } curry=curry->par; curry->val=0; if(curry->L!=0) { curry->val=curry->L->val; } if(curry->R!=0) { curry->val=gcd(curry->val,curry->R->val); } } break; } int Mx=(Lx+Rx)/2; if(P<=Mx) { if(currx->L==0) { currx->L=new nodex; currx->L->par=currx; } currx=currx->L; Rx=Mx; } else { if(currx->R==0) { currx->R=new nodex; currx->R->par=currx; } currx=currx->R; Lx=Mx+1; } } while(currx->par!=0) { currx=currx->par; nodex* lx=currx->L; nodex* rx=currx->R; nodey* curry; nodey* ly=0; nodey* ry=0; if(currx->Y==0) { currx->Y=new nodey; currx->Y->parx=currx; } curry=currx->Y; if(lx!=0) { ly=lx->Y; } if(rx!=0) { ry=rx->Y; } int Ly=0; int Ry=c-1; while(1) { ll ans=0; if(ly!=0) { ans=ly->val; } if(ry!=0) { ans=gcd(ans,ry->val); } if(curry!=0) { curry->val=ans; } if(Ly==Ry) { break; } int My=(Ly+Ry)/2; if(Q<=My) { if(curry->L==0) { curry->L=new nodey; curry->L->par=curry; } curry=curry->L; if(ly!=0) { ly=ly->L; } if(ry!=0) { ry=ry->L; } Ry=My; } else { if(curry->R==0) { curry->R=new nodey; curry->R->par=curry; } curry=curry->R; if(ly!=0) { ly=ly->R; } if(ry!=0) { ry=ry->R; } Ly=My+1; } } } //check(); } long long calculate(int P, int Q, int U, int V) { ll ans=0; vector <pair <nodex*,ii> > processx; vector <pair <nodey*,ii> > processy; processx.pb(make_pair(segment_tree,ii(0,r-1))); while(processx.size()) { nodex* currx=processx.back().first; int Lx=processx.back().second.first; int Rx=processx.back().second.second; processx.pop_back(); int Mx=(Lx+Rx)/2; if(P<=Lx && Rx<=U) { if(currx->Y!=0) { processy.pb(make_pair(currx->Y,ii(0,c-1))); } continue; } if(P<=Mx) { if(currx->L!=0) { processx.pb(make_pair(currx->L,ii(Lx,Mx))); } } if(Mx+1<=U) { if(currx->R!=0) { processx.pb(make_pair(currx->R,ii(Mx+1,Rx))); } } } while(processy.size()) { nodey* curry=processy.back().first; int Ly=processy.back().second.first; int Ry=processy.back().second.second; processy.pop_back(); int My=(Ly+Ry)/2; if(Q<=Ly && Ry<=V) { ans=gcd(ans,curry->val); continue; } if(Q<=My) { if(curry->L!=0) { processy.pb(make_pair(curry->L,ii(Ly,My))); } } if(My+1<=V) { if(curry->R!=0) { processy.pb(make_pair(curry->R,ii(My+1,Ry))); } } } return ans; }
#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...