Submission #13375

#TimeUsernameProblemLanguageResultExecution timeMemory
13375dohyun0324Game (IOI13_game)C++98
63 / 100
3330 ms256000 KiB
#include<stdio.h> #include "game.h" typedef long long ll; int n,m,x1,y1,x2,y2; ll k; ll gcd2(ll X, ll Y) { if(X==0) return Y; if(Y==0) return X; ll tmp; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } struct data { int rx,ry; data *l,*r; data(int s,int e):rx(s),ry(e){ l=r=NULL; } void update3() { if(rx==ry){start2.update2(1,m); return;} int mid=(rx+ry)/2; if(x1<=mid) { if(l==NULL) l=new data(rx,mid); l->rx=rx; l->ry=mid; l->update3(); } else { if(r==NULL) r=new data(mid+1,ry); r->rx=mid+1; r->ry=ry; r->update3(); } x2=y1; y2=y1; if(r==NULL) k=l->start2.query2(1,m); else if(l==NULL) k=r->start2.query2(1,m); else k=gcd2(l->start2.query2(1,m),r->start2.query2(1,m)); start2.update2(1,m); } ll query() { int mid=(rx+ry)/2; if(x1<=rx && ry<=y1) return start2.query2(1,m); if(x1>ry || y1<rx) return 0; if(l==NULL && r==NULL) return 0; else if(l==NULL) { r->rx=mid+1; r->ry=ry; return r->query(); } else if(r==NULL) { l->rx=rx; l->ry=mid; return l->query(); } l->rx=rx; l->ry=mid; r->rx=mid+1; r->ry=ry; return gcd2(l->query(),r->query()); } struct data2 { ll val; data2 *l,*r; data2(){} data2(ll v):val(v){l=r=NULL;} void update2(int cx,int cy) { if(cx==cy){val=k; return;} int mid=(cx+cy)/2; if(y1<=mid){ if(l==NULL) l=new data2(0); l->update2(cx,mid); } else{ if(r==NULL) r=new data2(0); r->update2(mid+1,cy); } if(r==NULL) val=l->val; else if(l==NULL) val=r->val; else val=gcd2(l->val,r->val); } ll query2(int cx,int cy) { int mid=(cx+cy)/2; if(cx>y2 || cy<x2) return 0; if((x2<=cx && cy<=y2) || (l==NULL && r==NULL)) return val; if(l==NULL) return r->query2(mid+1,cy); else if(r==NULL) return l->query2(cx,mid); return gcd2(l->query2(cx,mid),r->query2(mid+1,cy)); } }; data2 start2=data2(0); }; data start=data(1,n); void init(int R, int C){ n=R+1, m=C+1; start=data(1,n); } void update(int P, int Q, ll K){ x1=P+1; y1=Q+1; k=K; start.update3(); } ll calculate(int P, int Q, int U, int V){ x1=P+1; y1=U+1; x2=Q+1; y2=V+1; return start.query(); }
#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...