oj.uz

Submission #790475

# Submission time Handle Problem Language Result Execution time Memory
790475 2023-07-22T17:10:44 Z Valaki2 Game (IOI13_game) C++14
63 / 100
 5326 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define ll long long
#define pb push_back

#define __gcd gcd2

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;
}

int n, m;

unordered_map<ll, unordered_map<ll, ll> > tree;

vector<int> idcs;
void upd(int vx, int vy, int vlx, int vrx, int vly, int vry, int x, int y, ll val) {
    if(vlx == vrx) {
        if(vly == vry) {
            idcs.pb(vy);
            tree[vx][vy] = val;
            return;
        }
        idcs.pb(vy);
        int mid = (vly + vry) / 2;
        if(y <= mid) {
            upd(vx, 2 * vy, vlx, vrx, vly, mid, x, y, val);
        } else {
            upd(vx, 2 * vy + 1, vlx, vrx, mid + 1, vry, x, y, val);
        }
        tree[vx][vy] = __gcd(tree[vx][2 * vy], tree[vx][2 * vy + 1]);
        return;
    }
    int mid = (vlx + vrx) / 2;
    if(x <= mid) {
        upd(2 * vx, vy, vlx, mid, vly, vry, x, y, val);
    } else {
        upd(2 * vx + 1, vy, mid + 1, vrx, vly, vry, x, y, val);
    }
    for(int idx : idcs) {
        tree[vx][idx] = __gcd(tree[2 * vx][idx], tree[2 * vx + 1][idx]);
    }
}

ll que(int vx, int vy, int vlx, int vrx, int vly, int vry, int qlx, int qrx, int qly, int qry) {
    if(vlx == qlx && vrx == qrx) {
        if(vly == qly && vry == qry) {
            return tree[vx][vy];
        }
        if(vly > qry || vry < qly) {
            return 0ll;
        }
        int mid = (vly + vry) / 2;
        return __gcd(que(vx, 2 * vy, vlx, vrx, vly, mid, qlx, qrx, qly, min(qry, mid)), 
                    que(vx, 2 * vy + 1, vlx, vrx, mid + 1, vry, qlx, qrx, max(qly, mid + 1), qry));
    }
    if(vlx > qrx || vrx < qlx) {
        return 0ll;
    }
    int mid = (vlx + vrx) / 2;
    return __gcd(que(2 * vx, vy, vlx, mid, vly, vry, qlx, min(qrx, mid), qly, qry), 
                que(2 * vx + 1, vy, mid + 1, vrx, vly, vry, max(qlx, mid + 1), qrx, qly, qry));
}

void init(signed R, signed C) {
    n = R, m = C;
    //
}

void update(signed P, signed Q, ll K) {
    P++, Q++;
    int x = P, y = Q;
    ll val = K;
    idcs.clear();
    upd(1, 1, 1, n, 1, m, x, y, val);
}

ll calculate(signed P, signed Q, signed U, signed V) {
    P++, Q++, U++, V++;
    int a = P, b = Q, c = U, d = V;
    ll res = 0;
    res = que(1, 1, 1, n, 1, m, a, c, b, d);
    return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 552 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1381 ms 30004 KB Output is correct
5 Correct 908 ms 26060 KB Output is correct
6 Correct 1590 ms 65692 KB Output is correct
7 Correct 1611 ms 65396 KB Output is correct
8 Correct 1375 ms 62516 KB Output is correct
9 Correct 1688 ms 66592 KB Output is correct
10 Correct 1691 ms 65180 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1922 ms 32320 KB Output is correct
13 Correct 2058 ms 12704 KB Output is correct
14 Correct 1300 ms 2400 KB Output is correct
15 Correct 2546 ms 19716 KB Output is correct
16 Correct 462 ms 43764 KB Output is correct
17 Correct 4609 ms 171296 KB Output is correct
18 Correct 5212 ms 183364 KB Output is correct
19 Correct 5297 ms 183300 KB Output is correct
20 Correct 5189 ms 182564 KB Output is correct
21 Correct 1 ms 308 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1372 ms 29932 KB Output is correct
13 Correct 935 ms 26160 KB Output is correct
14 Correct 1646 ms 65976 KB Output is correct
15 Correct 1607 ms 65528 KB Output is correct
16 Correct 1415 ms 62672 KB Output is correct
17 Correct 1699 ms 66696 KB Output is correct
18 Correct 1686 ms 65332 KB Output is correct
19 Correct 1943 ms 31860 KB Output is correct
20 Correct 2044 ms 12804 KB Output is correct
21 Correct 1303 ms 2508 KB Output is correct
22 Correct 2557 ms 19588 KB Output is correct
23 Correct 404 ms 43792 KB Output is correct
24 Correct 4681 ms 171116 KB Output is correct
25 Correct 5326 ms 188460 KB Output is correct
26 Correct 5326 ms 188436 KB Output is correct
27 Correct 5275 ms 187628 KB Output is correct
28 Runtime error 879 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1386 ms 29564 KB Output is correct
13 Correct 914 ms 25900 KB Output is correct
14 Correct 1557 ms 65580 KB Output is correct
15 Correct 1622 ms 65324 KB Output is correct
16 Correct 1376 ms 62420 KB Output is correct
17 Correct 1675 ms 66448 KB Output is correct
18 Correct 1651 ms 65188 KB Output is correct
19 Correct 1894 ms 31692 KB Output is correct
20 Correct 2052 ms 12572 KB Output is correct
21 Correct 1286 ms 2168 KB Output is correct
22 Correct 2601 ms 19484 KB Output is correct
23 Correct 395 ms 43432 KB Output is correct
24 Correct 4608 ms 171212 KB Output is correct
25 Correct 5307 ms 188504 KB Output is correct
26 Correct 5281 ms 188392 KB Output is correct
27 Correct 5206 ms 187676 KB Output is correct
28 Runtime error 898 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -