Submission #400296

#	Time	Username	Problem	Language	Result	Execution time	Memory
400296		Antekb	Game (IOI13_game)	C++14	100 / 100	6531 ms	53752 KiB

game

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

using namespace std;

typedef long long ll;
const int N=(1<<30), M=21142005, K=682005;

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;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
struct node{
    node* l=nullptr, *r=nullptr;
    int rank, key;
    ll val, g;
    node(int _key, ll _val): key(_key), val(_val), g(_val) {rank=rng();}
    void upd(){
        g=val;
        if(l)g=gcd2(l->g, g);
        if(r)g=gcd2(r->g, g);
    }
};
node* merge(node* u, node* v){
    if(!u)return v;
    if(!v)return u;
    assert(u->key < v->key);
    if((v->rank)>(u->rank)){
        v->l=merge(u, v->l);
        v->upd();
        return v;
    }
    else{
        u->r=merge(u->r, v);
        u->upd();
        return u;
    }
}
#define mp(x, y) make_pair(x, y)
#define st first
#define nd second
typedef pair<node*, node*> pnn;
pnn split(node* v, int l){
    if(!v)return mp(nullptr, nullptr);
    if(v->key<l){
        pnn a=split(v->r, l);
        v->r=a.st;
        v->upd();
        a.st=v;
        return a;
    }
    else{
        pnn a=split(v->l, l);
        v->l=a.nd;
        v->upd();
        a.nd=v;
        return a;
    }
}
void wyp(node* v){
    if(!v) return;
    wyp(v->l);
    cout<<v->rank<<" "<<v->key<<" "<<v->val<<" "<<v->g<<"\n";
    wyp(v->r);
}
/*int wsk1=1;
int l1[M], r1[M];
ll val1[M];

void upd(int v){
    if(!v)return;
    val1[v]=gcd2(val1[l1[v]], val1[r1[v]]);
}
ll quer1d(int v, int L, int R, int l, int r){
    if(!v)return 0;
    //cout<<L<<" "<<R<<" "<<v->val<<"q\n";
    if(l==L && r==R){
        return val1[v];
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer1d(l1[v], L, M, l, min(M, r)));
    if(r>M)ans=gcd2(ans, quer1d(r1[v], M+1, R, max(l, M+1), r));
    return ans;
}*/
ll quer1d(node* v, int l, int r){
    //wyp(v);
    //cout<<l<<" "<<r<<"\n";

    pnn a=split(v, l);
    pnn b=split(a.nd, r+1);
    ll ans=0;
    if(b.st){
        ans=b.st->g;
        assert(b.st->key >=l && b.st -> key <=r);
    }
    a.nd=merge(b.st, b.nd);
    assert(merge(a.st, a.nd)==v);
    //cout<<ans<<"\n";
    return ans;
}
/*int upd1d(int v, int L, int R, int i, ll val){
    if(!v)v=wsk1++;
    if(L==R){
        //cout<<v->val<<" "<<val<<" "<<i<<"u\n";
        val1[v]=val;
        return v;
    }
    //cout<<L<<" "<<R<<" "<<v->val<<"a\n";
    int M=(L+R)>>1;
    if(i<=M)l1[v]=upd1d(l1[v], L, M, i, val);
    else r1[v]=upd1d(r1[v], M+1, R, i, val);
    upd(v);
    //cout<<L<<" "<<R<<" "<<v->val<<"b\n";
    return v;
}*/
node* upd1d(node* v, int i, ll val){
    pnn a=split(v, i);
    pnn b=split(a.nd, i+1);
    if(b.st){
        assert(b.st->key == i);
        b.st->val=val;
    }
    else b.st=new node(i, val);
    b.st->upd();
    a.nd=merge(b.st, b.nd);
    return merge(a.st, a.nd);
}

int wsk2=1;
int l2[K], r2[K];
node* nodes[K];
ll quer2d(int v, int L, int R, int l, int r, int x, int y){
    if(!v)return 0;
    if(l==L && r==R){
        return quer1d(nodes[v], x, y);
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer2d(l2[v], L, M, l, min(M, r), x, y));
    if(r>M)ans=gcd2(ans, quer2d(r2[v], M+1, R, max(l, M+1), r, x, y));
    return ans;
}

int upd2d(int v, int L, int R, int i, int j, ll val){
    if(!v)v=wsk2++;
    if(L==R){
        //cout<<L<<" "<<R<<" "<<i<<" "<<j<<"\n";
        nodes[v]=upd1d(nodes[v], j, val);
        return v;
    }
    int M=(L+R)>>1;
    if(i<=M)l2[v]=upd2d(l2[v], L, M, i, j, val);
    else r2[v]=upd2d(r2[v], M+1, R, i, j, val);
    //cout<<L<<" "<<R<<" "<<i<<" "<<j<<"\n";
    nodes[v]=upd1d(nodes[v], j, gcd2(quer1d(nodes[l2[v]], j, j), quer1d(nodes[r2[v]], j, j)));
    return v;
}
int root=0;
void init(int R, int C) {
    /* ... */
    for(int i=0; i<K; i++)nodes[i]=nullptr;
}

void update(int P, int Q, long long K) {
    root=upd2d(root, 0, N-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return quer2d(root, 0, N-1, P, U, Q, V);
}

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