oj.uz

Submission #580103

# Submission time Handle Problem Language Result Execution time Memory
580103 2022-06-20T15:17:50 Z MohamedFaresNebili Game (IOI13_game) C++14
100 / 100
 3024 ms 82088 KB 
#include <bits/stdc++.h>
#include "game.h"
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        int R, C;
        struct X{
            X *lf, *rf; int l, r; ll res;
            X(int s, int e): l(s), r(e), lf(nullptr), rf(nullptr), res(0ll) {}
        };
        struct Y{
            Y *lf, *rf; X node;
            Y(): lf(nullptr), rf(nullptr), node(0, C - 1) {}
        };

        ll op(ll A, ll B) {
            return __gcd(A, B);
        }
        void update(X *v, int p, ll k) {
            int l = v -> l, r = v -> r;
            if(l == r) {
                v -> res = k;
                return;
            }
            int md = (l + r) / 2;
            X **to = &(p <= md ? v -> lf : v -> rf);
            if(!*to) {
                *to = new X(p, p);
                (*to) -> res = k;
            }
            else if((*to) -> l <= p && (*to) -> r >= p)
                update(*to, p, k);
            else {
                while((p <= md) == ((*to) -> l <= md)) {
                    if(p <= md) r = md;
                    else l = md + 1;
                    md = (l + r) / 2;
                }
                X *node = new X(l, r);
                if((*to) -> r <= md) node -> lf = *to;
                else node -> rf = *to;
                *to = node;
                update(*to, p, k);
            }
            v -> res = op(v -> lf ? v -> lf -> res : 0,
                          v -> rf ? v -> rf -> res : 0);
        }

        ll query(X *v, int l, int r) {
            if(!v || v -> l > r || v -> r < l) return 0ll;
            if(v -> l >= l && v -> r <= r) return v -> res;
            return op(query(v -> lf, l, r), query(v -> rf, l, r));
        }

        void update(Y *v, int l, int r, int x, int y, ll k) {
            int md = (l + r) / 2;
            if(l == r) {
                update(&v -> node, y, k);
                return;
            }
            if(x <= md) {
                if(!v -> lf) v -> lf = new Y();
                update(v -> lf, l, md, x, y, k);
            }
            else {
                if(!v -> rf) v -> rf = new Y();
                update(v -> rf, md + 1, r, x, y, k);
            }
            ll curr = op(
                v -> lf ? query(&v -> lf -> node, y, y) : 0,
                v -> rf ? query(&v -> rf -> node, y, y) : 0);
            update(&v -> node, y, curr);
        }

        ll query(Y* V, int l, int r, int p, int q, int u, int v) {
            if(!V || l > u || r < p) return 0;
            if(l >= p && r <= u) return query(&V -> node, q, v);
            int md = (l + r) / 2;
            return op(query(V -> lf, l, md, p, q, u, v),
                      query(V -> rf, md + 1, r, p, q, u, v));
        }

        Y* root;
        void init(int N, int M) {
            R = N, C = M;
            root = new Y();
        }
        void update(int P, int Q, ll K) {
            update(root, 0, R - 1, P, Q, K);
        }
        ll calculate(int P, int Q, int U, int V) {
            return query(root, 0, R - 1, P, Q, U, V);
        }

Compilation message

game.cpp: In constructor 'X::X(int, int)':
game.cpp:21:32: warning: 'X::r' will be initialized after [-Wreorder]
   21 |             X *lf, *rf; int l, r; ll res;
      |                                ^
game.cpp:21:16: warning:   'X* X::lf' [-Wreorder]
   21 |             X *lf, *rf; int l, r; ll res;
      |                ^~
game.cpp:22:13: warning:   when initialized here [-Wreorder]
   22 |             X(int s, int e): l(s), r(e), lf(nullptr), rf(nullptr), res(0ll) {}
      |             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 427 ms 8432 KB Output is correct
5 Correct 319 ms 8648 KB Output is correct
6 Correct 382 ms 5372 KB Output is correct
7 Correct 435 ms 5096 KB Output is correct
8 Correct 280 ms 3788 KB Output is correct
9 Correct 405 ms 5420 KB Output is correct
10 Correct 369 ms 4840 KB Output is correct
11 Correct 0 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 706 ms 11552 KB Output is correct
13 Correct 1272 ms 5024 KB Output is correct
14 Correct 225 ms 908 KB Output is correct
15 Correct 1442 ms 6188 KB Output is correct
16 Correct 180 ms 9840 KB Output is correct
17 Correct 595 ms 6148 KB Output is correct
18 Correct 1130 ms 10300 KB Output is correct
19 Correct 979 ms 10452 KB Output is correct
20 Correct 867 ms 9760 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 451 ms 8292 KB Output is correct
13 Correct 311 ms 8664 KB Output is correct
14 Correct 367 ms 5456 KB Output is correct
15 Correct 436 ms 5044 KB Output is correct
16 Correct 282 ms 3812 KB Output is correct
17 Correct 392 ms 5156 KB Output is correct
18 Correct 370 ms 4944 KB Output is correct
19 Correct 691 ms 11484 KB Output is correct
20 Correct 1284 ms 4956 KB Output is correct
21 Correct 218 ms 852 KB Output is correct
22 Correct 1418 ms 6152 KB Output is correct
23 Correct 186 ms 9884 KB Output is correct
24 Correct 555 ms 6104 KB Output is correct
25 Correct 1059 ms 10372 KB Output is correct
26 Correct 855 ms 10300 KB Output is correct
27 Correct 764 ms 9668 KB Output is correct
28 Correct 395 ms 43240 KB Output is correct
29 Correct 1075 ms 45384 KB Output is correct
30 Correct 2019 ms 35108 KB Output is correct
31 Correct 1862 ms 28532 KB Output is correct
32 Correct 327 ms 10188 KB Output is correct
33 Correct 403 ms 10700 KB Output is correct
34 Correct 242 ms 39116 KB Output is correct
35 Correct 763 ms 26848 KB Output is correct
36 Correct 1661 ms 43296 KB Output is correct
37 Correct 1285 ms 43320 KB Output is correct
38 Correct 1244 ms 43000 KB Output is correct
39 Correct 1022 ms 35796 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 425 ms 8348 KB Output is correct
13 Correct 318 ms 8548 KB Output is correct
14 Correct 361 ms 5420 KB Output is correct
15 Correct 451 ms 5084 KB Output is correct
16 Correct 281 ms 3872 KB Output is correct
17 Correct 400 ms 5216 KB Output is correct
18 Correct 364 ms 4812 KB Output is correct
19 Correct 710 ms 11576 KB Output is correct
20 Correct 1300 ms 5084 KB Output is correct
21 Correct 219 ms 844 KB Output is correct
22 Correct 1445 ms 6180 KB Output is correct
23 Correct 185 ms 9896 KB Output is correct
24 Correct 586 ms 6252 KB Output is correct
25 Correct 1082 ms 10316 KB Output is correct
26 Correct 916 ms 10280 KB Output is correct
27 Correct 817 ms 9748 KB Output is correct
28 Correct 404 ms 43268 KB Output is correct
29 Correct 1117 ms 45344 KB Output is correct
30 Correct 2089 ms 35140 KB Output is correct
31 Correct 1819 ms 28580 KB Output is correct
32 Correct 325 ms 10400 KB Output is correct
33 Correct 406 ms 10644 KB Output is correct
34 Correct 242 ms 39100 KB Output is correct
35 Correct 815 ms 26880 KB Output is correct
36 Correct 1838 ms 43260 KB Output is correct
37 Correct 1315 ms 43532 KB Output is correct
38 Correct 1205 ms 42820 KB Output is correct
39 Correct 586 ms 80988 KB Output is correct
40 Correct 1971 ms 82088 KB Output is correct
41 Correct 3024 ms 67408 KB Output is correct
42 Correct 2678 ms 52480 KB Output is correct
43 Correct 453 ms 76740 KB Output is correct
44 Correct 389 ms 10952 KB Output is correct
45 Correct 1061 ms 35600 KB Output is correct
46 Correct 2215 ms 81032 KB Output is correct
47 Correct 2255 ms 81004 KB Output is correct
48 Correct 2282 ms 80652 KB Output is correct
49 Correct 1 ms 212 KB Output is correct