oj.uz

Submission #261055

# Submission time Handle Problem Language Result Execution time Memory
261055 2020-08-11T10:45:56 Z SamAnd Game (IOI13_game) C++17
80 / 100
 5905 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int T = 22003 * 30 * 30 * 3;

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

int R, C;

ll g[T];

int zy;
int uly[T], ury[T];

int zx;
int uy[T / 30];
int ulx[T / 30], urx[T / 30];

void ubdy(int tlx, int trx, int tly, int try_, int x, int y, ll k, int posyl, int posyr, int posy)
{
    if (tly == try_)
    {
        if (tlx == trx)
        {
            g[posy] = k;
            return;
        }
        g[posy] = gcd(g[posyl], g[posyr]);
        return;
    }
    int m = (tly + try_) / 2;
    if (y <= m)
    {
        if (!uly[posy])
            uly[posy] = ++zy;
        ubdy(tlx, trx, tly, m, x, y, k, uly[posyl], uly[posyr], uly[posy]);
    }
    else
    {
        if (!ury[posy])
            ury[posy] = ++zy;
        ubdy(tlx, trx, m + 1, try_, x, y, k, ury[posyl], ury[posyr], ury[posy]);
    }
    g[posy] = gcd(g[uly[posy]], g[ury[posy]]);
}

void ubdx(int tlx, int trx, int x, int y, ll k, int posx)
{
    if (tlx == trx)
    {
        if (!uy[posx])
            uy[posx] = ++zy;
        ubdy(tlx, trx, 0, C - 1, x, y, k, 0, 0, uy[posx]);
        return;
    }
    int m = (tlx + trx) / 2;
    if (x <= m)
    {
        if (!ulx[posx])
            ulx[posx] = ++zx;
        ubdx(tlx, m, x, y, k, ulx[posx]);
    }
    else
    {
        if (!urx[posx])
            urx[posx] = ++zx;
        ubdx(m + 1, trx, x, y, k, urx[posx]);
    }
    if (!uy[posx])
        uy[posx] = ++zy;
    ubdy(tlx, trx, 0, C - 1, x, y, k, uy[ulx[posx]], uy[urx[posx]], uy[posx]);
}

ll qryy(int tly, int try_, int ly, int ry, int posy)
{
    if (ly > ry)
        return 0;
    if (posy == 0)
        return 0;
    if (tly == ly && try_ == ry)
        return g[posy];
    int m = (tly + try_) / 2;
    return gcd(qryy(tly, m, ly, min(m, ry), uly[posy]),
               qryy(m + 1, try_, max(m + 1, ly), ry, ury[posy]));
}

ll qryx(int tlx, int trx, int lx, int rx, int ly, int ry, int posx)
{
    if (lx > rx)
        return 0;
    if (posx == 0)
        return 0;
    if (tlx == lx && trx == rx)
    {
        return qryy(0, C - 1, ly, ry, uy[posx]);
    }
    int m = (tlx + trx) / 2;
    return gcd(qryx(tlx, m, lx, min(m, rx), ly, ry, ulx[posx]),
               qryx(m + 1, trx, max(m + 1, lx), rx, ly, ry, urx[posx]));
}

void init(int R, int C)
{
    ::R = R;
    ::C = C;
    ++zx;
}

void update(int P, int Q, long long K)
{
    ubdx(0, R - 1, P, Q, K, 1);
}

long long calculate(int P, int Q, int U, int V)
{
    return qryx(0, R - 1, P, U, Q, V, 1);
}

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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 684 ms 8572 KB Output is correct
5 Correct 494 ms 9000 KB Output is correct
6 Correct 563 ms 5752 KB Output is correct
7 Correct 582 ms 5464 KB Output is correct
8 Correct 409 ms 4472 KB Output is correct
9 Correct 645 ms 5704 KB Output is correct
10 Correct 522 ms 5112 KB Output is correct
11 Correct 0 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 416 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1022 ms 10144 KB Output is correct
13 Correct 1735 ms 3836 KB Output is correct
14 Correct 398 ms 1144 KB Output is correct
15 Correct 1963 ms 5152 KB Output is correct
16 Correct 225 ms 9848 KB Output is correct
17 Correct 846 ms 6904 KB Output is correct
18 Correct 1707 ms 10548 KB Output is correct
19 Correct 1346 ms 10556 KB Output is correct
20 Correct 1280 ms 9768 KB Output is correct
21 Correct 0 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 618 ms 8632 KB Output is correct
13 Correct 472 ms 8952 KB Output is correct
14 Correct 536 ms 5752 KB Output is correct
15 Correct 594 ms 5396 KB Output is correct
16 Correct 394 ms 4344 KB Output is correct
17 Correct 553 ms 5624 KB Output is correct
18 Correct 511 ms 5240 KB Output is correct
19 Correct 1012 ms 10284 KB Output is correct
20 Correct 1677 ms 3836 KB Output is correct
21 Correct 348 ms 1100 KB Output is correct
22 Correct 1969 ms 5424 KB Output is correct
23 Correct 230 ms 9816 KB Output is correct
24 Correct 844 ms 6888 KB Output is correct
25 Correct 1421 ms 10256 KB Output is correct
26 Correct 1220 ms 10400 KB Output is correct
27 Correct 1278 ms 9848 KB Output is correct
28 Correct 884 ms 125756 KB Output is correct
29 Correct 2456 ms 140816 KB Output is correct
30 Correct 5905 ms 101872 KB Output is correct
31 Correct 5510 ms 78392 KB Output is correct
32 Correct 680 ms 1272 KB Output is correct
33 Correct 824 ms 2676 KB Output is correct
34 Correct 510 ms 137824 KB Output is correct
35 Correct 1800 ms 70516 KB Output is correct
36 Correct 3288 ms 138376 KB Output is correct
37 Correct 2718 ms 138628 KB Output is correct
38 Correct 2522 ms 137768 KB Output is correct
39 Correct 2351 ms 106616 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 615 ms 8824 KB Output is correct
13 Correct 478 ms 8824 KB Output is correct
14 Correct 504 ms 5752 KB Output is correct
15 Correct 566 ms 5496 KB Output is correct
16 Correct 389 ms 4344 KB Output is correct
17 Correct 529 ms 5496 KB Output is correct
18 Correct 500 ms 5240 KB Output is correct
19 Correct 1008 ms 10232 KB Output is correct
20 Correct 1653 ms 3836 KB Output is correct
21 Correct 356 ms 1144 KB Output is correct
22 Correct 2019 ms 5344 KB Output is correct
23 Correct 222 ms 9848 KB Output is correct
24 Correct 838 ms 6752 KB Output is correct
25 Correct 1669 ms 10200 KB Output is correct
26 Correct 1208 ms 10648 KB Output is correct
27 Correct 1186 ms 9848 KB Output is correct
28 Correct 854 ms 125688 KB Output is correct
29 Correct 2393 ms 140796 KB Output is correct
30 Correct 5769 ms 102028 KB Output is correct
31 Correct 5390 ms 78224 KB Output is correct
32 Correct 679 ms 1144 KB Output is correct
33 Correct 817 ms 2552 KB Output is correct
34 Correct 478 ms 138012 KB Output is correct
35 Correct 1748 ms 70420 KB Output is correct
36 Correct 3337 ms 138404 KB Output is correct
37 Correct 2590 ms 138488 KB Output is correct
38 Correct 2837 ms 137940 KB Output is correct
39 Runtime error 1216 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -