| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 561407 | stefantaga | 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 <bits/stdc++.h>
#include "game.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll cmmdc (ll a,ll b)
{
if (a==0)
{
return b;
}
if (b==0)
{
return a;
}
ll r = a%b;
while (r)
{
a=b;
b=r;
r=a%b;
}
return b;
}
struct TreapNode
{
ll priority;
ll val,g;
ll st,dr,poz;
TreapNode *fiust,*fiudr;
TreapNode (ll POZ,ll VAL)
{
priority = rng();
val=g=VAL;
st=dr=poz=POZ;
fiust=fiudr=NULL;
}
void update()
{
g=val;
st=dr=poz;
if (fiust)
{
g=cmmdc(g,fiust->g);
st=min(st,fiust->st);
dr=max(dr,fiust->dr);
}
if (fiudr)
{
g=cmmdc(g,fiudr->g);
st=min(st,fiudr->st);
dr=max(dr,fiudr->dr);
}
}
};
struct Treap
{
TreapNode *root;
Treap()
{
root = NULL;
}
void split(TreapNode *t,ll poz,TreapNode *&st,TreapNode *&dr)
{
if (t==NULL)
{
return void(st=dr=NULL);
}
if (t->poz<poz)
{
split(t->fiudr,poz,t->fiudr,dr);
st = t;
}
else
{
split(t->fiust,poz,st,t->fiust);
dr=t;
}
t->update();
}
void Merge(TreapNode *&t,TreapNode *st,TreapNode *dr)
{
if (st==NULL||dr==NULL)
{
if (st==NULL)
{
t=dr;
}
else
{
t=st;
}
return;
}
if (st->priority<dr->priority)
{
Merge(st->fiudr,st->fiudr,dr);
t=st;
}
else
{
Merge(dr->fiust,st,dr->fiust);
t=dr;
}
t->update();
}
bool Find(ll poz)
{
TreapNode *t = root;
while (t)
{
if (t->poz==poz)
{
return true;
}
if (t->poz<poz)
{
t=t->fiudr;
}
else
{
t=t->fiust;
}
}
return false;
}
void update(TreapNode *&t,ll poz,ll val)
{
if (t->poz==poz)
{
t->val=val;
t->update();
return;
}
if (t->poz<poz)
{
update(t->fiudr,poz,val);
}
else
{
update(t->fiust,poz,val);
}
t->update();
}
void Insert(ll poz,ll val)
{
if (Find(poz)==false)
{
TreapNode *T1,*T2;
split(root,poz,T1,T2);
Merge(root,T1,new TreapNode(poz,val));
Merge(root,root,T2);
}
else
{
update(root,poz,val);
}
}
ll query(TreapNode *t , ll ua,ll ub)
{
if (t==NULL)
{
return 0;
}
if (t->dr<ua||ub<t->st)
{
return 0;
}
if (ua<=t->st&&t->dr<=ub)
{
return t->g;
}
return cmmdc(query(t->fiust,ua,ub),query(t->fiudr,ua,ub));
}
ll query(ll st,ll dr)
{
if (root==NULL)
{
return 0;
}
return query(root,st,dr);
}
};
struct SegTree
{
ll st;
ll dr;
Treap treap;
SegTree *fiust,*fiudr;
SegTree()
{
fiust=fiudr=nullptr;
}
SegTree(ll lo,ll hi)
{
fiust=fiudr=nullptr;
st=lo;dr=hi;
}
void new_left()
{
if (fiust==nullptr)
{
fiust = new SegTree(st,(st+dr)/2);
}
}
void new_right()
{
if (fiudr==nullptr)
{
fiudr = new SegTree((st+dr)/2+1,dr);
}
}
void fix(ll poz)
{
ll val=0;
if (fiust)
{
val = cmmdc(val,fiust->treap.query(poz,poz));
}
if (fiudr)
{
val = cmmdc(val,fiudr->treap.query(poz,poz));
}
treap.Insert(poz,val);
}
void update(ll x,ll y,ll val)
{
if (dr<x||x<st)
{
return;
}
if (st==dr)
{
treap.Insert(y,val);
return;
}
ll mij = (st+dr)/2;
if (x<=mij)
{
new_left();
fiust->update(x,y,val);
}
else
{
new_right();
fiudr->update(x,y,val);
}
fix(y);
}
ll query(ll x,ll x2,ll y,ll y2)
{
if (dr<x||x2<st)
{
return 0;
}
if (x<=st&&dr<=x2)
{
return treap.query(y,y2);
}
ll val = 0;
if (fiust)
{
val = cmmdc(val,fiust->query(x,x2,y,y2));
}
if (fiudr)
{
val = cmmdc(val,fiudr->query(x,x2,y,y2));
}
return val;
}
}*seg;
void init(ll n,ll m)
{
seg= new SegTree(1,n);
}
void update(ll x,ll y,ll k)
{
seg->update(x+1,y+1,k);
}
long long calculate(ll x,ll y,ll x2,ll y2)
{
return seg->query(x+1,x2+1,y+1,y2+1);
}
#ifdef HOME
int main()
{
ifstream cin("date.in");
ofstream cout("date.out");
ll n,m,q;
cin>>n>>m>>q;
init(n,m);
for (;q--;)
{
ll tip;
cin>>tip;
if (tip==1)
{
ll P,Q;
long long K;
cin>>P>>Q>>K;
update(P,Q,K);
}
else
{
ll P,Q,U,V;
cin>>P>>Q>>U>>V;
cout<<calculate(P,Q,U,V)<<'\n';
}
}
return 0;
}
#endif // HOME