| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 962767 | serkanrashid | Game (IOI13_game) | C++14 | 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 Tnode
{
long long a;
Tnode *l, *r;
Tnode()
{
a = 0;
l = r = nullptr;
}
};
struct Tree
{
Tnode *A;
Tree *L, *R;
Tree()
{
A = nullptr;
L = R = nullptr;
}
};
Tree *Root;
int r,c;
int Ql,Qr,ql,qr;
int Pos,pos,val;
long long merge1(Tnode *&t1, Tnode *&t2)
{
//if(t1==nullptr&&t2==nullptr) return 0;
if(t1==nullptr) return t2->a;
if(t2==nullptr) return t1->a;
return __gcd(t1->a,t2->a);
}
void upd(Tnode *&t, int l, int r)
{
if(t==nullptr) t = new Tnode();
if(l==r)
{
t->a = val;
return;
}
int mid = (l+r)/2;
if(mid<=pos) upd(t->l,l,mid+0);
else upd(t->r,mid+1,r);
t->a = merge1(t->l,t->r);
}
Tnode *getA(Tree *&t)
{
if(t==nullptr) return nullptr;
return t->A;
}
long long *geta(Tnode *&t)
{
if(t==nullptr) return 0;
return t->a;
}
void Merge(Tnode *&t, Tnode *&t1, Tnode *&t2, int l, int r)
{
if(t==nullptr) t = new Tnode();
if(l==r)
{
t->a = __gcd(geta(t1),geta(t2));
return;
}
int mid = (l+r)/2;
if(mid<=pos) Merge(t->l,t1->l,t2->l,l,mid+0);
else Merge(t->r,t1->r,t2->r,mid+1,r);
t->a = __gcd(geta(t->l),geta(t->r));
}
void Upd(Tree *&t, int l, int r)
{
if(t==nullptr) t = new Tree();
if(l==r)
{
upd(t->A,0,c-1);
return;
}
int mid = (l+r)/2;
if(Pos<=mid) Upd(t->L,l,mid+0);
else Upd(t->R,mid+1,r);
Merge(t->A,getA(t->L),getA(t->R),0,c-1);
}
void update(int P, int Q, long long K)
{
Pos = P;
pos = Q;
val = K;
Upd(Root,0,r-1);
}
long long query(Tnode *&t, int l, int r)
{
if(r<ql||qr<l||l>r) return -1;
if(t==nullptr) return 0;
if(ql<=l&&r<=qr) return t->a;
int mid = (l+r)/2;
long long ch1 = query(t->l,l,mid+0);
long long ch2 = query(t->r,mid+1,r);
if(ch1==-1) return ch2;
if(ch2==-1) return ch1;
return __gcd(ch1,ch2);
}
long long Query(Tree *&t, int l, int r)
{
if(r<Ql||Qr<l||l>r) return -1;
if(t==nullptr) return 0;
if(Ql<=l&&r<=Qr) return query(t->A,0,c-1);
int mid = (l+r)/2;
long long ch1 = Query(t->L,l,mid+0);
long long ch2 = Query(t->R,mid+1,r);
if(ch1==-1) return ch2;
if(ch2==-1) return ch1;
return __gcd(ch1,ch2);
}
long long calculate(int P, int Q, int U, int V)
{
ql = Q;
qr = V;
///
Ql = P;
Qr = U;
long long ans = Query(Root,0,r-1);
if(ans==-1) ans = 0;
return ans;
}
void init(int R, int C)
{
r = R;
c = C;
}