제출 #765223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765223		fatemetmhr	게임 (IOI13_game)	C++17	0 / 100	1 ms	308 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 =  1e7;
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], 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 innerupd(int l, int r, int id, ll val, int v){
    if(r - l == 1){
        g[v] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid){
        if(!innerchil[v][0])
            innerchil[v][0] = innernode++;
        innerupd(l, mid, id, val, innerchil[v][0]);
    }
    else{
        if(!innerchil[v][1])
            innerchil[v][1] = innernode++;
        innerupd(mid, r, id, val, innerchil[v][1]);
    }
    g[v] = gcd2(g[innerchil[v][0]], g[innerchil[v][1]]);
}


ll innerget(int l, int r, int lq, int rq, int v){
    if(rq <= l || r <= lq)
        return 0;
    if(lq <= l && r <= rq)
        return g[v];
    int mid = (l + r) >> 1;
    if(!innerchil[v][0])
        innerchil[v][0] = innernode++;
    if(!innerchil[v][1])
        innerchil[v][1] = innernode++;
    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++;
    innerupd(0, m, id2, val, inner[v]);
    if(r - l == 1)
        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]);
    }
}

ll get(int l, int r, int lq, int rq, int llq, int rrq, int v){
    if(rq <= l || r <= lq)
        return 0;
    if(lq <= l && r <= rq){
        if(!inner[v])
            return 0;
        return innerget(0, m, llq, rrq, inner[v]);
    }
    int mid = (l + r) >> 1;
    if(!chil[v][0])
        chil[v][0] = newnode++;
    if(!chil[v][1])
        chil[v][1] = newnode++;
    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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20