| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 116803 | kig9981 | 게임 (IOI13_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct Seg
{
int l, r, s, e;
long long v;
Seg() : l(0), r(0), v(0), s(0), e(-1) {}
};
const int MAX=1e9;
vector<Seg> tree(2), tree2(1);
long long GCD(long long a, long long b)
{
for(;b;a%=b,swap(a,b));
return a;
}
long long get_gcd2(int n1, int n2, int p)
{
if(p==0 || n2<tree[p].s || tree[p].e<n1) return 0;
if(n1<=tree[p].s && tree[p].e<=n2) return tree2[p].v;
return GCD(get_gcd2(n1,n2,tree2[p].l),get_gcd2(n1,n2,tree2[p].r));
}
long long get_gcd(int x1, int x2, int y1, int y2, int p=1, int s=0, int e=MAX)
{
int m=(s+e)>>1;
if(p==0 || x2<s || e<x1) return 0;
if(x1<=s && e<=x2) return get_gcd2(y1,y2,tree[p].v);
return GCD(get_gcd(x1,x2,y1,y2,tree[p].l,s,m),get_gcd(x1,x2,y1,y2,tree[p].r,m+1,e));
}
void set_tree2(int n, long long v, int p)
{
int s=0, e=MAX, sz=0;
static int S[33];
if(tree[p].s<tree[p].e) S[sz++]=p;
while(s<e) {
int m=(s+e)>>1;
if(tree[p].e==-1) break;
else if(tree[p].s==s && tree[p].e==e) {
if(n<=m) {
if(tree[p].l==0) tree[p].l=tsz++;
p=tree[p].l; e=m;
}
else {
if(tree[p].r==0) tree[p].r=tsz++;
p=tree[p].r; s=m+1;
}
if(tree[p].s<tree[p].e) S[sz++]=p;
}
else if(m<tree[p].s) {
if(n<=m) {
tree[tsz].l=tree[p].l; tree[tsz].r=tree[p].r; tree[tsz].s=tree[p].s; tree[tsz].e=tree[p].e;
tree[tsz].v=tree[p].v;
tree[p].s=s; tree[p].e=e; tree[p].r=tsz; tree[p].l=++tsz;
S[sz++]=p; p=tsz++;
break;
}
s=m+1;
}
else {
if(n>m) {
tree[tsz].l=tree[p].l; tree[tsz].r=tree[p].r; tree[tsz].s=tree[p].s; tree[tsz].e=tree[p].e;
tree[tsz].v=tree[p].v;
tree[p].s=s; tree[p].e=e; tree[p].l=tsz; tree[p].r=++tsz;
S[sz++]=p; p=tsz++;
break;
}
e=m;
}
}
if(tree[p].e==-1) tree[p].s=tree[p].e=n;
tree[p].v=v;
while(sz--) {
p=S[sz];
tree[p].v=GCD(tree[tree[p].l].v,tree[tree[p].r].v);
}
}
void set_tree(int x, int y, long long v, int p=1, int s=0, int e=MAX)
{
int m=(s+e)>>1;
if(tree[p].v==0) tree[p].v=tree2.size(), tree2.push_back(Seg());
if(s==e) {
set_tree2(y,v,tree[p].v);
return;
}
if(x<=m) {
if(tree[p].l==0) tree[p].l=tree.size(), tree.push_back(Seg());
set_tree(x,y,v,tree[p].l,s,m);
}
else {
if(tree[p].r==0) tree[p].r=tree.size(), tree.push_back(Seg());
set_tree(x,y,v,tree[p].r,m+1,e);
}
set_tree2(y,GCD(get_gcd2(y,y,tree[tree[p].l].v),get_gcd2(y,y,tree[tree[p].r].v)),tree[p].v);
}
void init(int R, int C) {}
void update(int P, int Q, long long K) {set_tree(P,Q,K);}
long long calculate(int P, int Q, int U, int V) {return get_gcd(P,U,Q,V);}