oj.uz

Submission #706228

# Submission time Handle Problem Language Result Execution time Memory
706228 2023-03-06T06:56:02 Z sharaelong Game (IOI13_game) C++17
100 / 100
 4030 ms 102628 KB 
#include "game.h"
#include <bits/stdc++.h>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

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

struct Node1 {
    int n, ln, rn; // left node, right node
    Node1() : n(-1), ln(-1), rn(-1) {}
};

struct Node2 {
    int ln, rn, latest;
    ll val;
    Node2() : ln(-1), rn(-1), val(0), latest(-1) {}
};

int R, C;
vector<Node1> node1;
vector<Node2> node2;

int new_node1() {
    node1.push_back(Node1());
    return node1.size()-1;
}

int new_node2() {
    node2.push_back(Node2());
    return node2.size()-1;
}

void update2(int n, int nl, int nr, int y, ll v) {
    if (nl == nr) {
        node2[n].val = v;
        return;
    }

    int mid = (nl + nr) / 2;
    if (node2[n].latest != -1) {
        if (node2[n].latest <= mid) {
            node2[n].ln = new_node2();
            node2[node2[n].ln].latest = node2[n].latest;
            node2[node2[n].ln].val = node2[n].val;
        } else {
            node2[n].rn = new_node2();
            node2[node2[n].rn].latest = node2[n].latest;
            node2[node2[n].rn].val = node2[n].val;
        }
        node2[n].latest = -1;
    }
    
    if (y <= mid) {
        if (node2[n].ln == -1) {
            node2[n].ln = new_node2();
            node2[node2[n].ln].latest = y;
            node2[node2[n].ln].val = v;
        } else {
            update2(node2[n].ln, nl, mid, y, v);
        }
    } else {
        if (node2[n].rn == -1) {
            node2[n].rn = new_node2();
            node2[node2[n].rn].latest = y;
            node2[node2[n].rn].val = v;
        } else {
            update2(node2[n].rn, mid+1, nr, y, v);
        }
    }

    ll upd_gcd = 0;
    if (node2[n].ln != -1) upd_gcd = gcd2(upd_gcd, node2[node2[n].ln].val);
    if (node2[n].rn != -1) upd_gcd = gcd2(upd_gcd, node2[node2[n].rn].val);
    node2[n].val = upd_gcd;
}

ll query2(int n, int nl, int nr, int l, int r) {
    if (r < nl || nr < l) return 0;
    if (l <= nl && nr <= r) return node2[n].val;
    if (node2[n].latest != -1) {
        return (l <= node2[n].latest && node2[n].latest <= r ? node2[n].val : 0);
    }

    ll ret = 0;
    int mid = (nl + nr) / 2;
    if (node2[n].ln != -1) ret = gcd2(ret, query2(node2[n].ln, nl, mid, l, r));
    if (node2[n].rn != -1) ret = gcd2(ret, query2(node2[n].rn, mid+1, nr, l, r));
    return ret;
}

void update1(int n, int nl, int nr, int x, int y, ll v) {
    if (node1[n].n == -1) node1[n].n = new_node2();
    if (nl == nr) {
        update2(node1[n].n, 0, C-1, y, v);
        return;
    }

    int mid = (nl + nr) / 2;
    if (x <= mid) {
        if (node1[n].ln == -1) node1[n].ln = new_node1();
        update1(node1[n].ln, nl, mid, x, y, v);
    } else {
        if (node1[n].rn == -1) node1[n].rn = new_node1();
        update1(node1[n].rn, mid+1, nr, x, y, v);
    }

    ll upd_gcd = 0;
    if (node1[n].ln != -1) upd_gcd = gcd2(upd_gcd, query2(node1[node1[n].ln].n, 0, C-1, y, y));
    if (node1[n].rn != -1) upd_gcd = gcd2(upd_gcd, query2(node1[node1[n].rn].n, 0, C-1, y, y));
    update2(node1[n].n, 0, C-1, y, upd_gcd);
}

ll query1(int n, int nl, int nr, int x1, int y1, int x2, int y2) {
    if (nr < x1 || x2 < nl) return 0;
    if (x1 <= nl && nr <= x2) return (node1[n].n != -1 ? query2(node1[n].n, 0, C-1, y1, y2) : 0);

    ll ret = 0;
    int mid = (nl + nr) / 2;
    if (node1[n].ln != -1) ret = gcd2(ret, query1(node1[n].ln, nl, mid, x1, y1, x2, y2));
    if (node1[n].rn != -1) ret = gcd2(ret, query1(node1[n].rn, mid+1, nr, x1, y1, x2, y2));
    return ret;
}


int root;

void init(int _R, int _C) {
    R = _R;
    C = _C;
    root = new_node1();
}

void update(int P, int Q, ll K) {
    update1(root, 0, R-1, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return query1(root, 0, R-1, P, Q, U, V);
}

Compilation message

game.cpp: In constructor 'Node2::Node2()':
game.cpp:27:8: warning: 'Node2::val' will be initialized after [-Wreorder]
   27 |     ll val;
      |        ^~~
game.cpp:26:17: warning:   'int Node2::latest' [-Wreorder]
   26 |     int ln, rn, latest;
      |                 ^~~~~~
game.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     Node2() : ln(-1), rn(-1), val(0), latest(-1) {}
      |     ^~~~~

Subtask #1
10.0 / 10.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 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 296 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 340 KB Output is correct
12 Correct 1 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 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 397 ms 11372 KB Output is correct
5 Correct 300 ms 11064 KB Output is correct
6 Correct 348 ms 8568 KB Output is correct
7 Correct 376 ms 8264 KB Output is correct
8 Correct 264 ms 7492 KB Output is correct
9 Correct 359 ms 8372 KB Output is correct
10 Correct 330 ms 8100 KB Output is correct
11 Correct 1 ms 296 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 1 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 296 KB Output is correct
12 Correct 638 ms 12736 KB Output is correct
13 Correct 1134 ms 7808 KB Output is correct
14 Correct 244 ms 5588 KB Output is correct
15 Correct 1380 ms 9504 KB Output is correct
16 Correct 170 ms 10560 KB Output is correct
17 Correct 539 ms 9296 KB Output is correct
18 Correct 841 ms 11576 KB Output is correct
19 Correct 725 ms 11652 KB Output is correct
20 Correct 678 ms 11016 KB Output is correct
21 Correct 1 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 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 300 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 300 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 399 ms 11312 KB Output is correct
13 Correct 282 ms 11120 KB Output is correct
14 Correct 336 ms 8504 KB Output is correct
15 Correct 366 ms 8244 KB Output is correct
16 Correct 264 ms 7436 KB Output is correct
17 Correct 359 ms 8344 KB Output is correct
18 Correct 319 ms 8016 KB Output is correct
19 Correct 647 ms 12976 KB Output is correct
20 Correct 1156 ms 7816 KB Output is correct
21 Correct 243 ms 5728 KB Output is correct
22 Correct 1397 ms 9612 KB Output is correct
23 Correct 174 ms 10700 KB Output is correct
24 Correct 536 ms 8924 KB Output is correct
25 Correct 836 ms 10704 KB Output is correct
26 Correct 720 ms 10916 KB Output is correct
27 Correct 754 ms 10260 KB Output is correct
28 Correct 478 ms 30300 KB Output is correct
29 Correct 1096 ms 40876 KB Output is correct
30 Correct 3547 ms 29080 KB Output is correct
31 Correct 3347 ms 51464 KB Output is correct
32 Correct 502 ms 10456 KB Output is correct
33 Correct 673 ms 12236 KB Output is correct
34 Correct 240 ms 30092 KB Output is correct
35 Correct 750 ms 24140 KB Output is correct
36 Correct 1542 ms 33400 KB Output is correct
37 Correct 1141 ms 39088 KB Output is correct
38 Correct 1173 ms 38300 KB Output is correct
39 Correct 952 ms 28392 KB Output is correct
40 Correct 5 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 401 ms 7984 KB Output is correct
13 Correct 293 ms 8272 KB Output is correct
14 Correct 350 ms 5280 KB Output is correct
15 Correct 398 ms 4712 KB Output is correct
16 Correct 277 ms 4428 KB Output is correct
17 Correct 380 ms 4876 KB Output is correct
18 Correct 385 ms 4576 KB Output is correct
19 Correct 664 ms 10792 KB Output is correct
20 Correct 1252 ms 5344 KB Output is correct
21 Correct 380 ms 2520 KB Output is correct
22 Correct 1489 ms 6788 KB Output is correct
23 Correct 205 ms 7828 KB Output is correct
24 Correct 541 ms 5864 KB Output is correct
25 Correct 916 ms 8028 KB Output is correct
26 Correct 792 ms 8592 KB Output is correct
27 Correct 747 ms 7832 KB Output is correct
28 Correct 439 ms 29216 KB Output is correct
29 Correct 1103 ms 40752 KB Output is correct
30 Correct 3514 ms 29180 KB Output is correct
31 Correct 3230 ms 51464 KB Output is correct
32 Correct 466 ms 10456 KB Output is correct
33 Correct 1124 ms 12236 KB Output is correct
34 Correct 233 ms 30092 KB Output is correct
35 Correct 704 ms 24092 KB Output is correct
36 Correct 1368 ms 33440 KB Output is correct
37 Correct 1174 ms 39128 KB Output is correct
38 Correct 1309 ms 38260 KB Output is correct
39 Correct 579 ms 65864 KB Output is correct
40 Correct 1667 ms 68560 KB Output is correct
41 Correct 4030 ms 54168 KB Output is correct
42 Correct 3970 ms 102628 KB Output is correct
43 Correct 400 ms 59576 KB Output is correct
44 Correct 663 ms 10948 KB Output is correct
45 Correct 886 ms 28460 KB Output is correct
46 Correct 1731 ms 66740 KB Output is correct
47 Correct 1709 ms 66768 KB Output is correct
48 Correct 1709 ms 66480 KB Output is correct
49 Correct 0 ms 304 KB Output is correct