제출 #308078

#제출 시각아이디문제언어결과실행 시간메모리
308078daniel920712게임 (IOI13_game)C++14
80 / 100
6204 ms256000 KiB
#include "game.h" #include <stdio.h> 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 A { int nxl,nxr,nxt; long long con; }Node[9000005]; long long N,M,now=1; void New(int l,int r,int here,int t) { Node[here].nxt=t; Node[here].nxl=-1; Node[here].nxr=-1; Node[here].con=0; } void init(int R, int C) { N=R; M=C; New(0,N-1,0,-1); } void Merge(int here,int l,int r,int what,int lll,int rrr) { int ll,rr; if(what==lll&&what==rrr) { Node[here].con=0; if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con); if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con); return; } if(what<=(lll+rrr)/2) { if(Node[here].nxl==-1) { Node[here].nxl=now++; New(lll,(lll+rrr)/2,Node[here].nxl,-2); } if(l!=-1) ll=Node[l].nxl; if(r!=-1) rr=Node[r].nxl; Merge(Node[here].nxl,ll,rr,what,lll,(lll+rrr)/2); Node[here].con=0; if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con); if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con); } else { if(Node[here].nxr==-1) { Node[here].nxr=now++; New((lll+rrr)/2+1,rrr,Node[here].nxr,-2); } if(l!=-1) ll=Node[l].nxr; if(r!=-1) rr=Node[r].nxr; Merge(Node[here].nxr,ll,rr,what,(lll+rrr)/2+1,rrr); Node[here].con=0; if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con); if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con); } //printf("%d %d %d\n",lll,rrr,Node[here].con); } void cha(int l,int r,int x,int y,long long con,int here) { if(Node[here].nxt==-2) { if(y==l&&y==r) { Node[here].con=con; return; } if(y<=(l+r)/2) { if(Node[here].nxl==-1) { Node[here].nxl=now++; New(l,(l+r)/2,Node[here].nxl,-2); } cha(l,(l+r)/2,x,y,con,Node[here].nxl); Node[here].con=Node[Node[here].nxl].con; if(Node[here].nxr!=-1) Node[here].con=gcd2(Node[here].con,Node[Node[here].nxr].con); } else { if(Node[here].nxr==-1) { Node[here].nxr=now++; New((l+r)/2+1,r,Node[here].nxr,-2); } cha((l+r)/2+1,r,x,y,con,Node[here].nxr); Node[here].con=Node[Node[here].nxr].con; if(Node[here].nxl!=-1) Node[here].con=gcd2(Node[here].con,Node[Node[here].nxl].con); } //if(y==76) printf("%lld %lld %lld %lld\n",y,l,r,Node[here].con); } else { if(x==l&&x==r) { if(Node[here].nxt==-1) { Node[here].nxt=now++; New(0,M-1,Node[here].nxt,-2); } cha(0,M-1,x,y,con,Node[here].nxt); return; } if(x<=(l+r)/2) { if(Node[here].nxl==-1) { Node[here].nxl=now++; New(l,(l+r)/2,Node[here].nxl,-1); } cha(l,(l+r)/2,x,y,con,Node[here].nxl); } else { if(Node[here].nxr==-1) { Node[here].nxr=now++; New((l+r)/2+1,r,Node[here].nxr,-1); } cha((l+r)/2+1,r,x,y,con,Node[here].nxr); } if(Node[here].nxt==-1) { Node[here].nxt=now++; New(0,M-1,Node[here].nxt,-2); } //printf("aa %d %d\n",l,r); Merge(Node[here].nxt,Node[Node[here].nxl].nxt,Node[Node[here].nxr].nxt,y,0,M-1); } } long long Find(int l,int r,int x1,int y1,int x2,int y2,int here) { //printf("%lld %lld %lld %lld %lld\n",x1,y1,x2,y2,here); if(here==-1) return 0; if(Node[here].nxt==-2) { if(l==x2&&r==y2) { //printf("%lld %lld %lld\n",x2,y2,Node[here].con); return Node[here].con; } if(y2<=(l+r)/2) return Find(l,(l+r)/2,x1,y1,x2,y2,Node[here].nxl); if(x2>(l+r)/2) return Find((l+r)/2+1,r,x1,y1,x2,y2,Node[here].nxr); return gcd2(Find(l,(l+r)/2,x1,y1,x2,(l+r)/2,Node[here].nxl),Find((l+r)/2+1,r,x1,y1,(l+r)/2+1,y2,Node[here].nxr)); } else { if(l==x1&&r==y1) return Find(0,M-1,x1,y1,x2,y2,Node[here].nxt); if(y1<=(l+r)/2) return Find(l,(l+r)/2,x1,y1,x2,y2,Node[here].nxl); if(x1>(l+r)/2) return Find((l+r)/2+1,r,x1,y1,x2,y2,Node[here].nxr); return gcd2(Find(l,(l+r)/2,x1,(l+r)/2,x2,y2,Node[here].nxl),Find((l+r)/2+1,r,(l+r)/2+1,y1,x2,y2,Node[here].nxr)); } } void update(int P, int Q, long long K) { cha(0,N-1,P,Q,K,0); } long long calculate(int P, int Q, int U, int V) { long long ans=0,i; //printf("aaa\n"); ans=Find(0,N-1,P,U,Q,V,0); /*for(i=P;i<=U;i++) { ans=gcd2(ans,Find(i,i,Q,V,0)); //if(P==60) printf("%lld %lld\n",i,Find(i,i,Q,V,0)); }*/ //printf("cc %lld\n",ans); return ans; }

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'long long int calculate(int, int, int, int)':
game.cpp:174:21: warning: unused variable 'i' [-Wunused-variable]
  174 |     long long ans=0,i;
      |                     ^
game.cpp: In function 'void Merge(int, int, int, int, int, int)':
game.cpp:50:14: warning: 'll' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |         Merge(Node[here].nxl,ll,rr,what,lll,(lll+rrr)/2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:50:14: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
#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...