oj.uz

Submission #365215

# Submission time Handle Problem Language Result Execution time Memory
365215 2021-02-11T09:06:56 Z Berted Game (IOI13_game) C++17
100 / 100
 6386 ms 48084 KB 
#include "game.h"

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>

#define ll long long
#define pii pair<int, int>
#define ppi pair<pii, ll>
#define fst first
#define snd second

using namespace std;

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

namespace seg
{
    int r, c;

    vector<pii> Cx; vector<int> Rx;
    pii C[10000000]; int keep[10000001]; 
    ll val[10000000]; 

    int SSZ = 0;

    inline int newNode()
    {
        C[SSZ] = {-1, -1}; keep[SSZ] = -2; SSZ++;
        return SSZ - 1;
    }

    inline int newLine()
    {
        Cx.push_back({-1, -1}); Rx.push_back(-1);
        Rx.back() = newNode();
        return Cx.size() - 1;
    }

    inline void checkChildX(int u, bool b)
    {
        if (b && Cx[u].fst == -1)
        {
            int rr = newLine();
            Cx[u].fst = rr;
        }
        if (!b && Cx[u].snd == -1)
        {
            int rr = newLine();
            Cx[u].snd = rr;
        }
    }

    inline void checkChildY(int u, bool b)
    {
        if (b && C[u].fst == -1)
        {
            int idx = newNode();
            C[u].fst = idx;
        }
        if (!b && C[u].snd == -1)
        {
            int idx = newNode();
            C[u].snd = idx;
        }
    }

    inline int getRoot(int u)
    {
        if (u == -1) {return -1;}
        else {return Rx[u];}
    }

    inline int getChild(int u, bool b)
    {
        if (u == -1) {return -1;}
        else if (b) {return C[u].fst;}
        else {return C[u].snd;}
    }

    inline ll getVal(int u)
    {
        if (u == -1) {return 0;}
        return val[u];
    }

    void updateY(int u, int L, int R, int x, ll v)
    {
        if (L < R && (keep[u] != -2 && keep[u] != x))
        {
            int M = L + R >> 1;
            if (keep[u] != -1)
            {
                checkChildY(u, keep[u] <= M);
                if (keep[u] <= M)
                {
                    val[C[u].fst] = val[u];
                    keep[C[u].fst] = keep[u];
                }
                else
                {
                    val[C[u].snd] = val[u];
                    keep[C[u].snd] = keep[u];
                }
                keep[u] = -1;
            }
            
            checkChildY(u, x <= M);
            if (x <= M) updateY(C[u].fst, L, M, x, v);
            else updateY(C[u].snd, M + 1, R, x, v);
            val[u] = GCD(getVal(C[u].fst), getVal(C[u].snd));
        }
        else {keep[u] = x; val[u] = v;}
    }

    ll queryY(int u, int L, int R, int l, int r)
    {
        l = max(L, l); r = min(R, r);
        if (u == -1) {return 0;}
        if (l <= r)
        {
            if (L == l && R == r) {return val[u];}
            else if (keep[u] != -1)
            {
                if (l <= keep[u] && keep[u] <= r) return val[u];
                else return 0;
            }
            else
            {
                int M = L + R >> 1;
                return GCD(queryY(C[u].fst, L, M, l, r), queryY(C[u].snd, M + 1, R, l, r));
            }
        }
        return 0;
    }

    void updateX(int u, int L, int R, int x, int y, ll v)
    {
        if (L < R)
        {
            int M = L + R >> 1;
            checkChildX(u, x <= M);
            if (x <= M) updateX(Cx[u].fst, L, M, x, y, v);
            else updateX(Cx[u].snd, M + 1, R, x, y, v);
            v = GCD(queryY(getRoot(Cx[u].fst), 0, r - 1, y, y), queryY(getRoot(Cx[u].snd), 0, r - 1, y, y));
        }
        updateY(Rx[u], 0, r - 1, y, v);
    }

    

    ll queryX(int u, int L, int R, int lx, int rx, int ly, int ry)
    {
        lx = max(lx, L); rx = min(rx, R);
        if (u == -1) return 0;
        if (lx <= rx)
        {
            if (L == lx && R == rx) {return queryY(Rx[u], 0, r - 1, ly, ry);}
            else
            {
                int M = L + R >> 1;
                return GCD(queryX(Cx[u].fst, L, M, lx, rx, ly, ry), queryX(Cx[u].snd, M + 1, R, lx, rx, ly, ry));
            }
        }
        return 0;
    }
}

void init(int R, int C) 
{
    seg :: r = R; seg :: c = C;
    seg :: newLine();
}

void update(int P, int Q, ll K) 
{
    seg :: updateX(0, 0, seg :: c - 1, Q, P, K);
}

long long calculate(int P, int Q, int U, int V) 
{
    return seg :: queryX(0, 0, seg :: c - 1, Q, V, P, U);
}

Compilation message

game.cpp: In function 'void seg::updateY(int, int, int, int, long long int)':
game.cpp:102:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |             int M = L + R >> 1;
      |                     ~~^~~
game.cpp: In function 'long long int seg::queryY(int, int, int, int, int)':
game.cpp:141:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  141 |                 int M = L + R >> 1;
      |                         ~~^~~
game.cpp: In function 'void seg::updateX(int, int, int, int, int, long long int)':
game.cpp:152:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  152 |             int M = L + R >> 1;
      |                     ~~^~~
game.cpp: In function 'long long int seg::queryX(int, int, int, int, int, int, int)':
game.cpp:172:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  172 |                 int M = L + R >> 1;
      |                         ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 563 ms 11940 KB Output is correct
5 Correct 603 ms 11756 KB Output is correct
6 Correct 586 ms 9188 KB Output is correct
7 Correct 774 ms 8948 KB Output is correct
8 Correct 462 ms 7912 KB Output is correct
9 Correct 688 ms 9060 KB Output is correct
10 Correct 690 ms 8676 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 396 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 999 ms 11960 KB Output is correct
13 Correct 1684 ms 6988 KB Output is correct
14 Correct 334 ms 5612 KB Output is correct
15 Correct 1998 ms 8256 KB Output is correct
16 Correct 228 ms 9528 KB Output is correct
17 Correct 747 ms 8856 KB Output is correct
18 Correct 1159 ms 11032 KB Output is correct
19 Correct 1030 ms 11372 KB Output is correct
20 Correct 959 ms 10732 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 559 ms 11748 KB Output is correct
13 Correct 620 ms 11620 KB Output is correct
14 Correct 579 ms 9188 KB Output is correct
15 Correct 813 ms 9040 KB Output is correct
16 Correct 433 ms 8040 KB Output is correct
17 Correct 661 ms 9060 KB Output is correct
18 Correct 633 ms 8808 KB Output is correct
19 Correct 1042 ms 12036 KB Output is correct
20 Correct 1667 ms 7208 KB Output is correct
21 Correct 332 ms 5740 KB Output is correct
22 Correct 2013 ms 8172 KB Output is correct
23 Correct 207 ms 9672 KB Output is correct
24 Correct 695 ms 8812 KB Output is correct
25 Correct 1121 ms 11016 KB Output is correct
26 Correct 1030 ms 11208 KB Output is correct
27 Correct 939 ms 10680 KB Output is correct
28 Correct 590 ms 27740 KB Output is correct
29 Correct 1416 ms 27100 KB Output is correct
30 Correct 4630 ms 23296 KB Output is correct
31 Correct 4294 ms 19804 KB Output is correct
32 Correct 787 ms 10476 KB Output is correct
33 Correct 949 ms 11824 KB Output is correct
34 Correct 269 ms 20956 KB Output is correct
35 Correct 970 ms 17816 KB Output is correct
36 Correct 1993 ms 25308 KB Output is correct
37 Correct 1490 ms 25352 KB Output is correct
38 Correct 1412 ms 24944 KB Output is correct
39 Correct 1248 ms 22112 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 564 ms 11804 KB Output is correct
13 Correct 586 ms 11752 KB Output is correct
14 Correct 575 ms 9320 KB Output is correct
15 Correct 646 ms 9060 KB Output is correct
16 Correct 475 ms 8040 KB Output is correct
17 Correct 631 ms 9144 KB Output is correct
18 Correct 648 ms 8676 KB Output is correct
19 Correct 958 ms 12012 KB Output is correct
20 Correct 1713 ms 7200 KB Output is correct
21 Correct 400 ms 5612 KB Output is correct
22 Correct 1977 ms 8300 KB Output is correct
23 Correct 229 ms 9580 KB Output is correct
24 Correct 730 ms 8884 KB Output is correct
25 Correct 1158 ms 11136 KB Output is correct
26 Correct 1062 ms 11176 KB Output is correct
27 Correct 929 ms 10584 KB Output is correct
28 Correct 598 ms 27848 KB Output is correct
29 Correct 1455 ms 27236 KB Output is correct
30 Correct 4655 ms 23216 KB Output is correct
31 Correct 4350 ms 19584 KB Output is correct
32 Correct 757 ms 10456 KB Output is correct
33 Correct 963 ms 12020 KB Output is correct
34 Correct 257 ms 20828 KB Output is correct
35 Correct 949 ms 18148 KB Output is correct
36 Correct 2068 ms 25076 KB Output is correct
37 Correct 1505 ms 25272 KB Output is correct
38 Correct 1498 ms 24812 KB Output is correct
39 Correct 839 ms 48084 KB Output is correct
40 Correct 2399 ms 42584 KB Output is correct
41 Correct 6386 ms 41764 KB Output is correct
42 Correct 5626 ms 33300 KB Output is correct
43 Correct 468 ms 37204 KB Output is correct
44 Correct 1109 ms 11004 KB Output is correct
45 Correct 1165 ms 22172 KB Output is correct
46 Correct 2441 ms 41260 KB Output is correct
47 Correct 2552 ms 41264 KB Output is correct
48 Correct 2542 ms 41236 KB Output is correct
49 Correct 1 ms 364 KB Output is correct