Submission #1075906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075906		mc061	Game (IOI13_game)	C++17	63 / 100	1071 ms	160852 KiB

game

#pragma once

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

const int SZ = 1e9+1;

const int SMALL_SZ = 5e6;

struct smallnode {
    long long ans;
    int left, right;
    smallnode() {
        ans = 0, left = -1, right = -1;
    }
};
smallnode smalls[SMALL_SZ];
int nxt_free = 0;
int create() {
    smalls[nxt_free] = smallnode();
    return nxt_free++;
}

struct bignode {
    int left, right;
    int root;
    bignode() {
        root = -1, left = -1, right = -1;
    }
    void update(int idx, long long val, int x = 0, int tl = 0, int tr = SZ) {
        if (tl == tr) {
            smalls[x].ans = val;
            return;
        }
        int m = (tl + tr) >> 1;
        if (idx <= m) {
            if (smalls[x].left == -1) {
                smalls[x].left = create();
            }
            update(idx, val, smalls[x].left, tl, m);
        }
        else {
            if (smalls[x].right == -1) {
                smalls[x].right = create();
            }
            update(idx, val, smalls[x].right, m+1, tr);
        }
        smalls[x].ans = (smalls[x].left == -1 ? 0 : smalls[smalls[x].left].ans);
        smalls[x].ans = __gcd(smalls[x].ans, (smalls[x].right == -1 ? 0 : smalls[smalls[x].right].ans));
    }
    long long query(int l, int r, int x = 0, int tl = 0, int tr = SZ) {
        if (tl >= l && tr <= r) return smalls[x].ans;
        if (tr < l || tl > r) return 0;
        int m = (tl + tr) >> 1;
        long long from_r = (smalls[x].right == -1 ? 0 : query(l, r, smalls[x].right, m+1, tr));
        long long from_l = (smalls[x].left == -1 ? 0 : query(l, r, smalls[x].left, tl, m));
        return __gcd(from_l, from_r);
    }
};
bignode bigs[1<<16];
int nxt_free_big = 0;
int create_big() {
    bigs[nxt_free_big] = bignode();
    bigs[nxt_free_big].root = create();
    return nxt_free_big++;
}

struct segtree {
    void update(int i, int j, long long val, int x = 0, int tl = 0, int tr = SZ) {
        if (tl == tr) {
            bigs[x].update(j, val, bigs[x].root);
            return;
        }
        int m = (tl + tr) >> 1;
        if (i <= m) {
            if (bigs[x].left == -1) {
                bigs[x].left = create_big();
            }
            update(i, j, val, bigs[x].left, tl, m);
        }
        else {
            if (bigs[x].right == -1) {
                bigs[x].right = create_big();
            }
            update(i, j, val, bigs[x].right, m+1, tr);
        }
        long long from_l = (bigs[x].left == -1 ? 0 : bigs[bigs[x].left].query(j, j, bigs[bigs[x].left].root));
        long long from_r = (bigs[x].right == -1 ? 0 : bigs[bigs[x].right].query(j, j, bigs[bigs[x].right].root));
        bigs[x].update(j, __gcd(from_l, from_r), bigs[x].root);
    }
    long long query(int l, int r, int jl, int jr, int x = 0, int tl = 0, int tr = SZ) {
        if (tl >= l && tr <= r) {
            return bigs[x].query(jl, jr, bigs[x].root);
        }
        if (tl > r || l > tr) return 0;
        int m = (tl + tr) >> 1;
        long long from_l = 0;
        long long from_r = 0;
        if (bigs[x].left != -1) from_l = query(l, r, jl, jr, bigs[x].left, tl, m);
        if (bigs[x].right != -1) from_r = query(l, r, jl, jr, bigs[x].right, m+1, tr);
        return __gcd(from_l, from_r);
    }
};

const int SQ = 1e3+1;
segtree now;

void init(int R, int C) {
    create_big();
}
void update(int P, int Q, long long K) {
    now.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
    return now.query(P, U, Q, V);
}

Compilation message (stderr)

game.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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