Submission #49002

#TimeUsernameProblemLanguageResultExecution timeMemory
49002NamnamseoGame (IOI13_game)C++17
100 / 100
9488 ms256000 KiB
#include "game.h" #include <cstdio> typedef long long ll; #define DBG if(0) ll gcd2(ll a,ll b){ return b?gcd2(b,a%b):a; } /* 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 node { node *lp, *rp; ll val; int l,r; int sing_pos; node(int a,int b){ l=a; r=b; lp=rp=0; val=0; sing_pos = -1; } void insert_val(int pos,ll v){ if(l==r){ val=v; return; } int mid=(l+r)/2; //printf("insert_val %d,%lld; mid %d\n",pos,v,mid); if(pos<=mid){ if(!lp) lp=new node(l, mid); lp->update(pos, v); } else { if(!rp) rp=new node(mid+1, r); rp->update(pos, v); } val = 0; if(lp) val=gcd2(val, lp->val); if(rp) val=gcd2(val, rp->val); //printf("my %d~%d : %lld\n",l,r,val); } void update(int pos,ll uv){ DBG printf(">>> %lld: i am %d~%d. small-update %d / val %lld\n",ll(this)&0xffff, l,r,pos,uv); if(lp==0 && rp==0){ if(sing_pos == -1 || sing_pos == pos){ DBG puts("Singular Update"); sing_pos = pos; val = uv; return; } else { DBG printf("Pushing pre-\n"); insert_val(sing_pos, val); DBG puts("And..."); insert_val(pos, uv); } } else insert_val(pos,uv); } ll range(int a,int b){ if(r<a || b<l) return 0; if(lp==0 && rp==0 && sing_pos!=-1 && a<=sing_pos && sing_pos<=b) return val; if(a<=l && r<=b){ return val; } ll ret=0; if(lp) ret=gcd2(ret, lp->range(a,b)); if(rp) ret=gcd2(ret, rp->range(a,b)); DBG printf(">>> range %d~%d, get %d~%d : ret %lld\n",l,r,a,b,ret); return ret; } }; int n,m; struct node2 { node *p; int l,r; node2 *lp, *rp; node2(int a,int b){ l=a; r=b; p=new node(0, m-1); lp=0; rp=0; } void update2(int x,int y,ll val){ if(x<l || r<x) return; DBG printf("\nI am %d~%d. updating %d,%d / val %lld\n", l,r,x,y,val); if(l==r){ DBG puts("Tada update"); p->update(y,val); return; } int mid=(l+r)/2; ll yv=0; if(x<=mid){ if(!lp) lp=new node2(l, mid); lp->update2(x,y,val); } else { if(!rp) rp=new node2(mid+1, r); rp->update2(x,y,val); } yv=gcd2(lp?(lp->p->range(y,y)):0, rp?(rp->p->range(y,y)):0); DBG printf("%d~%d of %d is %lld\n", l, r, y, yv); p->update(y, yv); } ll range(int a,int b,int x,int y){ if(a<=l && r<=b){ //printf("%d~%d full contain; asking %d~%d\n", l,r,x,y); return p->range(x,y); } if(r<a || b<l) return 0; ll ret=0; if(lp) ret=gcd2(ret, lp->range(a,b,x,y)); if(rp) ret=gcd2(ret, rp->range(a,b,x,y)); //printf("xrange %d~%d; ask %d~%d, %d~%d: %lld\n",l,r,a,b,x,y,ret); return ret; } } *root=0; void init(int R, int C) { n=R; m=C; root=new node2(0, n-1); } void update(int P, int Q, long long K) { //putchar(10); root->update2(P, Q, K); } long long calculate(int P, int Q, int U, int V) { return root->range(P, U, Q, V); }

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
#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...