oj.uz

Submission #739617

# Submission time Handle Problem Language Result Execution time Memory
739617 2023-05-10T18:51:43 Z shrimb Game (IOI13_game) C++17
63 / 100
 1967 ms 256004 KB 
#ifdef MUAATH_5
#include "ioi.h"
#else
#include "game.h"
#endif
#include <numeric>
#define ll long long
#define int long long
#define OUT 0
#define merge gcd
using namespace std;
 
const int N = 1'000'000'000;
const int SZ = 3'500'000;
 
 
 
struct ynode {
    ynode() : val(OUT), left(0), right(0) {}
    ll val;
    int left, right;
};
 
struct xnode {
    xnode() : left(0), right(0), yy(0) {}
    int left, right;
    int yy;
} root;
 
int yyc = 1, xxc = 1;
xnode xnds[SZ];
ynode ynds[SZ];
 
ll query_y(const int &qy1, const int &qy2, const ynode &node, int l = 0, int r = N - 1)
{
    if (r < qy1 || qy2 < l) return OUT;
    if (qy1 <= l && r <= qy2) return node.val;
    const int mid = (l + r) / 2;
    return merge(
        (node.left ? query_y(qy1, qy2, ynds[node.left], l, mid) : OUT),
        (node.right ? query_y(qy1, qy2, ynds[node.right], mid + 1, r) : OUT)
    );
}
 
ll query_x(const int &qx1, const int &qy1, const int &qx2, const int &qy2, const xnode &node, int l = 0, int r = N - 1)
{
    if (r < qx1 || qx2 < l) return OUT;
    if (qx1 <= l && r <= qx2)
        return query_y(qy1, qy2, ynds[node.yy]);
    const int mid = (l + r) / 2;
    return merge(
        (node.left ? query_x(qx1, qy1, qx2, qy2, xnds[node.left], l, mid) : OUT),
        (node.right ? query_x(qx1, qy1, qx2, qy2, xnds[node.right], mid + 1, r) : OUT)
    );
}
 
 
void update_y(const int &qy, const ll &val, ynode &node, int l = 0, int r = N - 1)
{
    if (l == r) {
        node.val = val;
        return;
    }
    const int mid = (l + r) / 2;
    if (qy <= mid) {
        if (!node.left) node.left = yyc++;
        update_y(qy, val, ynds[node.left], l, mid);
    }
    else {
        if (!node.right) node.right = yyc++;
        update_y(qy, val, ynds[node.right], mid + 1, r);
    }
    node.val = merge((node.left ? ynds[node.left].val : OUT), (node.right ? ynds[node.right].val : OUT));
}
 
void update_x(const int &qx, const int &qy, const ll &val, xnode &node, int l = 0, int r = N - 1)
{
    if (!node.yy) node.yy = yyc++;
    if (l == r) {
        update_y(qy, val, ynds[node.yy]);
        return;
    }
    const int mid = (l + r) / 2;
    if (qx <= mid) {
        if (!node.left) node.left = xxc++;
        update_x(qx, qy, val, xnds[node.left], l, mid);
    }
    else {
        if (!node.right) node.right = xxc++;
        update_x(qx, qy, val, xnds[node.right], mid + 1, r);
    }
    update_y(qy, merge(
        (node.left ? query_y(qy, qy, ynds[xnds[node.left].yy]) : OUT),
        (node.right ? query_y(qy, qy, ynds[xnds[node.right].yy]) : OUT)
    ), ynds[node.yy]);
}
 
void init(signed R, signed C) { root = xnode(); }
void update(signed x, signed y, long long k) { update_x(x, y, k, root); }
long long calculate(signed x1, signed y1, signed x2, signed y2) { return query_x(x1, y1, x2, y2, root); }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 164556 KB Output is correct
2 Correct 71 ms 164588 KB Output is correct
3 Correct 73 ms 164580 KB Output is correct
4 Correct 71 ms 164652 KB Output is correct
5 Correct 69 ms 164652 KB Output is correct
6 Correct 68 ms 164588 KB Output is correct
7 Correct 83 ms 164608 KB Output is correct
8 Correct 66 ms 164556 KB Output is correct
9 Correct 86 ms 164592 KB Output is correct
10 Correct 69 ms 164548 KB Output is correct
11 Correct 89 ms 164624 KB Output is correct
12 Correct 74 ms 164624 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 164576 KB Output is correct
2 Correct 66 ms 164572 KB Output is correct
3 Correct 73 ms 164652 KB Output is correct
4 Correct 892 ms 168636 KB Output is correct
5 Correct 689 ms 168916 KB Output is correct
6 Correct 837 ms 165712 KB Output is correct
7 Correct 851 ms 165500 KB Output is correct
8 Correct 595 ms 166200 KB Output is correct
9 Correct 834 ms 165536 KB Output is correct
10 Correct 828 ms 165168 KB Output is correct
11 Correct 65 ms 164588 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 164608 KB Output is correct
2 Correct 65 ms 164580 KB Output is correct
3 Correct 73 ms 164612 KB Output is correct
4 Correct 68 ms 164620 KB Output is correct
5 Correct 70 ms 164528 KB Output is correct
6 Correct 67 ms 164560 KB Output is correct
7 Correct 65 ms 164520 KB Output is correct
8 Correct 67 ms 164616 KB Output is correct
9 Correct 80 ms 164556 KB Output is correct
10 Correct 68 ms 164528 KB Output is correct
11 Correct 68 ms 164528 KB Output is correct
12 Correct 1265 ms 168788 KB Output is correct
13 Correct 1672 ms 165432 KB Output is correct
14 Correct 592 ms 165164 KB Output is correct
15 Correct 1967 ms 165540 KB Output is correct
16 Correct 552 ms 165464 KB Output is correct
17 Correct 1124 ms 166044 KB Output is correct
18 Correct 1847 ms 165692 KB Output is correct
19 Correct 1615 ms 165892 KB Output is correct
20 Correct 1459 ms 165480 KB Output is correct
21 Correct 69 ms 164556 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 164552 KB Output is correct
2 Correct 66 ms 164564 KB Output is correct
3 Correct 68 ms 164700 KB Output is correct
4 Correct 75 ms 164540 KB Output is correct
5 Correct 75 ms 164568 KB Output is correct
6 Correct 69 ms 164556 KB Output is correct
7 Correct 65 ms 164536 KB Output is correct
8 Correct 67 ms 164644 KB Output is correct
9 Correct 68 ms 164528 KB Output is correct
10 Correct 71 ms 164556 KB Output is correct
11 Correct 67 ms 164600 KB Output is correct
12 Correct 801 ms 168716 KB Output is correct
13 Correct 641 ms 169168 KB Output is correct
14 Correct 821 ms 165640 KB Output is correct
15 Correct 838 ms 165396 KB Output is correct
16 Correct 572 ms 166496 KB Output is correct
17 Correct 856 ms 165584 KB Output is correct
18 Correct 812 ms 165152 KB Output is correct
19 Correct 1239 ms 168740 KB Output is correct
20 Correct 1751 ms 165484 KB Output is correct
21 Correct 580 ms 165100 KB Output is correct
22 Correct 1920 ms 165620 KB Output is correct
23 Correct 558 ms 165280 KB Output is correct
24 Correct 1117 ms 165840 KB Output is correct
25 Correct 1780 ms 165736 KB Output is correct
26 Correct 1561 ms 165912 KB Output is correct
27 Correct 1552 ms 165352 KB Output is correct
28 Runtime error 415 ms 256004 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 164564 KB Output is correct
2 Correct 80 ms 164640 KB Output is correct
3 Correct 83 ms 164544 KB Output is correct
4 Correct 66 ms 164528 KB Output is correct
5 Correct 70 ms 164580 KB Output is correct
6 Correct 84 ms 164588 KB Output is correct
7 Correct 68 ms 164604 KB Output is correct
8 Correct 66 ms 164656 KB Output is correct
9 Correct 68 ms 164628 KB Output is correct
10 Correct 67 ms 164644 KB Output is correct
11 Correct 68 ms 164544 KB Output is correct
12 Correct 779 ms 168728 KB Output is correct
13 Correct 633 ms 168940 KB Output is correct
14 Correct 800 ms 165708 KB Output is correct
15 Correct 821 ms 165492 KB Output is correct
16 Correct 573 ms 166220 KB Output is correct
17 Correct 788 ms 165544 KB Output is correct
18 Correct 752 ms 165052 KB Output is correct
19 Correct 1216 ms 168708 KB Output is correct
20 Correct 1721 ms 165268 KB Output is correct
21 Correct 571 ms 165076 KB Output is correct
22 Correct 1915 ms 165380 KB Output is correct
23 Correct 565 ms 165388 KB Output is correct
24 Correct 1085 ms 165840 KB Output is correct
25 Correct 1716 ms 165804 KB Output is correct
26 Correct 1557 ms 165920 KB Output is correct
27 Correct 1399 ms 165264 KB Output is correct
28 Runtime error 370 ms 256000 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -