Submission #871281

#	Time	Username	Problem	Language	Result	Execution time	Memory
871281		HuyQuang_re_Zero	Game (IOI13_game)	C++14	100 / 100	4346 ms	67800 KiB

game

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))

#include "game.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GCD(ll a,ll b) { return (a==0 && b==0) ? 0 : __gcd(a,b); }
struct treap
{
    treap *left,*right;
    ll key,prio,val,my_val;
    treap(ll _key,ll _val) { key=_key; val=my_val=_val; prio=rng(); left=right=NULL; }
    void comp()
    {
        val=GCD(my_val,GCD(left==NULL ? 0 : left->val,right==NULL ? 0 : right->val));
    }
};

TII Split(treap *u,ll key)
{
    if(u==NULL) return { NULL,NULL };
    if(u->key>key)
    {
        TII x=Split(u->left,key);
        u->left=x.snd;
        u->comp();
        return { x.fst,u };
    }
    else
    {
        TII x=Split(u->right,key);
        u->right=x.fst;
        u->comp();
        return { u,x.snd };
    }
}

treap *Merge(treap *u,treap *v)
{
    if(u==NULL && v==NULL) return NULL;
    if(u==NULL) return v;
    if(v==NULL) return u;
    if(u->prio>=v->prio)
    {
        u->right=Merge(u->right,v);
        u->comp();
        return u;
    }
    else
    {
        v->left=Merge(u,v->left);
        v->comp();
        return v;
    }
}
ll get_range(treap *u,ll l,ll r)
{
    TII x=Split(u,l-1);
    TII y=Split(x.snd,r);
   // cerr<<y.fst->key<<'\n';
    ll res=(y.fst==NULL ? 0 : y.fst->val);
    treap *tg=Merge(x.fst,y.fst);
    Merge(tg,y.snd);
    return res;
}
treap *Assign(treap *u,ll key,ll val)
{
    TII x=Split(u,key-1);
    TII y=Split(x.snd,key);
    treap *v=new treap(key,val);
  //  get_range(v,key,key)<<'\n';
   // exit(0);
    u=Merge(x.fst,v);
  //  cerr<<get_range(u,val,val)<<'\n';
    u=Merge(u,y.snd);
  //  cerr<<get_range(u,val,val)<<'\n';
    return u;
}


////////////////////////////////////////////////////////////////////////
struct node
{
    node *left,*right;
    treap *tree;
} *root;
treap *get_tree(node *u) { return (u==NULL) ? NULL : u->tree; }
node *UPDATE(node *u,int l,int r,int x,int y,ll k)
{
    if(u==NULL) u=new node();
    if(l==r)
    {
        u->tree=Assign(u->tree,y,k);
        return u;
    }
    int mid=(l+r)>>1;
    if(x<=mid) u->left=UPDATE(u->left,l,mid,x,y,k);
    else u->right=UPDATE(u->right,mid+1,r,x,y,k);
    u->tree=Assign(u->tree,y,GCD(get_range(get_tree(u->left),y,y),get_range(get_tree(u->right),y,y)));
    return u;
}

ll GET(node *u,int l,int r,int x1,int y1,int x2,int y2)
{
    if(u==NULL || x1>r || x2<l) return 0;
    if(x1<=l && r<=x2) return get_range(u->tree,y1,y2);
    int mid=(l+r)>>1;
    return GCD(GET(u->left,l,mid,x1,y1,x2,y2),GET(u->right,mid+1,r,x1,y1,x2,y2));
}

ll n,m,x,y,k,q,type;
void init(int _n,int _m) { n=_n; m=_m; }
void update(int x,int y,ll k)
{
    root=UPDATE(root,1,n,x+1,y+1,k);
}
ll calculate(int x1,int y1,int x2,int y2)
{
    return GET(root,1,n,x1+1,y1+1,x2+1,y2+1);
}

/*
int main()
{
    freopen("game.inp","r",stdin);
    freopen("game.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    init(n,m);
    while(cin>>type)
        if(type==1) cin>>x>>y>>k,update(x,y,k);
        else
        {
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            cout<<calculate(x1,y1,x2,y2)<<'\n';
        }
}
*/

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20