oj.uz

Submission #675465

# Submission time Handle Problem Language Result Execution time Memory
675465 2022-12-27T10:05:48 Z tae826 Game (IOI13_game) C++17
100 / 100
 3515 ms 210040 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int gapcnt, R, C;
#pragma pack(4)
struct YNode {
    ll gap;
    int lf = -1, rg = -1, lazy = -1;
} gap[10010010];

inline ll _gcd(ll x, ll y) { if(x == 0 || y == 0) return x+y; return __gcd(x, y); }

ll queryY(int now, int s, int e, int si, int ei) {
    if(s > ei || e < si) return 0;
    if(gap[now].lazy > 0) {
        if(gap[now].lazy >= si && gap[now].lazy <= ei) return gap[now].gap;
        else return 0;
    }
    if(s >= si && e <= ei) return gap[now].gap;
    ll lv = 0, rv = 0, ret = 0, m = s+e>>1;
    if(gap[now].lf != -1) lv = queryY(gap[now].lf, s, m, si, ei);
    if(gap[now].rg != -1) rv = queryY(gap[now].rg, m+1, e, si, ei);
    return _gcd(ret, _gcd(lv, rv));
}

ll queryX(int n, int s, int e, int si, int ei, int ssi, int eei) {
    if(s > ei || e < si) return 0;
    if(s >= si && e <= ei) return queryY(gap[n].lazy, 1, C, ssi, eei);
    ll lv = 0, rv = 0, m = s+e>>1;
    if(gap[n].lf != -1) lv = queryX(gap[n].lf, s, m, si, ei, ssi, eei);
    if(gap[n].rg != -1) rv = queryX(gap[n].rg, m+1, e, si, ei, ssi, eei);
    return _gcd(lv, rv);
}

void updateY(int now, int s, int e, int si, int ei, ll v) {
    if(s > ei || e < si) return;
    if(s >= si && e <= ei) { gap[now].gap = v; return; }
    if(gap[now].lazy == -1) {
        gap[now].lazy = si; gap[now].gap = v; return;
    } else {
        int m = s+e>>1;
        if(gap[now].lazy != -2) {
            if(gap[now].lazy <= m) {
                if(gap[now].lf == -1) gap[now].lf = gapcnt++;
                updateY(gap[now].lf, s, m, gap[now].lazy, gap[now].lazy, gap[now].gap);
            } else {
                if(gap[now].rg == -1) gap[now].rg = gapcnt++;
                updateY(gap[now].rg, m+1, e, gap[now].lazy, gap[now].lazy, gap[now].gap);
            }
        }

        if(si <= m) {
            if(gap[now].lf == -1) gap[now].lf = gapcnt++;
            updateY(gap[now].lf, s, m, si, ei, v);
        } else {
            if(gap[now].rg == -1) gap[now].rg = gapcnt++;
            updateY(gap[now].rg, m+1, e, si, ei, v);
        }

        ll lv = gap[now].lf == -1 ? 0 : gap[gap[now].lf].gap, rv = gap[now].rg == -1 ? 0 : gap[gap[now].rg].gap;
        gap[now].gap = _gcd(lv, rv);
        gap[now].lazy = -2;
    }
}

void updateX(int now, int s, int e, int si, int ei, int v, ll z) {
    if(s > ei || e < si) return;
    if(gap[now].lazy < 0) gap[now].lazy = gapcnt++;
    if(s >= si && e <= ei) { updateY(gap[now].lazy, 1, C, v, v, z); return; }
    int m = s+e>>1;
    if(si <= m) {
        if(gap[now].lf == -1) gap[now].lf = gapcnt++;
        updateX(gap[now].lf, s, m, si, ei, v, z);
    } else {
        if(gap[now].rg == -1) gap[now].rg = gapcnt++;
        updateX(gap[now].rg, m+1, e, si, ei, v, z);
    }
    ll lv = gap[now].lf < 0 ? 0 : queryY(gap[gap[now].lf].lazy, 1, C, v, v),
        rv = gap[now].rg < 0 ? 0 : queryY(gap[gap[now].rg].lazy, 1, C, v, v);
    updateY(gap[now].lazy, 1, C, v, v, _gcd(lv, rv));
}

void init(int _R, int _C) {
    gapcnt = 1; R = _R, C = _C;
}
void update(int P, int Q, ll K) {
    ++P; ++Q;
    updateX(0, 1, R, P, P, Q, K);
    if(gapcnt > 10000000) exit(1);
}

ll calculate(int P, int Q, int U, int V) {
    ++P; ++Q; ++U; ++V;
    return queryX(0, 1, R, P, U, Q, V);
}

Compilation message

game.cpp: In function 'll queryY(int, int, int, int, int)':
game.cpp:22:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     ll lv = 0, rv = 0, ret = 0, m = s+e>>1;
      |                                     ~^~
game.cpp: In function 'll queryX(int, int, int, int, int, int, int)':
game.cpp:31:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     ll lv = 0, rv = 0, m = s+e>>1;
      |                            ~^~
game.cpp: In function 'void updateY(int, int, int, int, int, ll)':
game.cpp:43:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int m = s+e>>1;
      |                 ~^~
game.cpp: In function 'void updateX(int, int, int, int, int, int, ll)':
game.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int m = s+e>>1;
      |             ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 196092 KB Output is correct
2 Correct 75 ms 196096 KB Output is correct
3 Correct 83 ms 196100 KB Output is correct
4 Correct 77 ms 196124 KB Output is correct
5 Correct 87 ms 196080 KB Output is correct
6 Correct 76 ms 196192 KB Output is correct
7 Correct 78 ms 196172 KB Output is correct
8 Correct 76 ms 196108 KB Output is correct
9 Correct 75 ms 196156 KB Output is correct
10 Correct 77 ms 196132 KB Output is correct
11 Correct 84 ms 196128 KB Output is correct
12 Correct 77 ms 196076 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 196172 KB Output is correct
2 Correct 83 ms 196080 KB Output is correct
3 Correct 76 ms 196088 KB Output is correct
4 Correct 542 ms 204712 KB Output is correct
5 Correct 383 ms 204464 KB Output is correct
6 Correct 409 ms 201828 KB Output is correct
7 Correct 432 ms 201556 KB Output is correct
8 Correct 335 ms 201996 KB Output is correct
9 Correct 428 ms 201752 KB Output is correct
10 Correct 398 ms 201352 KB Output is correct
11 Correct 76 ms 196052 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 196288 KB Output is correct
2 Correct 76 ms 196172 KB Output is correct
3 Correct 77 ms 196124 KB Output is correct
4 Correct 76 ms 196212 KB Output is correct
5 Correct 79 ms 196172 KB Output is correct
6 Correct 80 ms 196172 KB Output is correct
7 Correct 80 ms 196080 KB Output is correct
8 Correct 79 ms 196088 KB Output is correct
9 Correct 81 ms 196084 KB Output is correct
10 Correct 76 ms 196076 KB Output is correct
11 Correct 77 ms 196128 KB Output is correct
12 Correct 765 ms 204420 KB Output is correct
13 Correct 1320 ms 200808 KB Output is correct
14 Correct 316 ms 201292 KB Output is correct
15 Correct 1496 ms 201400 KB Output is correct
16 Correct 232 ms 201112 KB Output is correct
17 Correct 598 ms 202328 KB Output is correct
18 Correct 851 ms 202472 KB Output is correct
19 Correct 781 ms 202680 KB Output is correct
20 Correct 703 ms 202160 KB Output is correct
21 Correct 77 ms 196172 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196076 KB Output is correct
2 Correct 77 ms 196120 KB Output is correct
3 Correct 74 ms 196164 KB Output is correct
4 Correct 77 ms 196124 KB Output is correct
5 Correct 78 ms 196064 KB Output is correct
6 Correct 76 ms 196076 KB Output is correct
7 Correct 78 ms 196172 KB Output is correct
8 Correct 78 ms 196072 KB Output is correct
9 Correct 81 ms 196152 KB Output is correct
10 Correct 78 ms 196120 KB Output is correct
11 Correct 79 ms 196108 KB Output is correct
12 Correct 487 ms 204532 KB Output is correct
13 Correct 388 ms 204464 KB Output is correct
14 Correct 412 ms 201928 KB Output is correct
15 Correct 434 ms 201520 KB Output is correct
16 Correct 343 ms 202048 KB Output is correct
17 Correct 431 ms 201664 KB Output is correct
18 Correct 394 ms 201304 KB Output is correct
19 Correct 754 ms 204472 KB Output is correct
20 Correct 1263 ms 200748 KB Output is correct
21 Correct 306 ms 201440 KB Output is correct
22 Correct 1486 ms 201432 KB Output is correct
23 Correct 245 ms 201024 KB Output is correct
24 Correct 617 ms 202248 KB Output is correct
25 Correct 890 ms 202488 KB Output is correct
26 Correct 853 ms 202732 KB Output is correct
27 Correct 752 ms 202148 KB Output is correct
28 Correct 430 ms 207296 KB Output is correct
29 Correct 991 ms 209864 KB Output is correct
30 Correct 2784 ms 203624 KB Output is correct
31 Correct 2625 ms 203816 KB Output is correct
32 Correct 497 ms 205884 KB Output is correct
33 Correct 641 ms 205820 KB Output is correct
34 Correct 273 ms 203588 KB Output is correct
35 Correct 693 ms 207280 KB Output is correct
36 Correct 1162 ms 207832 KB Output is correct
37 Correct 959 ms 208088 KB Output is correct
38 Correct 914 ms 207376 KB Output is correct
39 Correct 816 ms 207628 KB Output is correct
40 Correct 79 ms 196060 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 196136 KB Output is correct
2 Correct 79 ms 196044 KB Output is correct
3 Correct 89 ms 196144 KB Output is correct
4 Correct 80 ms 196056 KB Output is correct
5 Correct 79 ms 196244 KB Output is correct
6 Correct 81 ms 196148 KB Output is correct
7 Correct 79 ms 196172 KB Output is correct
8 Correct 78 ms 196064 KB Output is correct
9 Correct 79 ms 196104 KB Output is correct
10 Correct 79 ms 196172 KB Output is correct
11 Correct 79 ms 196104 KB Output is correct
12 Correct 504 ms 204520 KB Output is correct
13 Correct 385 ms 204392 KB Output is correct
14 Correct 412 ms 201812 KB Output is correct
15 Correct 443 ms 201588 KB Output is correct
16 Correct 338 ms 202068 KB Output is correct
17 Correct 432 ms 201708 KB Output is correct
18 Correct 393 ms 201372 KB Output is correct
19 Correct 759 ms 204344 KB Output is correct
20 Correct 1286 ms 200916 KB Output is correct
21 Correct 311 ms 201592 KB Output is correct
22 Correct 1479 ms 201324 KB Output is correct
23 Correct 243 ms 201164 KB Output is correct
24 Correct 599 ms 202264 KB Output is correct
25 Correct 874 ms 202524 KB Output is correct
26 Correct 779 ms 202628 KB Output is correct
27 Correct 707 ms 202064 KB Output is correct
28 Correct 430 ms 207268 KB Output is correct
29 Correct 1033 ms 210040 KB Output is correct
30 Correct 2783 ms 203960 KB Output is correct
31 Correct 2677 ms 203868 KB Output is correct
32 Correct 514 ms 205932 KB Output is correct
33 Correct 637 ms 205848 KB Output is correct
34 Correct 275 ms 203604 KB Output is correct
35 Correct 692 ms 207332 KB Output is correct
36 Correct 1231 ms 207868 KB Output is correct
37 Correct 996 ms 208004 KB Output is correct
38 Correct 982 ms 207500 KB Output is correct
39 Correct 580 ms 207308 KB Output is correct
40 Correct 1478 ms 209516 KB Output is correct
41 Correct 3515 ms 204252 KB Output is correct
42 Correct 3450 ms 204172 KB Output is correct
43 Correct 408 ms 204092 KB Output is correct
44 Correct 667 ms 206240 KB Output is correct
45 Correct 835 ms 207708 KB Output is correct
46 Correct 1609 ms 208192 KB Output is correct
47 Correct 1583 ms 208356 KB Output is correct
48 Correct 1500 ms 207932 KB Output is correct
49 Correct 82 ms 196064 KB Output is correct