Submission #1075623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075623		Ignut	Game (IOI13_game)	C++17	37 / 100	860 ms	256000 KiB

game

// Ignut
 
#include <bits/stdc++.h>
#include "game.h"
 
using namespace std;
using ll = long long;
 
vector<ll> t[8001];
 
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 Update(int ind, int v, int l, int r, int pos, ll val) {
    t[ind][v] = gcd(t[ind * 2][v], t[ind * 2 + 1][v]);
    if (l == r) {
        return;
    }
    int mid = l + (r - l) / 2;
    if (pos <= mid)
        Update(ind, v * 2, l, mid, pos, val);
    else
        Update(ind, v * 2 + 1, mid + 1, r, pos, val);
}
 
void ChangeR(int v, int l, int r, int posR, int posC, ll val) {
    // cout << "update ind=" << v << '\n'; 
    if (l == r) {
        Change(v, 1, 0, c - 1, posC, val);
        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);
    Update(v, 1, 0, c - 1, posC, val);
}
 
void update(int P, int Q, ll K) {
    ChangeR(1, 0, r - 1, P, 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) {
        // cout << "ask ind=" << v << '\n';
        // cout << "get " << Ask(v, 1, 0, c - 1, ql_c, qr_c) << '\n';
        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: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20