Submission #1081966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081966		TheQuantiX	Game (IOI13_game)	C++17	63 / 100	1918 ms	256000 KiB

game

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

using namespace std;
using ll = int;

ll n, m, q, k, x, y, a, b, c;

struct segtree1d {
    vector<long long> tr;
    vector<ll> pl, pr;

    segtree1d() {
        tr.assign(1, 0);
        pl.assign(1, -1);
        pr.assign(1, -1);
    }

    void extend(ll x) {
        for (int i = 0; i < 2; i++) {
            tr.push_back(0);
            pl.push_back(-1);
            pr.push_back(-1);
        }
        pl[x] = tr.size() - 2;
        pr[x] = tr.size() - 1;
    }

    void update(ll x, ll l, ll r, ll idx, long long val) {
        // cout << x << ' ' << l << ' ' << r << ' ' << ' ' << idx << ' ' << val << '\n';
        if (l == r) {
            tr[x] = val;
            return;
        }
        if (pl[x] == -1) {
            extend(x);
        }
        ll mid = (r + l) / 2;
        if (idx <= mid) {
            update(pl[x], l, mid, idx, val);
        }
        else {
            update(pr[x], mid + 1, r, idx, val);
        }
        tr[x] = gcd(tr[pl[x]], tr[pr[x]]);
    }

    long long query(ll x, ll l, ll r, ll L, ll R) {
        if (r < l) {
            return 0;
        }
        if (r < L) {
            return 0;
        }
        if (R < l) {
            return 0;
        }
        if (R < L) {
            return 0;
        }
        if (L <= l && r <= R) {
            return tr[x];
        }
        if (pl[x] == -1) {
            extend(x);
        }
        ll mid = (r + l) / 2;
        return gcd(query(pl[x], l, mid, L, R), query(pr[x], mid + 1, r, L, R));
    }
};

struct segtree {
    vector<segtree1d> tr;
    vector<ll> pl, pr;

    segtree() {
        tr.assign(1, segtree1d());
        pl.assign(1, -1);
        pr.assign(1, -1);
    }

    void extend(ll x) {
        for (int i = 0; i < 2; i++) {
            tr.push_back(segtree1d());
            pl.push_back(-1);
            pr.push_back(-1);
        }
        pl[x] = tr.size() - 2;
        pr[x] = tr.size() - 1;
    }

    void update(ll x, ll l, ll r, ll X, ll Y, long long val) {
        // cout << x << ' ' << l << ' ' << r << ' ' << ' ' << X << ' ' << Y << ' ' << val << '\n';
        if (l == r) {
            tr[x].update(0, 0, m, Y, val);
            return;
        }
        if (pl[x] == -1) {
            extend(x);
        }
        ll mid = (r + l) / 2;
        if (X <= mid) {
            update(pl[x], l, mid, X, Y, val);
        }
        else {
            update(pr[x], mid + 1, r, X, Y, val);
        }
        tr[x].update(0, 0, m, Y, gcd(tr[pl[x]].query(0, 0, m, Y, Y), tr[pr[x]].query(0, 0, m, Y, Y)));
    }

    long long query(ll x, ll l, ll r, ll LX, ll RX, ll LY, ll RY) {
        if (r < l) {
            return 0;
        }
        if (r < LX) {
            return 0;
        }
        if (RX < l) {
            return 0;
        }
        if (RX < LX) {
            return 0;
        }
        if (LX <= l && r <= RX) {
            return tr[x].query(0, 0, m, LY, RY);
        }
        if (pl[x] == -1) {
            extend(x);
        }
        ll mid = (r + l) / 2;
        return gcd(query(pl[x], l, mid, LX, RX, LY, RY), query(pr[x], mid + 1, r, LX, RX, LY, RY));
    }
};

segtree sg;

void init(int R, int C) {
    n = R;
    m = C;
    sg = segtree();
}

void update(int P, int Q, long long K) {
    sg.update(0, 0, n, P, Q, K);
    // cout << '\n';
    // cout << P << ' ' << Q << ' ' << K << endl;
}

long long calculate(int P, int Q, int U, int V) {
    return sg.query(0, 0, n, P, U, Q, V);
}

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