| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 561394 | stefantaga | 게임 (IOI13_game) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
struct TreapNode
{
ll priority;
ll val,g;
int st,dr,poz;
TreapNode *fiust,*fiudr;
TreapNode (int poz,ll val)
{
priority = rng();
val=val;
st=dr=poz=poz;
fiust=fiudr=NULL;
}
void update()
{
g=val;
st=dr=poz;
if (fiust)
{
g=__gcd(g,fiust->g);
st=min(st,fiust->st);
dr=max(dr,fiust->dr);
}
if (fiudr)
{
g=__gcd(g,fiudr->g);
st=min(st,fiudr->st);
dr=max(dr,fiudr->dr);
}
}
};
struct Treap
{
TreapNode *root;
Treap()
{
root = NULL;
}
void split(TreapNode *t,int 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(int 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,int 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(int 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 , int ua,int ub)
{
if (t==NULL)
{
return 0;
}
if (t->dr<ua||ub<t->dr)
{
return 0;
}
if (ua<=t->st&&t->dr<=ub)
{
return t->g;
}
return __gcd(query(t->fiust,ua,ub),query(t->fiudr,ua,ub));
}
ll query(int st,int dr)
{
if (root==NULL)
{
return 0;
}
return query(root,st,dr);
}
};
struct SegTree
{
int g;;
int st;
int dr;
Treap *treap;
SegTree *fiust,*fiudr;
SegTree()
{
fiust=fiudr=nullptr;
}
SegTree(int lo,int 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(int poz)
{
ll val=0;
if (fiust)
{
val = __gcd(val,fiust->treap->query(poz,poz));
}
if (fiudr)
{
val = __gcd(val,fiudr->treap->query(poz,poz));
}
treap->Insert(poz,val);
}
void update(int x,int y,ll val)
{
if (dr<x||x<st)
{
return;
}
if (st==dr)
{
treap->Insert(y,val);
return;
}
int 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(int x,int x2,int y,int y2)
{
if (dr<x||x2<st)
{
return 0;
}
if (st<=x&&x2<=dr)
{
return treap->query(y,y2);
}
ll val = 0;
if (fiust)
{
val = __gcd(val,fiust->query(x,x2,y,y2));
}
if (fiudr)
{
val = __gcd(val,fiudr->query(x,x2,y,y2));
}
return val;
}
}*seg;
void Init(int n,int m)
{
seg= new SegTree(1,n);
}
void update(int x,int y,ll k)
{
seg->update(x+1,y+1,k);
}
long long calculate(int x,int y,int x2,int y2)
{
return seg->query(x,x2,y,y2);
}