oj.uz

Submission #485530

# Submission time Handle Problem Language Result Execution time Memory
485530 2021-11-08T04:30:45 Z DiTenix Game (IOI13_game) C++14
80 / 100
 3785 ms 256004 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
long long gcd(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Node {
    ll val;
    int lef, rig;
} a[maxn * 200];
#define lef(x) (a[x].lef)
#define rig(x) (a[x].rig)
#define val(x) (a[x].val)
#define Node int&
void comb(int x) {
    val(x) = gcd(val(lef(x)), val(rig(x)));
}
int new_node(ll v) {
    static int sz = 0;
    ++sz;
    return sz;
}
int root2d, R, C;
unordered_map<int, int> root;

void set1d(int l, int r, Node x, Node r1, Node r2, int k, ll v) {
    if (!x) x = new_node(0);
    if (l == r) {
        if (!r1 & !r2) {
            val(x) = v;
        } else {
            val(x) = gcd(val(r1), val(r2));
        }
    } else {
        int m = (l + r) >> 1;
        if (k <= m) set1d(l, m, lef(x), lef(r1), lef(r2), k, v);
        else set1d(m + 1, r, rig(x), rig(r1), rig(r2), k, v);
        comb(x);
    }
}

void set2d(int l, int r, Node x, int _x, int _y, ll v) {
    if (!x) x = new_node(0);
    if (l != r) {
        int m = (l + r) >> 1;
        if (_x <= m) set2d(l, m, lef(x), _x, _y, v);
        else set2d(m + 1, r, rig(x), _x, _y, v);
    }
    set1d(0, C - 1, root[x], root[lef(x)], root[rig(x)], _y, v);
}
ll qry1d(int l, int r, Node x, int L, int R) {
    // printf("qry1d %d %d %d\n", l, r, x);
    if (!x) return 0;
    if (l > R || r < L) return 0;
    if (l >= L && r <= R) return val(x);
    int m = (l + r) >> 1;
    return gcd(qry1d(l, m, lef(x), L, R), qry1d(m + 1, r, rig(x), L, R));
}
ll qry2d(int l, int r, Node x, int L, int R, int _L, int _R) {
    if (!x) return 0;
    if (l > R || r < L) return 0;
    // printf("qry2d %d %d %d %d %d\n", l, r, L, R, x);
    if (l >= L && r <= R) return qry1d(0, C - 1, root[x], _L, _R);
    int m = (l + r) >> 1;
    return gcd(qry2d(l, m, lef(x), L, R, _L, _R), qry2d(m + 1, r, rig(x), L, R, _L, _R));
}



void init(int R, int C) {
    ::R = R;
    ::C = C;
}

void update(int P, int Q, long long K) {
    set2d(0, R - 1, root2d, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    if (P > U) swap(P, U);
    if (Q > V) swap(Q, V);
    return qry2d(0, R - 1, root2d, P, U, Q, V);
}
/*
signed main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cin.tie(0)->sync_with_stdio(false);
    int m;
    cin >> R >> C >> m;
    // printf("%d %d %d\n", R, C, m);
    while (m--) {
        int op;
        cin >> op;
        // printf("%d\n", op);
        if (op == 1) {
            int x, y;
            ll v;
            cin >> x >> y >> v;
            modify(x, y, v);
        } else {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            if (x1 > x2) swap(x1, x2);
            if (y1 > y2) swap(y1, y2);
            ll res = qry(x1, x2, y1, y2);
            cout << res << "\n";
        }

    }
    // printf("%d %d\n", root2d, root[root2d]);
}*/
/*
1 1 64
2 0 0 0 0
2 0 0 0 0
2 0 0 0 0
1 0 0 5352072091165800
2 0 0 0 0
1 0 0 15571253006461152
1 0 0 36204425277916896
1 0 0 80686018200191040
1 0 0 720602986354563312
2 0 0 0 0
1 0 0 90705271009665312
2 0 0 0 0
1 0 0 583803309300971760
1 0 0 3317329660750560
2 0 0 0 0
2 0 0 0 0
2 0 0 0 0
1 0 0 84776821924066272
1 0 0 581927323100969664
1 0 0 93139161501610224
1 0 0 28340661117472704
1 0 0 74529074218959360
2 0 0 0 0
1 0 0 462419028676725120
1 0 0 4416867915235776
1 0 0 840475934823549024
1 0 0 8247617084266560
1 0 0 117571055091706944
1 0 0 839204903894797440
1 0 0 820805176764813240
1 0 0 82688722861897152
1 0 0 136422472061715840
1 0 0 555837014267982720
1 0 0 935087613488388360
1 0 0 17770822018565616
1 0 0 10726679222715456
1 0 0 621229604181863040
1 0 0 12477973789689408
2 0 0 0 0
1 0 0 227153207069268480
1 0 0 262037449583477568
1 0 0 562837835495871936
1 0 0 131875056326325312
1 0 0 922430858108760
1 0 0 763487168205041280
2 0 0 0 0
2 0 0 0 0
1 0 0 551850903114166656
1 0 0 243713152409807808
1 0 0 306811355534716032
1 0 0 115604757169181280
2 0 0 0 0
1 0 0 29254579698314880
1 0 0 35080064244441216
1 0 0 97819409912384160
1 0 0 34259332503876480
2 0 0 0 0
2 0 0 0 0
1 0 0 159548730492191040
1 0 0 11555364984947784
2 0 0 0 0
1 0 0 3373083100427040
2 0 0 0 0
2 0 0 0 0*/

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 462 ms 9500 KB Output is correct
5 Correct 328 ms 9824 KB Output is correct
6 Correct 397 ms 6608 KB Output is correct
7 Correct 417 ms 6512 KB Output is correct
8 Correct 294 ms 5316 KB Output is correct
9 Correct 386 ms 6484 KB Output is correct
10 Correct 360 ms 6084 KB Output is correct
11 Correct 0 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 810 ms 11412 KB Output is correct
13 Correct 1322 ms 4720 KB Output is correct
14 Correct 271 ms 1888 KB Output is correct
15 Correct 1657 ms 5968 KB Output is correct
16 Correct 188 ms 10816 KB Output is correct
17 Correct 719 ms 7648 KB Output is correct
18 Correct 1012 ms 11180 KB Output is correct
19 Correct 884 ms 11316 KB Output is correct
20 Correct 851 ms 10700 KB Output is correct
21 Correct 0 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 445 ms 9476 KB Output is correct
13 Correct 325 ms 9780 KB Output is correct
14 Correct 364 ms 6636 KB Output is correct
15 Correct 428 ms 6348 KB Output is correct
16 Correct 295 ms 5232 KB Output is correct
17 Correct 378 ms 6472 KB Output is correct
18 Correct 363 ms 6212 KB Output is correct
19 Correct 744 ms 11108 KB Output is correct
20 Correct 1264 ms 4760 KB Output is correct
21 Correct 267 ms 2140 KB Output is correct
22 Correct 1532 ms 5992 KB Output is correct
23 Correct 164 ms 10780 KB Output is correct
24 Correct 645 ms 7712 KB Output is correct
25 Correct 937 ms 11232 KB Output is correct
26 Correct 861 ms 11396 KB Output is correct
27 Correct 862 ms 10744 KB Output is correct
28 Correct 674 ms 135436 KB Output is correct
29 Correct 1437 ms 150676 KB Output is correct
30 Correct 3785 ms 107564 KB Output is correct
31 Correct 3557 ms 82120 KB Output is correct
32 Correct 487 ms 1904 KB Output is correct
33 Correct 613 ms 3252 KB Output is correct
34 Correct 385 ms 147436 KB Output is correct
35 Correct 1036 ms 75760 KB Output is correct
36 Correct 1977 ms 147952 KB Output is correct
37 Correct 1614 ms 148024 KB Output is correct
38 Correct 1582 ms 147608 KB Output is correct
39 Correct 1384 ms 113316 KB Output is correct
40 Correct 0 ms 204 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 438 ms 9120 KB Output is correct
13 Correct 312 ms 9412 KB Output is correct
14 Correct 357 ms 6336 KB Output is correct
15 Correct 386 ms 6000 KB Output is correct
16 Correct 279 ms 4928 KB Output is correct
17 Correct 376 ms 6092 KB Output is correct
18 Correct 350 ms 5680 KB Output is correct
19 Correct 748 ms 10820 KB Output is correct
20 Correct 1273 ms 4360 KB Output is correct
21 Correct 250 ms 1476 KB Output is correct
22 Correct 1521 ms 5752 KB Output is correct
23 Correct 163 ms 10396 KB Output is correct
24 Correct 693 ms 7240 KB Output is correct
25 Correct 964 ms 10692 KB Output is correct
26 Correct 837 ms 10948 KB Output is correct
27 Correct 828 ms 10456 KB Output is correct
28 Correct 655 ms 135276 KB Output is correct
29 Correct 1451 ms 150124 KB Output is correct
30 Correct 3763 ms 107016 KB Output is correct
31 Correct 3754 ms 81796 KB Output is correct
32 Correct 498 ms 1700 KB Output is correct
33 Correct 663 ms 3036 KB Output is correct
34 Correct 471 ms 147264 KB Output is correct
35 Correct 1091 ms 75512 KB Output is correct
36 Correct 2093 ms 147828 KB Output is correct
37 Correct 1798 ms 147748 KB Output is correct
38 Correct 1690 ms 147312 KB Output is correct
39 Runtime error 898 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -