oj.uz

Submission #1075598

# Submission time Handle Problem Language Result Execution time Memory
1075598 2024-08-26T07:56:34 Z Ignut Game (IOI13_game) C++17
37 / 100
 911 ms 256000 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 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 544 ms 134224 KB Output is correct
5 Correct 397 ms 133880 KB Output is correct
6 Correct 472 ms 131412 KB Output is correct
7 Correct 449 ms 131168 KB Output is correct
8 Correct 392 ms 131536 KB Output is correct
9 Correct 474 ms 131412 KB Output is correct
10 Correct 439 ms 130988 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 1712 KB Output is correct
3 Correct 2 ms 1628 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 1704 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 740 ms 133948 KB Output is correct
13 Correct 911 ms 130332 KB Output is correct
14 Runtime error 111 ms 256000 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 2 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 539 ms 134228 KB Output is correct
13 Correct 354 ms 133832 KB Output is correct
14 Correct 471 ms 131400 KB Output is correct
15 Correct 417 ms 131224 KB Output is correct
16 Correct 359 ms 131412 KB Output is correct
17 Correct 416 ms 131152 KB Output is correct
18 Correct 393 ms 130940 KB Output is correct
19 Correct 679 ms 133972 KB Output is correct
20 Correct 830 ms 130476 KB Output is correct
21 Runtime error 107 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 1624 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1464 KB Output is correct
12 Correct 504 ms 134228 KB Output is correct
13 Correct 352 ms 133972 KB Output is correct
14 Correct 416 ms 131408 KB Output is correct
15 Correct 400 ms 131156 KB Output is correct
16 Correct 355 ms 131576 KB Output is correct
17 Correct 412 ms 131152 KB Output is correct
18 Correct 379 ms 130844 KB Output is correct
19 Correct 661 ms 134048 KB Output is correct
20 Correct 842 ms 130384 KB Output is correct
21 Runtime error 132 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -