Submission #986357

#TimeUsernameProblemLanguageResultExecution timeMemory
986357PyqeGame (IOI13_game)C++17
100 / 100
4825 ms239136 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; int n,m,nn=0; long long ga[12540069]; int pa[12540069][2]; long long gcd2(long long x,long long y) { for(;y;) { x%=y; swap(x,y); } return x; } void sgud(int ix,int l,int r,int x,long long w) { if(l>=x&&r<=x) { ga[ix]=w; } else { int ii,md=(l+r)/2,l2,r2; for(ii=0;ii<2;ii++) { l2=!ii?l:md+1; r2=!ii?md:r; if(!(l2>x||r2<x)) { if(!pa[ix][ii]) { nn++; pa[ix][ii]=nn; } sgud(pa[ix][ii],l2,r2,x,w); } } ga[ix]=gcd2(ga[pa[ix][0]],ga[pa[ix][1]]); } } long long sgqr(int ix,int l,int r,int lh,int rh) { if(!ix||l>rh||r<lh) { return 0; } else if(l>=lh&&r<=rh) { return ga[ix]; } else { long long md=(l+r)/2; return gcd2(sgqr(pa[ix][0],l,md,lh,rh),sgqr(pa[ix][1],md+1,r,lh,rh)); } } struct segtreetree { int l,r,sg; segtreetree *p[3]; void bd(int lh,int rh) { l=lh; r=rh; nn++; sg=nn; p[0]=0; } void blc() { if(!p[0]) { int ii,md=l+(r-l)/3,md2=r-(r-l+2)/3; for(ii=0;ii<3;ii++) { p[ii]=new segtreetree; } p[0]->bd(l,md); p[1]->bd(md+1,md2); p[2]->bd(md2+1,r); } } long long ud(int y,int x,long long w) { if(l>y||r<y) { return sgqr(sg,0,m-1,x,x); } else if(!(l>=y&&r<=y)) { int ii; long long k=0; blc(); for(ii=0;ii<3;ii++) { k=gcd2(k,p[ii]->ud(y,x,w)); } w=k; } sgud(sg,0,m-1,x,w); return w; } long long qr(int lh,int rh,int lh2,int rh2) { if(l>rh||r<lh) { return 0; } else if((l>=lh&&r<=rh)||!p[0]) { return sgqr(sg,0,m-1,lh2,rh2); } else { long long ii,z=0; for(ii=0;ii<3;ii++) { z=gcd2(z,p[ii]->qr(lh,rh,lh2,rh2)); } return z; } } } sgg; void init(int on,int om) { n=on; m=om; sgg.bd(0,n-1); } void update(int y,int x,long long w) { sgg.ud(y,x,w); } long long calculate(int y,int x,int y2,int x2) { return sgg.qr(y,y2,x,x2); }
#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...