oj.uz

Submission #261059

# Submission time Handle Problem Language Result Execution time Memory
261059 2020-08-11T10:48:52 Z SamAnd Game (IOI13_game) C++17
80 / 100
 6010 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 = 10003 * 30 * 30;

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 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 0 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 0 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 623 ms 8748 KB Output is correct
5 Correct 471 ms 9084 KB Output is correct
6 Correct 515 ms 5880 KB Output is correct
7 Correct 555 ms 5880 KB Output is correct
8 Correct 391 ms 4600 KB Output is correct
9 Correct 531 ms 5752 KB Output is correct
10 Correct 498 ms 5264 KB Output is correct
11 Correct 1 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 0 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 0 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 1043 ms 10348 KB Output is correct
13 Correct 1688 ms 4216 KB Output is correct
14 Correct 352 ms 1400 KB Output is correct
15 Correct 1952 ms 5392 KB Output is correct
16 Correct 222 ms 9980 KB Output is correct
17 Correct 814 ms 7032 KB Output is correct
18 Correct 1431 ms 10616 KB Output is correct
19 Correct 1400 ms 10536 KB Output is correct
20 Correct 1250 ms 9976 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 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 0 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 0 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 643 ms 8924 KB Output is correct
13 Correct 476 ms 9208 KB Output is correct
14 Correct 501 ms 6136 KB Output is correct
15 Correct 570 ms 5752 KB Output is correct
16 Correct 390 ms 4604 KB Output is correct
17 Correct 542 ms 5752 KB Output is correct
18 Correct 518 ms 5496 KB Output is correct
19 Correct 1012 ms 10480 KB Output is correct
20 Correct 1643 ms 4180 KB Output is correct
21 Correct 361 ms 1272 KB Output is correct
22 Correct 1960 ms 5272 KB Output is correct
23 Correct 232 ms 10104 KB Output is correct
24 Correct 818 ms 7032 KB Output is correct
25 Correct 1448 ms 10324 KB Output is correct
26 Correct 1187 ms 10928 KB Output is correct
27 Correct 1108 ms 10084 KB Output is correct
28 Correct 872 ms 125928 KB Output is correct
29 Correct 2513 ms 141048 KB Output is correct
30 Correct 5764 ms 102080 KB Output is correct
31 Correct 5404 ms 78288 KB Output is correct
32 Correct 709 ms 1256 KB Output is correct
33 Correct 849 ms 2552 KB Output is correct
34 Correct 495 ms 137884 KB Output is correct
35 Correct 1828 ms 70592 KB Output is correct
36 Correct 3344 ms 138308 KB Output is correct
37 Correct 2933 ms 138652 KB Output is correct
38 Correct 2763 ms 137956 KB Output is correct
39 Correct 2267 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 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 304 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 645 ms 8964 KB Output is correct
13 Correct 478 ms 9080 KB Output is correct
14 Correct 518 ms 6040 KB Output is correct
15 Correct 583 ms 5676 KB Output is correct
16 Correct 395 ms 4624 KB Output is correct
17 Correct 600 ms 5880 KB Output is correct
18 Correct 654 ms 5368 KB Output is correct
19 Correct 1032 ms 10460 KB Output is correct
20 Correct 1719 ms 4024 KB Output is correct
21 Correct 380 ms 1304 KB Output is correct
22 Correct 2083 ms 5196 KB Output is correct
23 Correct 222 ms 9976 KB Output is correct
24 Correct 926 ms 6996 KB Output is correct
25 Correct 1842 ms 10328 KB Output is correct
26 Correct 1404 ms 10524 KB Output is correct
27 Correct 1332 ms 9876 KB Output is correct
28 Correct 997 ms 125944 KB Output is correct
29 Correct 2571 ms 141084 KB Output is correct
30 Correct 6010 ms 102344 KB Output is correct
31 Correct 5510 ms 78572 KB Output is correct
32 Correct 675 ms 1528 KB Output is correct
33 Correct 859 ms 2956 KB Output is correct
34 Correct 522 ms 138468 KB Output is correct
35 Correct 1919 ms 71032 KB Output is correct
36 Correct 3287 ms 139048 KB Output is correct
37 Correct 2672 ms 139064 KB Output is correct
38 Correct 2777 ms 138564 KB Output is correct
39 Runtime error 612 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -