oj.uz

Submission #1075516

# Submission time Handle Problem Language Result Execution time Memory
1075516 2024-08-26T07:17:31 Z Ignut Game (IOI13_game) C++17
0 / 100
 1 ms 1628 KB 
// 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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 1624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 1628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 1628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 1628 KB Output isn't correct
3 Halted 0 ms 0 KB -