oj.uz

Submission #590690

# Submission time Handle Problem Language Result Execution time Memory
590690 2022-07-06T08:42:51 Z Drew_ Game (IOI13_game) C++17
63 / 100
 12361 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;

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

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

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 0 ms 212 KB Output is correct
2 Correct 4 ms 428 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 428 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 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 2403 ms 21460 KB Output is correct
5 Correct 1476 ms 21848 KB Output is correct
6 Correct 1982 ms 18912 KB Output is correct
7 Correct 2504 ms 18536 KB Output is correct
8 Correct 1194 ms 12032 KB Output is correct
9 Correct 2293 ms 18664 KB Output is correct
10 Correct 2207 ms 18292 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 424 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 4965 ms 27872 KB Output is correct
13 Correct 3706 ms 11108 KB Output is correct
14 Correct 1814 ms 1848 KB Output is correct
15 Correct 4599 ms 15460 KB Output is correct
16 Correct 2079 ms 35880 KB Output is correct
17 Correct 3447 ms 21844 KB Output is correct
18 Correct 5894 ms 36340 KB Output is correct
19 Correct 5178 ms 36556 KB Output is correct
20 Correct 5134 ms 35708 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 4 ms 428 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2340 ms 21424 KB Output is correct
13 Correct 1482 ms 22088 KB Output is correct
14 Correct 1978 ms 18836 KB Output is correct
15 Correct 2509 ms 18924 KB Output is correct
16 Correct 1146 ms 12184 KB Output is correct
17 Correct 2191 ms 18708 KB Output is correct
18 Correct 2158 ms 18596 KB Output is correct
19 Correct 4953 ms 27988 KB Output is correct
20 Correct 3675 ms 11180 KB Output is correct
21 Correct 1850 ms 1776 KB Output is correct
22 Correct 4641 ms 15568 KB Output is correct
23 Correct 1969 ms 35920 KB Output is correct
24 Correct 3380 ms 21856 KB Output is correct
25 Correct 5956 ms 36504 KB Output is correct
26 Correct 5178 ms 36540 KB Output is correct
27 Correct 5147 ms 35836 KB Output is correct
28 Runtime error 12308 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 0 ms 212 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2337 ms 20700 KB Output is correct
13 Correct 1472 ms 20972 KB Output is correct
14 Correct 2020 ms 18120 KB Output is correct
15 Correct 2574 ms 17868 KB Output is correct
16 Correct 1123 ms 11460 KB Output is correct
17 Correct 2155 ms 17960 KB Output is correct
18 Correct 2382 ms 17620 KB Output is correct
19 Correct 4895 ms 27104 KB Output is correct
20 Correct 3661 ms 10400 KB Output is correct
21 Correct 1820 ms 1440 KB Output is correct
22 Correct 4572 ms 14736 KB Output is correct
23 Correct 2008 ms 35148 KB Output is correct
24 Correct 3356 ms 21276 KB Output is correct
25 Correct 5879 ms 35420 KB Output is correct
26 Correct 5163 ms 35704 KB Output is correct
27 Correct 5094 ms 35072 KB Output is correct
28 Runtime error 12361 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -