Submission #1101354

#TimeUsernameProblemLanguageResultExecution timeMemory
1101354alexander707070Game (IOI13_game)C++14
63 / 100
1313 ms256000 KiB
#include<bits/stdc++.h> #include "game.h" #define MAXN 500007 using namespace std; const int maxs=1e9; 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; } unordered_map<int,int> mp; struct ST{ struct node{ int l,r; long long val; }; vector<node> tree; int num; void init(){ tree.push_back({0,0,0}); tree.push_back({0,0,0}); num=1; } void addnode(){ num++; tree.push_back({0,0,0}); } void check(int v){ if(tree[v].l==0){ addnode(); tree[v].l=num; } if(tree[v].r==0){ addnode(); tree[v].r=num; } } void update(int v,int l,int r,int pos,long long val){ if(l==r){ tree[v].val=val; }else{ int tt=(l+r)/2; check(v); if(pos<=tt)update(tree[v].l,l,tt,pos,val); else update(tree[v].r,tt+1,r,pos,val); tree[v].val=gcd2(tree[tree[v].l].val,tree[tree[v].r].val); } } long long getgcd(int v,int l,int r,int ll,int rr){ if(v==0 or ll>rr)return 0; if(l==ll and r==rr){ return tree[v].val; }else{ int tt=(l+r)/2; return gcd2( getgcd(tree[v].l,l,tt,ll,min(tt,rr)) , getgcd(tree[v].r,tt+1,r,max(tt+1,ll),rr) ); } } void upd(int pos,long long val){ update(1,1,maxs,pos,val); } long long query(int l,int r){ return getgcd(1,1,maxs,l,r); } }; int last,currid; ST col[30007]; struct ST2D{ struct node{ int l,r; ST t; }; vector<node> tree; int num; void init(){ ST a,b; a.init(); b.init(); tree.push_back({0,0,a}); tree.push_back({0,0,b}); num=1; } void addnode(){ ST a; a.init(); tree.push_back({0,0,a}); num++; } void check(int v){ if(tree[v].l==0){ addnode(); tree[v].l=num; } if(tree[v].r==0){ addnode(); tree[v].r=num; } } void update(int v,int l,int r,int posx,int posy,long long val){ if(l==r){ tree[v].t.upd(posy,val); }else{ int tt=(l+r)/2; check(v); if(posx<=tt)update(tree[v].l,l,tt,posx,posy,val); else update(tree[v].r,tt+1,r,posx,posy,val); long long newval = col[currid].query(l,r); tree[v].t.upd(posy,newval); } } long long getgcd(int v,int l,int r,int lx,int rx,int ly,int ry){ if(v==0 or lx>rx)return 0; if(l==lx and r==rx){ return tree[v].t.query(ly,ry); }else{ int tt=(l+r)/2; return gcd2( getgcd(tree[v].l,l,tt,lx,min(tt,rx),ly,ry) , getgcd(tree[v].r,tt+1,r,max(tt+1,lx),rx,ly,ry) ); } } void upd(int x,int y,long long val){ update(1,1,maxs,x,y,val); } long long query(int a,int b,int c,int d){ return getgcd(1,1,maxs,a,c,b,d); } }seg; void init(int R, int C) { seg.init(); } void update(int P, int Q, long long K) { P++; Q++; if(mp[Q]==0){ last++; mp[Q]=last; col[last].init(); } currid=mp[Q]; col[currid].upd(P,K); seg.upd(P,Q,K); } long long calculate(int P, int Q, int U, int V) { P++; Q++; U++; V++; return seg.query(P,Q,U,V); } /*int main(){ init(10,10); update(0,0,20); update(0,2,15); update(1,1,12); cout<<calculate(0,0,0,2)<<"\n"; cout<<calculate(0,0,1,1)<<"\n"; update(0,1,6); update(1,1,14); cout<<calculate(0,0,0,2)<<"\n"; cout<<calculate(0,0,1,1)<<"\n"; return 0; }*/
#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...