| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1191614 | tyellow | Game (IOI13_game) | C++17 | 0 ms | 0 KiB |
#include "game.h"
#include"bits/stdc++.h"
#define pb push_back
#define int long long
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define F first
#define S second
#define LINE cout<<"--------------------------\n";
#define endl cout << '\n';
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
const int inf = 1000000000;
const int maxn = 2e5;
int r , c , n ;
//Treap
struct node
{
node *l , *r;
int pri , val , gcd , pos;
node(){}
node(int _val , int _pos){
l=r=nullptr;
pri = rand() , val = _val , gcd=_val , pos = _pos;
}
inline void up(){
int a = 0 , b = 0;
if(l!=nullptr) a = l->gcd;
if(r!=nullptr) b = r->gcd;
gcd = __gcd(val,__gcd(a , b));
}
}mem[maxn<<3];
node *merge(node *a , node *b){
if(a == nullptr) return b;
if(b == nullptr) return a;
if(a->pri < b->pri){
a->r = merge(a->r , b);
return a->up() , a;
}
else{
b->l = merge(a , b->l);
return b->up() , b;
}
}
void split(node *root , node *&a , node *&b , int pos){
if(root == nullptr) return a=b=nullptr , void();
if(root->pos <= pos){
a = root;
split(root->r , a->r , b , pos);
}
else{
b = root;
split(root->l , a , b->l , pos);
}
root->up();
}
int top = 0;
void insert(node *&root , int val , int pos){
node *a=nullptr , *b=nullptr , *c=nullptr , *d=nullptr;
split(root , a , b , pos);
split(a , c , d , pos-1);
if(d == nullptr) mem[top]=node(val,pos) , a = merge(c , &mem[top++]) ;
else d->val = val , d->gcd = val , a = merge(c , d);
root = merge(a , b);
}
int query(node *&root , int l , int r, int x1 , int x2){
int res = 0;
node *a , *b , *c , *d;
split(root , a , b , l-1);
split(b , c , d , r);
if(c != nullptr) res = c->gcd;
root = merge(a , merge(c , d));
return res;
}
//Segment Tree
struct st
{
st *lc , *rc;
node *treap;
st(){
lc = rc = nullptr;
treap = nullptr;
}
}*stroot=nullptr,stmem[maxn<<3];
int sttop;
int st_query(int l , int r , int x1 , int x2 , int y1 , int y2 , st *rt){
if(rt == nullptr) return 0;
if(rt->treap == nullptr) return 0;
if(x1 <= l && r <= x2) return query(rt->treap , y1 , y2 , l , r);
int mid = (l+r)>>1;
if(x2 <= mid) return st_query(l , mid , x1 , x2 , y1 , y2 , rt->lc);
else if(x1 > mid) return st_query(mid+1 , r , x1 , x2 , y1 , y2 , rt->rc);
else return __gcd(st_query(l , mid , x1 , x2 , y1 , y2 , rt->lc)
,st_query(mid+1 , r , x1 , x2 , y1 , y2 , rt->rc));
}
void modify(int l , int r , int x , int y , int val , st *&rt){
if(rt == nullptr) stmem[sttop]=st() , rt = &stmem[sttop++];
if(l == r) return insert(rt->treap , val , y), void();
int mid = (l+r)>>1;
if(x <= mid) modify(l , mid , x , y , val , rt->lc);
else modify(mid+1 , r , x , y , val , rt->rc);
//merge treap
if(rt->lc == nullptr && rt->rc == nullptr) insert(rt->treap , val , y);
else if(rt->rc == nullptr) insert(rt->treap , query(rt->lc->treap , y , y , l , r) , y);
else if(rt->lc == nullptr) insert(rt->treap , query(rt->rc->treap , y , y , l , r) , y);
else{
int a = query(rt->lc->treap , y , y , l , r) , b = query(rt->rc->treap , y , y , l , r);
insert(rt->treap , __gcd(a , b) , y);
}
}
void init(int R, int C) {
r = R, c = C;
}
void update(int P, int Q, int K) {
modify(0 , r-1 , P , Q , K , stroot);
}
int calculate(int P, int Q, int U, int V) {
cout << st_query(0 , r-1 , P , U , Q , V , stroot) << '\n';
}