oj.uz

Submission #261061

# Submission time Handle Problem Language Result Execution time Memory
261061 2020-08-11T10:49:56 Z SamAnd Game (IOI13_game) C++17
80 / 100
 6190 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 * 6;

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 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 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 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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 636 ms 8684 KB Output is correct
5 Correct 492 ms 8912 KB Output is correct
6 Correct 535 ms 5692 KB Output is correct
7 Correct 606 ms 5512 KB Output is correct
8 Correct 393 ms 4472 KB Output is correct
9 Correct 615 ms 5604 KB Output is correct
10 Correct 512 ms 5088 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 360 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 1034 ms 10140 KB Output is correct
13 Correct 1719 ms 3660 KB Output is correct
14 Correct 358 ms 1020 KB Output is correct
15 Correct 2032 ms 4968 KB Output is correct
16 Correct 219 ms 9720 KB Output is correct
17 Correct 845 ms 6688 KB Output is correct
18 Correct 1564 ms 10268 KB Output is correct
19 Correct 1360 ms 10412 KB Output is correct
20 Correct 1462 ms 9648 KB Output is correct
21 Correct 1 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 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 416 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 645 ms 8696 KB Output is correct
13 Correct 507 ms 8824 KB Output is correct
14 Correct 580 ms 5752 KB Output is correct
15 Correct 774 ms 5604 KB Output is correct
16 Correct 475 ms 4440 KB Output is correct
17 Correct 643 ms 5496 KB Output is correct
18 Correct 623 ms 5380 KB Output is correct
19 Correct 1105 ms 10576 KB Output is correct
20 Correct 1660 ms 4104 KB Output is correct
21 Correct 350 ms 1404 KB Output is correct
22 Correct 2051 ms 5608 KB Output is correct
23 Correct 244 ms 10104 KB Output is correct
24 Correct 864 ms 7112 KB Output is correct
25 Correct 1494 ms 10544 KB Output is correct
26 Correct 1182 ms 10488 KB Output is correct
27 Correct 1116 ms 10040 KB Output is correct
28 Correct 874 ms 125944 KB Output is correct
29 Correct 2600 ms 141400 KB Output is correct
30 Correct 6190 ms 102436 KB Output is correct
31 Correct 5755 ms 78764 KB Output is correct
32 Correct 693 ms 1864 KB Output is correct
33 Correct 828 ms 3064 KB Output is correct
34 Correct 480 ms 138528 KB Output is correct
35 Correct 1624 ms 71384 KB Output is correct
36 Correct 3392 ms 139068 KB Output is correct
37 Correct 2757 ms 139164 KB Output is correct
38 Correct 2643 ms 138488 KB Output is correct
39 Correct 2178 ms 107280 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 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 9464 KB Output is correct
13 Correct 469 ms 9592 KB Output is correct
14 Correct 516 ms 6392 KB Output is correct
15 Correct 612 ms 6136 KB Output is correct
16 Correct 422 ms 5112 KB Output is correct
17 Correct 577 ms 6264 KB Output is correct
18 Correct 509 ms 6008 KB Output is correct
19 Correct 1006 ms 11052 KB Output is correct
20 Correct 1654 ms 4344 KB Output is correct
21 Correct 352 ms 1704 KB Output is correct
22 Correct 1944 ms 5880 KB Output is correct
23 Correct 243 ms 10488 KB Output is correct
24 Correct 885 ms 7544 KB Output is correct
25 Correct 1516 ms 10948 KB Output is correct
26 Correct 1267 ms 11208 KB Output is correct
27 Correct 1192 ms 10360 KB Output is correct
28 Correct 933 ms 126524 KB Output is correct
29 Correct 2434 ms 141456 KB Output is correct
30 Correct 5912 ms 102240 KB Output is correct
31 Correct 5400 ms 78492 KB Output is correct
32 Correct 699 ms 1400 KB Output is correct
33 Correct 848 ms 2952 KB Output is correct
34 Correct 532 ms 138104 KB Output is correct
35 Correct 1688 ms 70488 KB Output is correct
36 Correct 3323 ms 138212 KB Output is correct
37 Correct 2538 ms 138596 KB Output is correct
38 Correct 2603 ms 137968 KB Output is correct
39 Runtime error 1271 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -