| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 553647 | nicholask | 게임 (IOI13_game) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
struct smallnode{
smallnode *lc,*rc;
long long val;
smallnode(){
lc=rc=nullptr;
val=0;
}
};
struct bignode{
bignode *lc,*rc;
smallnode *down;
long long val;
bignode(){
lc=rc=nullptr;
down=nullptr;
val=0;
}
};
bignode *root;
long long gcd(long long a,long long b){
while (b) b^=a^=b^=a%=b;
return a;
}
int n,m;
void init(int R,int C){
root=new bignode;
n=R;
m=C;
}
long long queryY(smallnode *id,int tlY,int trY,int lY,int rY){
if (!id||lY>rY) return 0ll;
if (lY<=tlY&&trY<=rY) return id->val;
int tmY=(tlY+trY)/2;
long long lans=(id->lc?queryY(id->lc,tlY,tmY,lY,min(rY,tmY)):0ll);
long long rans=(id->rc?queryY(id->rc,tmY+1,trY,max(lY,tmY+1),rY):0ll);
return gcd(lans,rans);
}
long long queryX(bignode *id,int tlX,int trX,int lX,int rX,int lY,int rY){
if (!id||lX>rX) return 0ll;
if (lX<=tlX&&trX<=rX) return queryY(id->down,1,m,lY,rY);
int tmX=(tlX+trX)/2;
long long lans=(id->lc?queryX(id->lc,tlX,tmX,lX,min(rX,tmX),lY,rY):0ll);
long long rans=(id->rc?queryX(id->rc,tmX+1,trX,max(lX,tmX+1),rX,lY,rY):0ll);
return gcd(lans,rans);
}
void updateY(smallnode *id,int tlY,int trY,int yp,long long Val){
if (!id) return;
if (tlY==trY){
id->val=Val;
return;
}
int tmY=(tlY+trY)/2;
if (yp<=tmY){
if (!id->lc) id->lc=new smallnode;
updateY(id->lc,tlY,tmY,yp,Val);
} else {
if (!id->rc) id->rc=new smallnode;
updateY(id->rc,tmY+1,trY,yp,Val);
}
long long lans=(id->lc?id->lc->val:0ll);
long long rans=(id->rc?id->rc->val:0ll);
id->val=gcd(lans,rans);
}
void updateX(bignode *id,int tlX,int trX,int xp,int yp,long long Val){
if (!id->down) id->down=new smallnode;
if (tlX==trX){
updateY(id->down,1,m,yp,Val);
return;
}
int tmX=(tlX+trX)/2;
if (xp<=tmX){
if (!id->lc) id->lc=new bignode;
updateX(id->lc,tlX,tmX,xp,yp,Val);
} else {
if (!id->rc) id->rc=new bignode;
updateX(id->rc,tmX+1,trX,xp,yp,Val);
}
long long lans=(id->lc?queryY(id->lc->down,1,m,yp,yp):0ll);
long long rans=(id->rc?queryY(id->rc->down,1,m,yp,yp):0ll);
updateY(id->down,1,m,yp,gcd(lans,rans));
}
void update(int P,int Q,int K){
updateX(root,1,n,P+1,Q+1,K);
}
long long calculate(int P,int Q,int U,int V){
return queryX(root,1,n,P+1,U+1,Q+1,V+1);
}