Submission #1077897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077897		TheQuantiX	Game (IOI13_game)	C++17	37 / 100	13073 ms	19492 KiB

game

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

using namespace std;
using ll = long long;

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

struct segtree {
    vector<ll> tr;
    vector<ll> ur, ul, dr, dl;

    segtree() {
        tr.assign(1, 0);
        ur.assign(1, -1);
        ul.assign(1, -1);
        dr.assign(1, -1);
        dl.assign(1, -1);
    }

    void extend(ll x) {
        for (int i = 0; i < 4; i++) {
            tr.push_back(0);
            ul.push_back(-1);
            ur.push_back(-1);
            dl.push_back(-1);
            dr.push_back(-1);
        }
        ul[x] = tr.size() - 4;
        ur[x] = tr.size() - 3;
        dl[x] = tr.size() - 2;
        dr[x] = tr.size() - 1;
    }

    void update(ll x, ll lx, ll rx, ll ly, ll ry, ll X, ll Y, ll val) {
        if (lx == rx && ly == ry) {
            tr[x] = val;
            return;
        }
        if (ur[x] == -1) {
            extend(x);
        }
        ll midx = (rx + lx) / 2;
        ll midy = (ry + ly) / 2;
        if (X <= midx) {
            if (Y <= midy) {
                update(ul[x], lx, midx, ly, midy, X, Y, val);
            }
            else {
                update(ur[x], lx, midx, midy + 1, ry, X, Y, val);
            }
        }
        else {
            if (Y <= midy) {
                update(dl[x], midx + 1, rx, ly, midy, X, Y, val);
            }
            else {
                update(dr[x], midx + 1, rx, midy + 1, ry, X, Y, val);
            }
        }
        tr[x] = gcd(gcd(tr[ul[x]], tr[ur[x]]), gcd(tr[dl[x]], tr[dr[x]]));
    }

    ll query(ll x, ll lx, ll rx, ll ly, ll ry, ll LX, ll RX, ll LY, ll RY) {
        if (tr[x] == 0) {
            return 0;
        }
        if (rx < lx) {
            return 0;
        }
        if (rx < LX) {
            return 0;
        }
        if (RX < lx) {
            return 0;
        }
        if (RX < LX) {
            return 0;
        }
        if (ry < ly) {
            return 0;
        }
        if (ry < LY) {
            return 0;
        }
        if (RY < ly) {
            return 0;
        }
        if (RY < LY) {
            return 0;
        }
        if (LX <= lx && rx <= RX && LY <= ly && ry <= RY) {
            return tr[x];
        }
        if (ur[x] == -1) {
            extend(x);
        }
        ll midx = (rx + lx) / 2;
        ll midy = (ry + ly) / 2;
        return gcd(
                    gcd(query(ul[x], lx, midx,     ly, midy, LX, RX, LY, RY), query(ur[x], lx, midx,     midy + 1, ry, LX, RX, LY, RY)), 
                    gcd(query(dl[x], midx + 1, rx, ly, midy, LX, RX, LY, RY), query(dr[x], midx + 1, rx, midy + 1, ry, 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, 0, m, P, Q, K);
    // cout << P << ' ' << Q << ' ' << K << endl;
}

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

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