oj.uz

Submission #156918

# Submission time Handle Problem Language Result Execution time Memory
156918 2019-10-08T09:32:46 Z TAISA_ Game (IOI13_game) C++14
63 / 100
 3321 ms 138700 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int nx, ny;
vector<vector<ll>> dat;
void upd(int x, int y, ll to) {
    int kx = x + nx, ky = y + ny;
    dat[kx][ky] = to;
    while (kx > 0) {
        if (kx < x + nx) {
            dat[kx][ky] = gcd2(dat[kx << 1][ky], dat[kx << 1 | 1][ky]);
        }
        int k = ky;
        k >>= 1;
        while (k > 0) {
            dat[kx][k] = gcd2(dat[kx][k << 1], dat[kx][k << 1 | 1]);
            k >>= 1;
        }
        kx >>= 1;
    }
}

ll getx(int x1, int y1, int x2, int y2, int ky, int k, int l, int r) {
    if (x2 <= l || r <= x1) {
        return 0;
    }
    if (x1 <= l && r <= x2) {
        return dat[k][ky];
    }
    ll vl = getx(x1, y1, x2, y2, ky, k << 1, l, (l + r) / 2);
    ll vr = getx(x1, y1, x2, y2, ky, k << 1 | 1, (l + r) / 2, r);
    return gcd2(vl, vr);
}

ll gety(int x1, int y1, int x2, int y2, int k, int l, int r) {
    if (y2 <= l || r <= y1) {
        return 0;
    }
    if (y1 <= l && r <= y2) {
        return getx(x1, y1, x2, y2, k, 1, 0, nx);
    }
    ll vl = gety(x1, y1, x2, y2, k << 1, l, (l + r) / 2);
    ll vr = gety(x1, y1, x2, y2, k << 1 | 1, (l + r) / 2, r);
    return gcd2(vl, vr);
}

void init(int R, int C) {
    ++R;
    ++C;
    nx = 1;
    while (nx < R) {
        nx <<= 1;
    }
    ny = 1;
    while (ny < C) {
        ny <<= 1;
    }
    dat.resize(2 * nx);
    for (int i = 0; i < 2 * nx; i++) {
        dat[i].resize(2 * ny);
    }
}

void update(int P, int Q, long long K) { upd(P, Q, K); }

long long calculate(int P, int Q, int U, int V) {
    return gety(P, Q, U + 1, V + 1, 1, 0, ny);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 1071 ms 70472 KB Output is correct
5 Correct 897 ms 74492 KB Output is correct
6 Correct 1281 ms 71908 KB Output is correct
7 Correct 1307 ms 71744 KB Output is correct
8 Correct 1002 ms 72088 KB Output is correct
9 Correct 1271 ms 71772 KB Output is correct
10 Correct 1242 ms 71436 KB Output is correct
11 Correct 2 ms 396 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 760 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 1536 ms 37492 KB Output is correct
13 Correct 2764 ms 34276 KB Output is correct
14 Correct 1206 ms 137136 KB Output is correct
15 Correct 3303 ms 137064 KB Output is correct
16 Correct 532 ms 136940 KB Output is correct
17 Correct 2213 ms 138140 KB Output is correct
18 Correct 2587 ms 138328 KB Output is correct
19 Correct 2606 ms 138700 KB Output is correct
20 Correct 2324 ms 137948 KB Output is correct
21 Correct 2 ms 252 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 1101 ms 70948 KB Output is correct
13 Correct 897 ms 74496 KB Output is correct
14 Correct 1256 ms 71964 KB Output is correct
15 Correct 1250 ms 71596 KB Output is correct
16 Correct 1000 ms 71956 KB Output is correct
17 Correct 1316 ms 71720 KB Output is correct
18 Correct 1140 ms 71568 KB Output is correct
19 Correct 1577 ms 41540 KB Output is correct
20 Correct 2786 ms 38160 KB Output is correct
21 Correct 1240 ms 137220 KB Output is correct
22 Correct 3315 ms 137192 KB Output is correct
23 Correct 539 ms 136728 KB Output is correct
24 Correct 2174 ms 138300 KB Output is correct
25 Correct 2711 ms 138232 KB Output is correct
26 Correct 2486 ms 138380 KB Output is correct
27 Correct 2418 ms 137944 KB Output is correct
28 Runtime error 4 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 1053 ms 71316 KB Output is correct
13 Correct 892 ms 74520 KB Output is correct
14 Correct 1238 ms 71828 KB Output is correct
15 Correct 1288 ms 71712 KB Output is correct
16 Correct 1020 ms 72124 KB Output is correct
17 Correct 1303 ms 71716 KB Output is correct
18 Correct 1191 ms 71500 KB Output is correct
19 Correct 1575 ms 41352 KB Output is correct
20 Correct 2770 ms 37992 KB Output is correct
21 Correct 1240 ms 137176 KB Output is correct
22 Correct 3321 ms 137148 KB Output is correct
23 Correct 576 ms 136788 KB Output is correct
24 Correct 2136 ms 138176 KB Output is correct
25 Correct 2531 ms 138340 KB Output is correct
26 Correct 2482 ms 138304 KB Output is correct
27 Correct 2319 ms 137852 KB Output is correct
28 Runtime error 4 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -