oj.uz

Submission #920599

# Submission time Handle Problem Language Result Execution time Memory
920599 2024-02-02T18:45:47 Z Macker Game (IOI13_game) C++17
63 / 100
 1448 ms 138700 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

vector<vector<ll>> st;
int lenx = 1, leny = 1;

ll comb(ll a, ll b){
    if(!a) return b;
    if(!b) return a;
    return gcd2(a, b);
}

ll qry_y(int l, int r, int ix, int i = 1, int s = 0, int e = leny){
    if(l >= e || r <= s) return 0;
    if(l <= s && e <= r){
        return st[ix][i];
    }
    return comb(qry_y(l, r, ix, i * 2, s, (s + e) / 2),
            qry_y(l, r, ix, i * 2 + 1, (s + e) / 2, e));
}

ll qry_x(int l, int ly, int r, int ry, int i = 1, int s = 0, int e = lenx){
    if(l >= e || r <= s) return 0;
    if(l <= s && e <= r){
        return qry_y(ly, ry, i);
    }
    return comb(qry_x(l, ly, r, ry, i * 2, s, (s + e) / 2),
             qry_x(l, ly, r, ry, i * 2 + 1, (s + e) / 2, e));
}

void upd_y(int x, int y, ll val, bool b, int ix, int i = 1, int s = 0, int e = leny){
    if(y >= e || y < s) return;
    if(y == s && s + 1 == e){
        if(b) st[ix][i] = val;
        else st[ix][i] = comb(st[ix * 2][i], st[ix * 2 + 1][i]);
        return;
    }
    upd_y(x, y, val, b, ix, i * 2, s, (s + e) / 2);
    upd_y(x, y, val, b, ix, i * 2 + 1, (s + e) / 2, e);
    st[ix][i] = comb(st[ix][i * 2], st[ix][i * 2 + 1]);
}

void upd_x(int x, int y, ll val, int i = 1, int s = 0, int e = lenx){
    if(x >= e || x < s) return;
    if(x == s && s + 1 == e) {
        upd_y(x, y, val, true, i);
        return;
    }
    upd_x(x, y, val, i * 2, s, (s + e) / 2);
    upd_x(x, y, val, i * 2 + 1, (s + e) / 2, e);
    upd_y(x, y, val, false, i);
}

void init(int R, int C) {
    while(lenx < R) lenx *= 2;
    while(leny < C) leny *= 2;
    st.resize(2 * lenx, vector<ll>(2 * leny, 0));
}

void update(int P, int Q, long long K) {
    upd_x(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return qry_x(P, Q, U + 1, V + 1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 436 ms 74652 KB Output is correct
5 Correct 345 ms 74312 KB Output is correct
6 Correct 538 ms 72180 KB Output is correct
7 Correct 527 ms 71628 KB Output is correct
8 Correct 416 ms 72008 KB Output is correct
9 Correct 494 ms 71756 KB Output is correct
10 Correct 457 ms 71340 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 952 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 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 700 ms 41300 KB Output is correct
13 Correct 996 ms 38140 KB Output is correct
14 Correct 545 ms 137068 KB Output is correct
15 Correct 1261 ms 136148 KB Output is correct
16 Correct 295 ms 136784 KB Output is correct
17 Correct 1316 ms 138176 KB Output is correct
18 Correct 1448 ms 138700 KB Output is correct
19 Correct 1364 ms 138652 KB Output is correct
20 Correct 1334 ms 137608 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 423 ms 74460 KB Output is correct
13 Correct 362 ms 73908 KB Output is correct
14 Correct 507 ms 72084 KB Output is correct
15 Correct 556 ms 71632 KB Output is correct
16 Correct 435 ms 71864 KB Output is correct
17 Correct 512 ms 71744 KB Output is correct
18 Correct 448 ms 71236 KB Output is correct
19 Correct 760 ms 41324 KB Output is correct
20 Correct 999 ms 37940 KB Output is correct
21 Correct 600 ms 136060 KB Output is correct
22 Correct 1191 ms 137128 KB Output is correct
23 Correct 294 ms 136648 KB Output is correct
24 Correct 1239 ms 138372 KB Output is correct
25 Correct 1437 ms 138368 KB Output is correct
26 Correct 1364 ms 138180 KB Output is correct
27 Correct 1337 ms 137960 KB Output is correct
28 Runtime error 2 ms 600 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 948 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 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 442 ms 74748 KB Output is correct
13 Correct 339 ms 74392 KB Output is correct
14 Correct 524 ms 71752 KB Output is correct
15 Correct 497 ms 71576 KB Output is correct
16 Correct 457 ms 72120 KB Output is correct
17 Correct 511 ms 71688 KB Output is correct
18 Correct 466 ms 71152 KB Output is correct
19 Correct 706 ms 41556 KB Output is correct
20 Correct 997 ms 38048 KB Output is correct
21 Correct 580 ms 136984 KB Output is correct
22 Correct 1227 ms 136968 KB Output is correct
23 Correct 294 ms 136784 KB Output is correct
24 Correct 1229 ms 138040 KB Output is correct
25 Correct 1392 ms 138140 KB Output is correct
26 Correct 1382 ms 138320 KB Output is correct
27 Correct 1228 ms 137960 KB Output is correct
28 Runtime error 2 ms 612 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -