oj.uz

Submission #1075623

# Submission time Handle Problem Language Result Execution time Memory
1075623 2024-08-26T08:02:44 Z Ignut Game (IOI13_game) C++17
37 / 100
 860 ms 256000 KB 
// 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 1652 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 1884 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 1 ms 1880 KB Output is correct
12 Correct 1 ms 600 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 464 ms 134436 KB Output is correct
5 Correct 351 ms 134224 KB Output is correct
6 Correct 436 ms 131664 KB Output is correct
7 Correct 454 ms 131408 KB Output is correct
8 Correct 366 ms 131664 KB Output is correct
9 Correct 415 ms 131376 KB Output is correct
10 Correct 362 ms 130896 KB Output is correct
11 Correct 1 ms 604 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 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1648 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 1884 KB Output is correct
10 Correct 1 ms 1672 KB Output is correct
11 Correct 1 ms 1884 KB Output is correct
12 Correct 702 ms 134228 KB Output is correct
13 Correct 832 ms 130388 KB Output is correct
14 Runtime error 107 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 0 ms 604 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 1884 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 1 ms 1884 KB Output is correct
12 Correct 512 ms 134228 KB Output is correct
13 Correct 383 ms 134016 KB Output is correct
14 Correct 416 ms 131620 KB Output is correct
15 Correct 408 ms 131408 KB Output is correct
16 Correct 376 ms 131664 KB Output is correct
17 Correct 426 ms 131420 KB Output is correct
18 Correct 406 ms 130924 KB Output is correct
19 Correct 706 ms 134024 KB Output is correct
20 Correct 860 ms 130560 KB Output is correct
21 Runtime error 111 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 604 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 628 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 1656 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 1 ms 1884 KB Output is correct
12 Correct 541 ms 134436 KB Output is correct
13 Correct 383 ms 134224 KB Output is correct
14 Correct 477 ms 131544 KB Output is correct
15 Correct 436 ms 131668 KB Output is correct
16 Correct 502 ms 131664 KB Output is correct
17 Correct 430 ms 131412 KB Output is correct
18 Correct 403 ms 131032 KB Output is correct
19 Correct 724 ms 134012 KB Output is correct
20 Correct 850 ms 130412 KB Output is correct
21 Runtime error 125 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -