oj.uz

Submission #590703

# Submission time Handle Problem Language Result Execution time Memory
590703 2022-07-06T08:59:38 Z Drew_ Game (IOI13_game) C++17
63 / 100
 9226 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define f1 first
#define s2 second

using ii = pair<int, int>;
using ll = long long;

const int MAX = 5e3 + 69;

int ar[MAX][MAX];
inline ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        if (X < MAX && Y < MAX)
            return ar[X][Y];

        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int R, C;
unordered_map<ll, ll> st; 
void init(int r, int c) 
{
    R = r; C = c;

    for (int i = 0; i < MAX; ++i)
        for (int j = (i == 0); j < MAX; ++j)
            ar[i][j] = __gcd(i, j);
}

inline ll get(int a, int b)
{
    if (!st.count(2ll * a*C + b))
        return 0;
    return st[2ll * a*C + b];
}

void update(int P, int Q, ll K) 
{
    int _P = P + R, _Q = Q + C;
    for (int i = _P; i > 0; i >>= 1)
    {
        for (int j = _Q; j > 0; j >>= 1)
        {
            if (i == _P && j == _Q) st[2ll * i*C + j] = K;
            else if (i == _P) st[2ll * i*C + j] = gcd(get(i, j << 1), get(i, j << 1 | 1));
            else if (j == _Q) st[2ll * i*C + j] = gcd(get(i << 1, j), get(i << 1 | 1, j));
            else st[2ll * i*C + j] = gcd(gcd(get(i, j << 1), get(i, j << 1 | 1)), gcd(get(i << 1, j), get(i << 1 | 1, j)));
        }
    }
}

ll calculate(int P, int Q, int U, int V) 
{
    ll res = 0;
    for (P += R, U += R+1; P < U; P >>= 1, U >>= 1)
    {
        if (P & 1)
        {
            for (int l = Q+C, r = V+C+1; l < r; l >>= 1, r >>= 1)
            {
                if (l & 1) res = gcd(res, get(P, l++));
                if (r & 1) res = gcd(res, get(P, --r));
            }
            P++;
        }
        if (U & 1)
        {
            --U;
            for (int l = Q+C, r = V+C+1; l < r; l >>= 1, r >>= 1)
            {
                if (l & 1) res = gcd(res, get(U, l++));
                if (r & 1) res = gcd(res, get(U, --r));
            }
        }
    } 
    return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1086 ms 100800 KB Output is correct
2 Correct 1094 ms 100920 KB Output is correct
3 Correct 1063 ms 100908 KB Output is correct
4 Correct 1072 ms 100868 KB Output is correct
5 Correct 1060 ms 100772 KB Output is correct
6 Correct 1067 ms 100988 KB Output is correct
7 Correct 1082 ms 101028 KB Output is correct
8 Correct 1079 ms 100740 KB Output is correct
9 Correct 1084 ms 101008 KB Output is correct
10 Correct 1069 ms 100836 KB Output is correct
11 Correct 1070 ms 100868 KB Output is correct
12 Correct 1071 ms 100972 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 100892 KB Output is correct
2 Correct 1082 ms 100728 KB Output is correct
3 Correct 1092 ms 100844 KB Output is correct
4 Correct 1943 ms 115844 KB Output is correct
5 Correct 1659 ms 116120 KB Output is correct
6 Correct 1937 ms 112980 KB Output is correct
7 Correct 1964 ms 112728 KB Output is correct
8 Correct 1521 ms 108624 KB Output is correct
9 Correct 1951 ms 113060 KB Output is correct
10 Correct 1909 ms 112460 KB Output is correct
11 Correct 1053 ms 100760 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 100880 KB Output is correct
2 Correct 1094 ms 100984 KB Output is correct
3 Correct 1109 ms 101052 KB Output is correct
4 Correct 1061 ms 100804 KB Output is correct
5 Correct 1072 ms 100752 KB Output is correct
6 Correct 1071 ms 100892 KB Output is correct
7 Correct 1069 ms 100852 KB Output is correct
8 Correct 1062 ms 100996 KB Output is correct
9 Correct 1077 ms 100948 KB Output is correct
10 Correct 1043 ms 100812 KB Output is correct
11 Correct 1073 ms 100864 KB Output is correct
12 Correct 2692 ms 124052 KB Output is correct
13 Correct 2398 ms 107560 KB Output is correct
14 Correct 1984 ms 101536 KB Output is correct
15 Correct 2823 ms 111092 KB Output is correct
16 Correct 1894 ms 124248 KB Output is correct
17 Correct 2378 ms 114692 KB Output is correct
18 Correct 3400 ms 124648 KB Output is correct
19 Correct 3418 ms 124708 KB Output is correct
20 Correct 3064 ms 124044 KB Output is correct
21 Correct 1084 ms 100832 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1065 ms 100924 KB Output is correct
2 Correct 1071 ms 100872 KB Output is correct
3 Correct 1078 ms 101120 KB Output is correct
4 Correct 1061 ms 100748 KB Output is correct
5 Correct 1076 ms 100884 KB Output is correct
6 Correct 1084 ms 101032 KB Output is correct
7 Correct 1075 ms 100844 KB Output is correct
8 Correct 1075 ms 100832 KB Output is correct
9 Correct 1103 ms 100944 KB Output is correct
10 Correct 1078 ms 100800 KB Output is correct
11 Correct 1066 ms 100964 KB Output is correct
12 Correct 2065 ms 115748 KB Output is correct
13 Correct 1920 ms 116076 KB Output is correct
14 Correct 2136 ms 113020 KB Output is correct
15 Correct 2123 ms 112712 KB Output is correct
16 Correct 1584 ms 108560 KB Output is correct
17 Correct 2015 ms 112920 KB Output is correct
18 Correct 1941 ms 112552 KB Output is correct
19 Correct 2751 ms 124024 KB Output is correct
20 Correct 2350 ms 107652 KB Output is correct
21 Correct 2004 ms 101564 KB Output is correct
22 Correct 2797 ms 111084 KB Output is correct
23 Correct 1899 ms 124168 KB Output is correct
24 Correct 2428 ms 114692 KB Output is correct
25 Correct 3745 ms 124528 KB Output is correct
26 Correct 3054 ms 124692 KB Output is correct
27 Correct 2972 ms 124004 KB Output is correct
28 Runtime error 9226 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1070 ms 100852 KB Output is correct
2 Correct 1060 ms 100900 KB Output is correct
3 Correct 1063 ms 101240 KB Output is correct
4 Correct 1068 ms 100748 KB Output is correct
5 Correct 1052 ms 100864 KB Output is correct
6 Correct 1062 ms 100916 KB Output is correct
7 Correct 1073 ms 100856 KB Output is correct
8 Correct 1059 ms 100764 KB Output is correct
9 Correct 1054 ms 100980 KB Output is correct
10 Correct 1052 ms 100864 KB Output is correct
11 Correct 1079 ms 100824 KB Output is correct
12 Correct 2031 ms 115784 KB Output is correct
13 Correct 1666 ms 116172 KB Output is correct
14 Correct 1786 ms 112988 KB Output is correct
15 Correct 1964 ms 112664 KB Output is correct
16 Correct 1586 ms 108468 KB Output is correct
17 Correct 2141 ms 112928 KB Output is correct
18 Correct 1971 ms 112532 KB Output is correct
19 Correct 2816 ms 124208 KB Output is correct
20 Correct 3064 ms 107588 KB Output is correct
21 Correct 2009 ms 101544 KB Output is correct
22 Correct 2821 ms 111184 KB Output is correct
23 Correct 2074 ms 124272 KB Output is correct
24 Correct 2487 ms 114636 KB Output is correct
25 Correct 3418 ms 124540 KB Output is correct
26 Correct 3470 ms 124692 KB Output is correct
27 Correct 3099 ms 124180 KB Output is correct
28 Runtime error 9046 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -