Submission #687860

#	Time	Username	Problem	Language	Result	Execution time	Memory
687860		lam	Game (IOI13_game)	C++17	100 / 100	7060 ms	67580 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define ll long long
using namespace std;

typedef pair<int,int> ii;
#define ff first
#define ss second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int inf = 1e9 + 7;
int n,m;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct node
{
    node *l=nullptr, *r=nullptr;
    int wt; ll val=0LL, vval=0LL;
    ii key;
    node (ii _key, ll x)
    {
        key=_key; val=x;
        vval=x;
        wt=rng()%INT_MAX;
    }
};

struct Node
{
    Node *l=nullptr, *r=nullptr;
    node *it=nullptr;
    Node() {}
};

Node *tree = nullptr;

inline ll get_g(node *&x)
{
    return (x)?x->val:0LL;
}

void upd(node *&x)
{
    if (!x) return;
    x->val = gcd2(x->vval,gcd2(get_g(x->l),get_g(x->r)));
}

pair<node*, node*> split(node *x, ii key)
{
    if (!x) return {nullptr,nullptr};
    if (x->key<=key) {pair<node*,node*> tt=split(x->r,key); x->r=tt.ff; upd(x); return{x,tt.ss}; }
    else {pair<node*,node*> tt=split(x->l,key); x->l=tt.ss; upd(x); return {tt.ff,x}; }
}

node* merg(node *l, node *r)
{
    if (!l||!r) return (!l)?r:l;
    if (l->wt>r->wt){
        l->r=merg(l->r,r); upd(l); return l;
    }
    else {
        r->l=merg(l,r->l); upd(r); return r;
    }
}

void ins(node *&x, ii key, ll val)
{
//    cout<<key.ff<<' '<<key.ss<<" = "<<val<<'\n';
    auto [a,b] = split(x,make_pair(key.ff,key.ss-1));
    auto [c,d] = split(b,key);
    x = merg(merg(a,(new node(key,val))),d);
}

ll get2(node *&x, int l, int r)
{
    auto [a,b] = split(x,make_pair(l-1,inf));
    auto [c,d] = split(b,make_pair(r,inf));
    ll ans = get_g(c);
//    cout<<ans<<'\n';
    x = merg(a,merg(c,d));
    return ans;
}

void updat(Node *&x, int lx, int rx, int idx, int idy, ll val)
{
    if (!x) x=new Node();
//    cout<<lx<<' '<<rx<<" + ";
    ins(x->it,{idy,idx},val);
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (idx<=mid) updat(x->l,lx,mid,idx,idy,val);
    else updat(x->r,mid+1,rx,idx,idy,val);
}

ll get(Node *x, int lx, int rx, int l, int r, int ly, int ry)
{
    if (!x) return 0LL;
    if (lx>r||rx<l) return 0LL;
    if (lx>=l&&rx<=r)
    {
//        cout<<l<<' '<<r<<' '<<ly<<' '<<ry<<": ";
        return get2(x->it,ly,ry);
    }
    int mid=(lx+rx)/2;
    return gcd2(get(x->l,lx,mid,l,r,ly,ry),get(x->r,mid+1,rx,l,r,ly,ry));
}

void init(int R, int C) {
    n=R; m=C;
}

void update(int P, int Q, long long K) {
    P++; Q++;
    updat(tree,1,n,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    P++; Q++; U++; V++;
    return get(tree,1,n,P,U,Q,V);
}

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