Submission #561418

#	Time	Username	Problem	Language	Result	Execution time	Memory
561418		stefantaga	Game (IOI13_game)	C++14	0 / 100	1 ms	340 KiB

game

#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 = rand();
        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(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+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

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