Submission #598508

#	Time	Username	Problem	Language	Result	Execution time	Memory
598508		Bench0310	Game (IOI13_game)	C++17	100 / 100	5803 ms	77696 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;
typedef long long ll;

mt19937 gen(513);
int N,M;

struct Treap;
using twoTreaps=array<Treap*,2>;

struct Treap
{
    int p;
    ll val;
    ll g;
    int priority;
    twoTreaps kids;
    Treap(int np,ll ng){p=np;val=g=ng;priority=gen();kids[0]=kids[1]=nullptr;}
};

void recalc(Treap *me)
{
    if(!me) return;
    me->g=gcd(gcd(me->kids[0]?me->kids[0]->g:0,me->kids[1]?me->kids[1]->g:0),me->val);
}

twoTreaps tsplit(Treap *me,int lim) //p<=lim
{
    if(!me) return {nullptr,nullptr};
    if(me->p>lim)
    {
        auto [one,two]=tsplit(me->kids[0],lim);
        me->kids[0]=two;
        recalc(me);
        return {one,me};
    }
    else
    {
        auto [one,two]=tsplit(me->kids[1],lim);
        me->kids[1]=one;
        recalc(me);
        return {me,two};
    }
}

Treap* tmerge(Treap *a,Treap *b)
{
    if(!a) return b;
    if(!b) return a;
    if(a->priority<b->priority)
    {
        a->kids[1]=tmerge(a->kids[1],b);
        recalc(a);
        return a;
    }
    else
    {
        b->kids[0]=tmerge(a,b->kids[0]);
        recalc(b);
        return b;
    }
}

Treap* tupdate(Treap *me,int p,ll g)
{
    auto [one,tmp]=tsplit(me,p-1);
    auto [two,three]=tsplit(tmp,p);
    if(two==nullptr) two=new Treap(p,g);
    else two->val=two->g=g;
    return tmerge(tmerge(one,two),three);
}

ll tquery(Treap *me,int l,int r)
{
    auto [one,tmp]=tsplit(me,l-1);
    auto [two,three]=tsplit(tmp,r);
    ll g=(two?two->g:0);
    tmerge(tmerge(one,two),three);
    return g;
}

struct Up
{
    Treap *me;
    Up *l,*r;
    Up(){me=nullptr;l=r=nullptr;}
    void extend(){if(!l){l=new Up();r=new Up();}}
};

void update(Up *now,int l,int r,int pos_r,int pos_c,ll g)
{
    if(l==r) now->me=tupdate(now->me,pos_c,g);
    else
    {
        now->extend();
        int m=(l+r)/2;
        if(pos_r<=m) update(now->l,l,m,pos_r,pos_c,g);
        else update(now->r,m+1,r,pos_r,pos_c,g);
        now->me=tupdate(now->me,pos_c,gcd(tquery(now->l->me,pos_c,pos_c),tquery(now->r->me,pos_c,pos_c)));
    }
}

ll query(Up *now,int l,int r,int ql,int qr,int cl,int cr)
{
    if(ql>qr||!now) return 0;
    if(l==ql&&r==qr) return tquery(now->me,cl,cr);
    int m=(l+r)/2;
    return gcd(query(now->l,l,m,ql,min(qr,m),cl,cr),query(now->r,m+1,r,max(ql,m+1),qr,cl,cr));
}

Up* root=nullptr;

void init(int n,int m)
{
    N=n;
    M=m;
    root=new Up();
}

void update(int r,int c,ll k)
{
    update(root,1,N,r+1,c+1,k);
}

ll calculate(int p,int q,int u,int v)
{
    return query(root,1,N,p+1,u+1,q+1,v+1);
}

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