제출 #400302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
400302		Antekb	Game (IOI13_game)	C++14	100 / 100	9607 ms	28564 KiB

game

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

using namespace std;

typedef long long ll;
const int N=(1<<30), M=5e6, 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());
int wsk1=1;
int l1[M], r1[M], Rank[M], Key[M];
ll val1[M], g[M];
/*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(int v){
    g[v]=val1[v];
    if(l1[v])g[v]=gcd2(g[l1[v]], g[v]);
    if(r1[v])g[v]=gcd2(g[r1[v]], g[v]);
}
int merge(int u, int v){
    if(!u)return v;
    if(!v)return u;
    assert(Key[u] < Key[v]);
    if(Rank[v]>Rank[u]){
        l1[v]=merge(u, l1[v]);
        upd(v);
        return v;
    }
    else{
        r1[u]=merge(r1[u], v);
        upd(u);
        return u;
    }
}
#define mp(x, y) make_pair(x, y)
#define st first
#define nd second
typedef pair<int, int> pnn;
pnn split(int v, int l){
    if(!v)return mp(0, 0);
    if(Key[v]<l){
        pnn a=split(r1[v], l);
        r1[v]=a.st;
        upd(v);
        a.st=v;
        return a;
    }
    else{
        pnn a=split(l1[v], l);
        l1[v]=a.nd;
        upd(v);
        a.nd=v;
        return a;
    }
}
void wyp(int v){
    if(!v) return;
    wyp(l1[v]);
    cout<<Rank[v]<<" "<<Key[v]<<" "<<val1[v]<<" "<<g[v]<<"\n";
    wyp(r1[v]);
}
/*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(int 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=g[b.st];
        assert(Key[b.st] >=l && Key[b.st] <=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;
}*/
int upd1d(int v, int i, ll val){
    pnn a=split(v, i);
    pnn b=split(a.nd, i+1);
    if(b.st){
        assert(Key[b.st] == i);
        val1[b.st]=val;
    }
    else{
        b.st=wsk1;
        val1[wsk1]=val;
        g[wsk1]=val;
        Key[wsk1]=i;
        Rank[wsk1]=rng();
        wsk1++;
    }
    upd(b.st);
    a.nd=merge(b.st, b.nd);
    return merge(a.st, a.nd);
}

int wsk2=1;
int l2[K], r2[K];
int 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) {
    /* ... */
}

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