| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 601657 | alirezasamimi100 | 게임 (IOI13_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<int,int>;
const int T=800;
long long gcd2(long long X, long long Y) {
long long tmp;
if(X<Y) swap(X,Y);
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct n1{
n1 *lc,*rc;
ll x;
n1(){
lc=rc=nullptr;
x=0;
}
};
struct n2{
n2 *lc,*rc;
n1 *x;
n2(){
lc=rc=nullptr;
x=new n1;
}
} *rt=new n2;
int n,m;
map<pii,ll> mp;
void upd1(const n1 *v, const int &l, const int &r, const int &p, const ll &x, const int &k = -1){
if(r-l<=T && k!=-1){
v->x=0;
for(int i=l; i<r; i++) if(mp.count({k,i})) v->x=gcd2(v->x,mp[{k,i}]);
return;
}
if(r-l==1){
v->x=x;
return;
}
int m=(l+r)>>1;
if(p<m){
if(!v->lc) v->lc=new n1;
upd1(v->lc,l,m,p,x,k);
}else{
if(!v->rc) v->rc=new n1;
upd1(v->rc,m,r,p,x,k);
}
v->x=0;
if(v->lc) v->x=gcd2(v->x,v->lc->x);
if(v->rc) v->x=gcd2(v->x,v->rc->x);
}
ll get1(const n1 *v, const int &l, const int &r, const int &tl, const int &tr, const int &k = -1){
if(l>=tr || tl>=r || tl>=tr) return 0;
if(l>=tl && r<=tr) return v->x;
if(r-l<=T && k!=-1){
ll ans=0;
for(int i=l; i<r; i++) if(i>=tl && i<tr && mp.count({k,i})) ans=gcd2(ans,mp[{k,i}]);
return ans;
}
int m=(l+r)>>1;
ll ans=0;
if(v->lc) ans=gcd2(ans,get1(v->lc,l,m,tl,tr,k));
if(v->rc) ans=gcd2(ans,get1(v->rc,m,r,tl,tr,k));
return ans;
}
void upd2(const n2 *v, const int &l, const int &r, const int &p, const int &q, const ll &x){
if(r-l==1){
upd1(v->x,0,m,q,x,l);
return;
}
int m=(l+r)>>1;
if(p<m){
if(!v->lc) v->lc=new n2;
upd2(v->lc,l,m,p,q,x);
}else{
if(!v->rc) v->rc=new n2;
upd2(v->rc,m,r,p,q,x);
}
ll y=0;
if(v->lc){
if(m-l==1) y=gcd2(y,get1(v->lc->x,0,::m,q,q+1,l));
else y=gcd2(y,get1(v->lc->x,0,::m,q,q+1));
}
if(v->rc){
if(r-m==1) y=gcd2(y,get1(v->rc->x,0,::m,q,q+1,m));
else y=gcd2(y,get1(v->rc->x,0,::m,q,q+1));
}
upd1(v->x,0,::m,q,y);
}
ll get2(const n2 *v, const int &l, const int &r, const int &tl, const int &tr, const int &tp, const int &tq){
if(l>=tr || tl>=r || tl>=tr) return 0;
if(l>=tl && r<=tr){
if(r-l==1) return get1(v->x,0,m,tp,tq,l);
return get1(v->x,0,m,tp,tq);
}
int m=(l+r)>>1;
ll ans=0;
if(v->lc) ans=gcd2(ans,get2(v->lc,l,m,tl,tr,tp,tq));
if(v->rc) ans=gcd2(ans,get2(v->rc,m,r,tl,tr,tp,tq));
return ans;
}
void init(int R, int C) {
n=R;
m=C;
}
void update(int p, int q, long long k) {
mp[{p,q}]=k;
upd2(rt,0,n,p,q,k);
}
long long calculate(int p, int q, int u, int v) {
return get2(rt,0,n,p,u+1,q,v+1);
}