제출 #553492

#제출 시각아이디문제언어결과실행 시간메모리
553492nicholask게임 (IOI13_game)C++14
0 / 100
13093 ms340 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; long long gcd(int a,int b){ while (b) b^=a^=b^=a^=b; return a; } int n,m; long long seg[8001][8001]; void updateY(int idX,int tlX,int trX,int idY,int tlY,int trY,int xp,int yp,long long val){ if (tlY==trY){ if (tlX==trX) seg[idX][idY]=val; else seg[idX][idY]=gcd(seg[2*idX][idY],seg[2*idX+1][idY]); return; } int tm=(tlY+trY)/2; if (yp<=tm) updateY(idX,tlX,trX,2*idY,tlY,tm,xp,yp,val); else updateY(idX,tlX,trX,2*idY+1,tm+1,trY,xp,yp,val); seg[idX][idY]=gcd(seg[idX][2*idY],seg[idX][2*idY+1]); } void updateX(int idX,int tlX,int trX,int xp,int yp,long long val){ if (tlX!=trX){ int tm=(tlX+trX)/2; if (xp<=tm) updateX(2*idX,tlX,tm,xp,yp,val); else updateX(2*idX+1,tm+1,trX,xp,yp,val); } updateY(idX,tlX,trX,1,1,m,xp,yp,val); } long long queryY(int idX,int idY,int tlY,int trY,int yps,int ype){ if (yps>ype) return 0; if (yps<=tlY&&trY<=ype) return seg[idX][idY]; int tm=(tlY+trY)/2; long long lx=queryY(idX,2*idY,tlY,tm,yps,min(tm,ype)); long long rx=queryY(idX,2*idY+1,tm+1,trY,max(yps,tm+1),ype); return gcd(lx,rx); } long long queryX(int idX,int tlX,int trX,int xps,int xpe,int yps,int ype){ if (xps>xpe) return 0; if (xps<=tlX&&trX<=xpe) return queryY(idX,1,1,m,yps,ype); int tm=(tlX+trX)/2; long long lx=queryX(2*idX,tlX,tm,xps,min(tm,xpe),yps,ype); long long rx=queryX(2*idX+1,tm+1,trX,max(xps,tm+1),xpe,yps,ype); return gcd(lx,rx); } void init(int R, int C) { n=R; m=C; } void update(int P, int Q, long long K) { P++; Q++; updateX(1,1,n,P,Q,K); } long long calculate(int P, int Q, int U, int V) { P++; Q++; U++; V++; return queryX(1,1,n,P,U,Q,V); }
#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...