Submission #1075504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075504		Ignut	Game (IOI13_game)	C++17	37 / 100	13102 ms	40092 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(R, {});
    for (int i = 0; i < 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 update(int P, int Q, ll 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 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;
}

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