Submission #765278

#	Time	Username	Problem	Language	Result	Execution time	Memory
765278		fatemetmhr	Game (IOI13_game)	C++17	80 / 100	3273 ms	256000 KiB

game

//  ~ Be Name Khoda ~  //

#include "game.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  2e7;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int n, m, newnode = 2, innernode = 2, inner[maxnt];
int chil[maxnt][2], innerchil[maxnt][2];
ll g[maxnt];


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;
}


void innerupdbase(int l, int r, int id, ll val, int v){
    //cout << "inner upd with " << l << ' ' << r << ' ' << id << ' ' << val << ' ' << v << endl;
    if(r - l == 1){
        g[v] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid){
        if(!innerchil[v][0])
            innerchil[v][0] = innernode++;
        innerupdbase(l, mid, id, val, innerchil[v][0]);
    }
    else{
        if(!innerchil[v][1])
            innerchil[v][1] = innernode++;
        innerupdbase(mid, r, id, val, innerchil[v][1]);
    }
    g[v] = gcd2(g[innerchil[v][0]], g[innerchil[v][1]]);
    //cout << "ok " << l << ' ' << r << ' ' << val << ' ' << v << ' ' << g[v] << ' ' << g[innerchil[v][1]] << ' ' << g[innerchil[v][0]] << endl;
}

void innerupdult(int l, int r, int id, int v1, int v2, int v3){
    g[v1] = gcd2(g[v2], g[v3]);
    if(r - l == 1)
        return;
    int mid = (l + r) >> 1;
    if(id < mid){
        if(!innerchil[v1][0])
            innerchil[v1][0] = innernode++;
        innerupdult(l, mid, id, innerchil[v1][0], innerchil[v2][0], innerchil[v3][0]);
    }
    else{
        if(!innerchil[v1][1])
            innerchil[v1][1] = innernode++;
        innerupdult(mid, r, id, innerchil[v1][1], innerchil[v2][1], innerchil[v3][1]);
    }
}


ll innerget(int l, int r, int lq, int rq, int v){
    if(v == 0 || rq <= l || r <= lq)
        return 0;
    if(lq <= l && r <= rq){
        //cout << "inner getting " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << g[v] << endl;
        return g[v];
    }
    int mid = (l + r) >> 1;
    return gcd2(innerget(l, mid, lq, rq, innerchil[v][0]), innerget(mid, r, lq, rq, innerchil[v][1]));
}


void upd(int l, int r, int id, int id2, ll val, int v){
    if(!inner[v])
        inner[v] = innernode++;
    //cout << "entering iiner update " << l << ' ' << r << ' ' << v << ' ' << inner[v] << ' ' << val << endl;
    if(r - l == 1){
        innerupdbase(0, m, id2, val, inner[v]);
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid){
        if(!chil[v][0])
            chil[v][0] = newnode++;
        upd(l, mid, id, id2, val, chil[v][0]);
    }
    else{
        if(!chil[v][1])
            chil[v][1] = newnode++;
        upd(mid, r, id, id2, val, chil[v][1]);
    }
    innerupdult(0, m, id2, inner[v], inner[chil[v][0]], inner[chil[v][1]]);
}

ll get(int l, int r, int lq, int rq, int llq, int rrq, int v){
    if(v == 0 || rq <= l || r <= lq)
        return 0;
    if(lq <= l && r <= rq){
        if(!inner[v])
            return 0;
        ll ret = innerget(0, m, llq, rrq, inner[v]);
        //cout << "here " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << ret << endl;
        return ret;
    }
    int mid = (l + r) >> 1;
    return gcd2(get(l, mid, lq, rq, llq, rrq, chil[v][0]), get(mid, r, lq, rq, llq, rrq, chil[v][1]));
}

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

void update(int x, int y, long long k) {
    upd(0, n, x, y, k, 1);
}

long long calculate(int l, int d, int r, int u) {
    return get(0, n, l, r + 1, d, u + 1, 1);
}

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