oj.uz

Submission #581732

# Submission time Handle Problem Language Result Execution time Memory
581732 2022-06-23T05:19:26 Z ggoh Game (IOI13_game) C++14
100 / 100
 4011 ms 95160 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int R, C, N, ch, P, Q, U, V;
int px, qx;
int xco, yco;
long long K;
struct Y
{
    Y *left, *right;
    long long val;
    int only;
    Y()
    {
        left = right = NULL;
        val = 0ll;
        only = -1;
    }
};
struct X
{
    X *left, *right;
    Y *ynode;
    X()
    {
        left = right = NULL;
        ynode = NULL;
    }
} * inix;

long long gcd2(long long xx, long long yy)
{
    if (yy == 0)
        return xx;
    return gcd2(yy, xx % yy);
}

void yup(Y *y, int s, int e, long long v)
{
    int m = (s + e) >> 1;
    if (y->only == -1)
    {
        y->val = v;
        y->only = yco;
        return;
    }
    else if (y->only >= 0)
    {
        if (y->only == yco)
        {
            y->val = v;
            return;
        }
        else
        {
            if (y->only <= m)
            {
                y->left = new Y();
                y->left->val = y->val;
                y->left->only = y->only;
            }
            else
            {
                y->right = new Y();
                y->right->val = y->val;
                y->right->only = y->only;
            }
            y->only = -2;
        }
    }
    if (m >= yco)
    {
        if (!y->left)
        {
            y->left = new Y();
        }
        yup(y->left, s, m, v);
    }
    else
    {
        if (!y->right)
        {
            y->right = new Y();
        }
        yup(y->right, m + 1, e, v);
    }
    long long l = 0, r = 0;
    if (y->left)
        l = y->left->val;
    if (y->right)
        r = y->right->val;
    y->val = gcd2(l, r);
}
long long yans(Y *y, int s, int e, int py, int qy)
{
    int m = (s + e) >> 1;
    if ((!y) || s > qy || e < py)
        return 0ll;
    if (py <= s && e <= qy)
        return y->val;
    if (y->only >= 0)
    {
        if (py <= y->only && y->only <= qy)
        {
            return y->val;
        }
        else
            return 0ll;
    }
    long long l = 0, r = 0;
    if (y->left)
        l = yans(y->left, s, m, py, qy);
    if (y->right)
        r = yans(y->right, m + 1, e, py, qy);
    return gcd2(l, r);
}
void xup(X *x, int s, int e, long long v)
{
    int m = (s + e) >> 1;
    if (!x->ynode)
        x->ynode = new Y();
    if (s != e)
    {
        if (m >= xco)
        {
            if (!x->left)
            {
                x->left = new X();
            }
            xup(x->left, s, m, v);
        }
        else
        {
            if (!x->right)
            {
                x->right = new X();
            }
            xup(x->right, m + 1, e, v);
        }
    }
    long long realv;
    if (s == e)
        realv = v;
    else
    {
        realv = gcd2(x->left ? yans(x->left->ynode, 0, C - 1, yco, yco) : 0, x->right ? yans(x->right->ynode, 0, C - 1, yco, yco) : 0);
    }
    yup(x->ynode, 0, C - 1, realv);
}
long long xans(X *x, int s, int e, int px, int qx, int py, int qy)
{
    int m = (s + e) >> 1;
    if ((!x->ynode) || s > qx || e < px)
        return 0ll;
    if (px <= s && e <= qx)
    {
        return yans(x->ynode, 0, C - 1, py, qy);
    }
    long long l = 0, r = 0;
    if (x->left)
        l = xans(x->left, s, m, px, qx, py, qy);
    if (x->right)
        r = xans(x->right, m + 1, e, px, qx, py, qy);
    return gcd2(l, r);
}
void init(int RR, int CC)
{
    R = RR;
    C = CC;
    inix = new X();
}
void update(int P, int Q, long long K)
{
    xco = P;
    yco = Q;
    xup(inix, 0, R - 1, K);
}
long long calculate(int P, int Q, int U, int V)
{
    return xans(inix, 0, R - 1, P, U, Q, V);
}

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 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 1 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 340 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 451 ms 9004 KB Output is correct
5 Correct 339 ms 9300 KB Output is correct
6 Correct 370 ms 6128 KB Output is correct
7 Correct 463 ms 5784 KB Output is correct
8 Correct 289 ms 4168 KB Output is correct
9 Correct 423 ms 5936 KB Output is correct
10 Correct 409 ms 5572 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 256 KB Output is correct
5 Correct 0 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 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 740 ms 12336 KB Output is correct
13 Correct 1329 ms 5760 KB Output is correct
14 Correct 281 ms 968 KB Output is correct
15 Correct 1598 ms 7432 KB Output is correct
16 Correct 180 ms 11184 KB Output is correct
17 Correct 650 ms 6876 KB Output is correct
18 Correct 1058 ms 11556 KB Output is correct
19 Correct 896 ms 11628 KB Output is correct
20 Correct 851 ms 11144 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 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 502 ms 9140 KB Output is correct
13 Correct 332 ms 9304 KB Output is correct
14 Correct 399 ms 6116 KB Output is correct
15 Correct 440 ms 5864 KB Output is correct
16 Correct 290 ms 4172 KB Output is correct
17 Correct 439 ms 5872 KB Output is correct
18 Correct 418 ms 5708 KB Output is correct
19 Correct 753 ms 12344 KB Output is correct
20 Correct 1285 ms 5704 KB Output is correct
21 Correct 244 ms 1048 KB Output is correct
22 Correct 1542 ms 7392 KB Output is correct
23 Correct 187 ms 11232 KB Output is correct
24 Correct 627 ms 6836 KB Output is correct
25 Correct 1097 ms 11592 KB Output is correct
26 Correct 958 ms 11612 KB Output is correct
27 Correct 892 ms 11172 KB Output is correct
28 Correct 475 ms 37644 KB Output is correct
29 Correct 1251 ms 43320 KB Output is correct
30 Correct 3155 ms 43488 KB Output is correct
31 Correct 2964 ms 34620 KB Output is correct
32 Correct 515 ms 10560 KB Output is correct
33 Correct 700 ms 13984 KB Output is correct
34 Correct 239 ms 37020 KB Output is correct
35 Correct 824 ms 25664 KB Output is correct
36 Correct 1683 ms 41272 KB Output is correct
37 Correct 1267 ms 41532 KB Output is correct
38 Correct 1278 ms 40760 KB Output is correct
39 Correct 1026 ms 33944 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 340 KB Output is correct
7 Correct 1 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 497 ms 9076 KB Output is correct
13 Correct 324 ms 9340 KB Output is correct
14 Correct 403 ms 6116 KB Output is correct
15 Correct 479 ms 5908 KB Output is correct
16 Correct 348 ms 4208 KB Output is correct
17 Correct 442 ms 5836 KB Output is correct
18 Correct 380 ms 5576 KB Output is correct
19 Correct 755 ms 12396 KB Output is correct
20 Correct 1285 ms 5744 KB Output is correct
21 Correct 274 ms 956 KB Output is correct
22 Correct 1532 ms 7560 KB Output is correct
23 Correct 196 ms 11208 KB Output is correct
24 Correct 649 ms 6908 KB Output is correct
25 Correct 1082 ms 11552 KB Output is correct
26 Correct 885 ms 11648 KB Output is correct
27 Correct 821 ms 11228 KB Output is correct
28 Correct 440 ms 37700 KB Output is correct
29 Correct 1148 ms 43416 KB Output is correct
30 Correct 3205 ms 43448 KB Output is correct
31 Correct 2877 ms 34544 KB Output is correct
32 Correct 545 ms 10560 KB Output is correct
33 Correct 602 ms 14072 KB Output is correct
34 Correct 261 ms 37080 KB Output is correct
35 Correct 793 ms 25744 KB Output is correct
36 Correct 1511 ms 41200 KB Output is correct
37 Correct 1173 ms 41448 KB Output is correct
38 Correct 1182 ms 40804 KB Output is correct
39 Correct 609 ms 95160 KB Output is correct
40 Correct 1723 ms 78948 KB Output is correct
41 Correct 4011 ms 86024 KB Output is correct
42 Correct 3720 ms 66628 KB Output is correct
43 Correct 467 ms 73780 KB Output is correct
44 Correct 608 ms 10872 KB Output is correct
45 Correct 1012 ms 34008 KB Output is correct
46 Correct 2025 ms 77656 KB Output is correct
47 Correct 2099 ms 77944 KB Output is correct
48 Correct 1892 ms 77296 KB Output is correct
49 Correct 1 ms 212 KB Output is correct