Submission #686902

#TimeUsernameProblemLanguageResultExecution timeMemory
686902lam게임 (IOI13_game)C++14
0 / 100
1 ms308 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; int n,m; struct node { int l, r, itx; long long val; node (bool is_x) { if (is_x) { l=r=itx=0; val=0LL; } else { l=r=0; itx=-1; val=0LL; } } }; vector <node> t; 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; } void update2(int &y, int ly, int ry, int idy, long long val) { if (y==0) { y=t.size(); t.push_back(node(0)); } if (ly==ry) { t[y].val = val; return; } int mid=ly+(ry-ly)/2; if (idy<=mid) update2(t[y].l,ly,mid,idy,val); else update2(t[y].r,mid+1,ry,idy,val); t[y].val=gcd2(t[t[y].l].val,t[t[y].r].val); // cout<<ly<<' '<<ry<<": "<<t[y].val<<endl; } void upd(int &x, int lx, int rx, int idx, int idy, int val) { // cout<<x<<"->"; if (x==0) { x=t.size(); t.push_back(node(1)); } // cout<<lx<<' '<<rx<<" !!"<<endl; update2(t[x].itx,1,m,idy,val); if (lx==rx) return; int mid=lx+(rx-lx)/2; if (idx<=mid) upd(t[x].l,lx,mid,idx,idy,val); else upd(t[x].r,mid+1,rx,idx,idy,val); } int get(int y, int ly, int ry, int l, int r) { if (y==0) return 0; if (t[y].val==0) return 0; if (ly>r||ry<l) return 0; if (ly>=l&&ry<=r) return t[y].val; int mid=ly+(ry-ly)/2; return gcd2(get(t[y].l,ly,mid,l,r),get(t[y].r,mid+1,ry,l,r)); } int get2(int x, int lx, int rx, int l, int r, int ly, int ry) { if (x==0) return 0; if (lx>r||rx<l) return 0; if (lx>=l&&rx<=r) return get(t[x].itx, 1, m, ly, ry); int mid=lx+(rx-lx)/2; return gcd2(get2(t[x].l,lx,mid,l,r,ly,ry),get2(t[x].r,mid+1,rx,l,r,ly,ry)); } void init(int R, int C) { /* ... */ n=R; m=C; t.push_back(node(1)); t.push_back(node(1)); } void update(int P, int Q, long long K) { /* ... */ P++; Q++; int val = 1; upd(val,1,n,P,Q,K); } long long calculate(int P, int Q, int U, int V) { /* ... */ P++; Q++; U++; V++; int val = 1; val = 1; return get2(val,1,n,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...