Submission #1075516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075516		Ignut	Game (IOI13_game)	C++17	0 / 100	1 ms	1628 KiB

game

// Ignut

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

using namespace std;
using ll = long long;

vector<vector<ll>> t;

int r, c;

void init(int R, int C) {
    r = R, c = C;
    t.assign(4 * R, {});
    for (int i = 0; i < 4 * R; i ++) t[i].assign(4 * C, 0);
}

void Change(int ind, int v, int l, int r, int pos, ll val) {
    if (l == r) {
        t[ind][v] = val;
        return;
    }
    int mid = l + (r - l) / 2;
    if (pos <= mid)
        Change(ind, v * 2, l, mid, pos, val);
    else
        Change(ind, v * 2 + 1, mid + 1, r, pos, val);
    t[ind][v] = gcd(t[ind][v * 2], t[ind][v * 2 + 1]);
}

void ChangeR(int v, int l, int r, int posR, int posC, ll val) {
    Change(v, 1, 0, c - 1, posC, val);
    if (l == r)
        return;
    int mid = l + (r - l) / 2;
    if (posR <= mid)
        ChangeR(v * 2, l, mid, posR, posC, val);
    else
        ChangeR(v * 2 + 1, mid + 1, r, posR, posC, val);
}

void update(int P, int Q, ll K) {
    ChangeR(1, 0, r - 1, P, Q, K);
    // Change(P, 1, 0, c - 1, Q, K);
}

ll Ask(int ind, int v, int l, int r, int ql, int qr) {
    if (ql > r || l > qr)
        return 0ll;
    if (l >= ql && r <= qr)
        return t[ind][v];
    int mid = l + (r - l) / 2;
    return gcd(Ask(ind, v * 2, l, mid, ql, qr), Ask(ind, v * 2 + 1, mid + 1, r, ql, qr));
}

ll AskR(int v, int l, int r, int ql_r, int qr_r, int ql_c, int qr_c) {
    if (l > qr_r || ql_r > r)
        return 0;
    if (l >= ql_r && r <= qr_r)
        return Ask(v, 1, 0, c - 1, ql_c, qr_c);
    int mid = l + (r - l) / 2;
    return gcd(AskR(v * 2, l, mid, ql_r, qr_r, ql_c, qr_c), AskR(v * 2 + 1, mid + 1, r, ql_r, qr_r, ql_c, qr_c));
}

ll calculate(int P, int Q, int U, int V) {
    // ll res = 0;
    // for (int ind = P; ind <= U; ind ++)
    //     res = gcd(res, Ask(ind, 1, 0, c - 1, Q, V));
    // return res;
    return AskR(1, 0, r - 1, P, U, Q, V);
}

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