Submission #400251

#	Time	Username	Problem	Language	Result	Execution time	Memory
400251		Antekb	Game (IOI13_game)	C++14	80 / 100	4848 ms	256004 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;
}
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;
}
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 wsk2=1;
int l2[K], r2[K], val2[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(val2[v], 0, N-1, 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){
        val2[v]=upd1d(val2[v], 0, N-1, 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);
    val2[v]=upd1d(val2[v], 0, N-1, j, gcd2(quer1d(val2[l2[v]], 0, N-1, j, j), quer1d(val2[r2[v]], 0, N-1, 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: 0 / 20