oj.uz

Submission #261041

# Submission time Handle Problem Language Result Execution time Memory
261041 2020-08-11T10:26:36 Z SamAnd Game (IOI13_game) C++17
80 / 100
 5765 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;

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];
int ulx[T], urx[T];

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 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 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 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 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 630 ms 8772 KB Output is correct
5 Correct 472 ms 8956 KB Output is correct
6 Correct 512 ms 5880 KB Output is correct
7 Correct 587 ms 5496 KB Output is correct
8 Correct 392 ms 4600 KB Output is correct
9 Correct 542 ms 5752 KB Output is correct
10 Correct 502 ms 5240 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 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 1086 ms 10576 KB Output is correct
13 Correct 1738 ms 4216 KB Output is correct
14 Correct 358 ms 1272 KB Output is correct
15 Correct 1996 ms 5220 KB Output is correct
16 Correct 226 ms 9976 KB Output is correct
17 Correct 863 ms 6904 KB Output is correct
18 Correct 1434 ms 10296 KB Output is correct
19 Correct 1243 ms 10616 KB Output is correct
20 Correct 1183 ms 10000 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 416 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 627 ms 8696 KB Output is correct
13 Correct 482 ms 9076 KB Output is correct
14 Correct 534 ms 5752 KB Output is correct
15 Correct 569 ms 5496 KB Output is correct
16 Correct 397 ms 4600 KB Output is correct
17 Correct 563 ms 5624 KB Output is correct
18 Correct 515 ms 5368 KB Output is correct
19 Correct 1049 ms 10744 KB Output is correct
20 Correct 1657 ms 4088 KB Output is correct
21 Correct 362 ms 1408 KB Output is correct
22 Correct 1969 ms 5144 KB Output is correct
23 Correct 263 ms 9976 KB Output is correct
24 Correct 832 ms 7160 KB Output is correct
25 Correct 1465 ms 10464 KB Output is correct
26 Correct 1206 ms 10488 KB Output is correct
27 Correct 1202 ms 9832 KB Output is correct
28 Correct 877 ms 136312 KB Output is correct
29 Correct 2284 ms 150812 KB Output is correct
30 Correct 5638 ms 108836 KB Output is correct
31 Correct 5243 ms 85100 KB Output is correct
32 Correct 689 ms 10488 KB Output is correct
33 Correct 843 ms 11896 KB Output is correct
34 Correct 494 ms 144716 KB Output is correct
35 Correct 1721 ms 80248 KB Output is correct
36 Correct 3198 ms 149076 KB Output is correct
37 Correct 2475 ms 149220 KB Output is correct
38 Correct 2439 ms 148584 KB Output is correct
39 Correct 2270 ms 117152 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 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 616 ms 8684 KB Output is correct
13 Correct 475 ms 8952 KB Output is correct
14 Correct 502 ms 5752 KB Output is correct
15 Correct 562 ms 5624 KB Output is correct
16 Correct 402 ms 4472 KB Output is correct
17 Correct 571 ms 6008 KB Output is correct
18 Correct 516 ms 5240 KB Output is correct
19 Correct 1065 ms 10488 KB Output is correct
20 Correct 1707 ms 4124 KB Output is correct
21 Correct 355 ms 1272 KB Output is correct
22 Correct 1988 ms 5280 KB Output is correct
23 Correct 228 ms 10048 KB Output is correct
24 Correct 849 ms 6820 KB Output is correct
25 Correct 1581 ms 10336 KB Output is correct
26 Correct 1209 ms 10488 KB Output is correct
27 Correct 1131 ms 9976 KB Output is correct
28 Correct 861 ms 136184 KB Output is correct
29 Correct 2393 ms 151012 KB Output is correct
30 Correct 5765 ms 109048 KB Output is correct
31 Correct 5401 ms 85324 KB Output is correct
32 Correct 685 ms 10476 KB Output is correct
33 Correct 890 ms 11584 KB Output is correct
34 Correct 497 ms 144688 KB Output is correct
35 Correct 1729 ms 80160 KB Output is correct
36 Correct 3219 ms 148908 KB Output is correct
37 Correct 2793 ms 149164 KB Output is correct
38 Correct 2645 ms 148808 KB Output is correct
39 Runtime error 1207 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -