제출 #218909

#제출 시각아이디문제언어결과실행 시간메모리
218909urd05게임 (IOI13_game)C++14
100 / 100
5747 ms231484 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; typedef pair<int,int> P; typedef pair<int,P> iP; typedef pair<P,P> PP; int r,c; const int siz=1<<30; long long gcd(long long a,long long b) { if (b==0) { return a; } return gcd(b,a%b); } long long value[19500000]; int lr[19500000]; int s=0; int sz=0; const long long INF=2e18; int root[700000]; int arr[700000]; void init0(int node) { root[node]=sz; value[sz]=2*INF; lr[sz]=-1; sz++; } void update0(int y,long long v,int node,int nodel=0,int noder=c-1) { if (nodel==noder) { value[node]=(value[node]/INF)*INF+v; return; } int mid=(nodel+noder)/2; if (y<=mid) { if (value[node]/INF==0) { update0(y,v,node+1,nodel,mid); } if (value[node]/INF==1) { if (lr[node]==-1) { lr[node]=sz; value[sz]=2*INF; lr[sz]=-1; sz++; } update0(y,v,lr[node],nodel,mid); } if (value[node]/INF==2) { value[node]-=2*INF; value[sz]=2*INF; lr[sz]=-1; sz++; update0(y,v,node+1,nodel,mid); } } else { if (value[node]/INF==0) { if (lr[node]==-1) { lr[node]=sz; value[sz]=2*INF; lr[sz]=-1; sz++; } update0(y,v,lr[node],mid+1,noder); } if (value[node]/INF==1) { update0(y,v,node+1,mid+1,noder); } if (value[node]/INF==2) { value[node]-=INF; value[sz]=2*INF; lr[sz]=-1; sz++; update0(y,v,node+1,mid+1,noder); } } long long x=0; if (value[node]/INF==0) { x=gcd(x,value[node+1]%INF); } else if (lr[node]!=-1) { x=gcd(x,value[lr[node]]%INF); } if (value[node]/INF==1) { x=gcd(x,value[node+1]%INF); } else if (lr[node]!=-1) { x=gcd(x,value[lr[node]]%INF); } value[node]=(value[node]/INF)*INF+x; } long long sum0(int l,int r,int node,int nodel=0,int noder=c-1) { if (r<nodel||l>noder) { return 0; } if (l<=nodel&&noder<=r) { return value[node]%INF; } long long ret=0; int mid=(nodel+noder)/2; if (value[node]/INF==0) { ret=gcd(sum0(l,r,node+1,nodel,mid),ret); } else if (lr[node]!=-1) { ret=gcd(sum0(l,r,lr[node],nodel,mid),ret); } if (value[node]/INF==1) { ret=gcd(sum0(l,r,node+1,mid+1,noder),ret); } else if (lr[node]!=-1) { ret=gcd(sum0(l,r,lr[node],mid+1,noder),ret); } return ret; } const int I=1e6; void init2() { arr[s++]=3*I-1; } void update2(int x,int y,long long v,int node=0,int nodel=0,int noder=r-1) { if (nodel==noder) { if (root[node]==-1) { init0(node); } update0(y,v,root[node]); return; } int mid=(nodel+noder)/2; if (x<=mid) { if (arr[node]/I==0) { update2(x,y,v,node+1,nodel,mid); } if (arr[node]/I==1) { if (arr[node]%I==I-1) { arr[node]=(arr[node]/I)*I+s; arr[s++]=3*I-1; } update2(x,y,v,arr[node]%I,nodel,mid); } if (arr[node]/I==2) { arr[node]-=2*I; arr[s++]=3*I-1; update2(x,y,v,node+1,nodel,mid); } } else { if (arr[node]/I==0) { if (arr[node]%I==I-1) { arr[node]=(arr[node]/I)*I+s; arr[s++]=3*I-1; } update2(x,y,v,arr[node]%I,mid+1,noder); } if (arr[node]/I==1) { update2(x,y,v,node+1,mid+1,noder); } if (arr[node]/I==2) { arr[node]-=I; arr[s++]=3*I-1; update2(x,y,v,node+1,mid+1,noder); } } long long val=0; if (arr[node]/I==0) { val=gcd(sum0(y,y,root[node+1]),val); } else if (arr[node]%I!=I-1) { val=gcd(sum0(y,y,root[arr[node]%I]),val); } if (arr[node]/I==1) { val=gcd(sum0(y,y,root[node+1]),val); } else if (arr[node]%I!=I-1) { val=gcd(sum0(y,y,root[arr[node]%I]),val); } if (root[node]==-1) { init0(node); } update0(y,val,root[node]); } long long sum2(int xl,int xr,int yl,int yr,int node=0,int nodel=0,int noder=r-1) { if (xr<nodel||xl>noder) { return 0; } if (xl<=nodel&&noder<=xr) { return sum0(yl,yr,root[node]); } int mid=(nodel+noder)/2; long long ret=0; if (arr[node]/I==0) { ret=gcd(ret,sum2(xl,xr,yl,yr,node+1,nodel,mid)); } else if (arr[node]%I!=I-1) { ret=gcd(ret,sum2(xl,xr,yl,yr,arr[node]%I,nodel,mid)); } if (arr[node]/I==1) { ret=gcd(ret,sum2(xl,xr,yl,yr,node+1,mid+1,noder)); } else if (arr[node]%I!=I-1) { ret=gcd(ret,sum2(xl,xr,yl,yr,arr[node]%I,mid+1,noder)); } return ret; } void init(int x,int y) { r=x; c=y; init2(); memset(root,-1,sizeof(root)); } void update(int p,int q,long long k) { update2(p,q,k); } long long calculate(int p,int q,int u,int v) { return sum2(p,u,q,v); }

컴파일 시 표준 에러 (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...