| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 116803 | kig9981 | Game (IOI13_game) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);}