oj.uz

Submission #261087

# Submission time Handle Problem Language Result Execution time Memory
261087 2020-08-11T11:24:18 Z SamAnd Game (IOI13_game) C++17
80 / 100
 9405 ms 256000 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;

map<pair<int, int>, ll> mp;

int zy;
int uly[T / 3 * 2], ury[T / 3 * 2];
ll g[T / 3 * 2];

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 (trx - tlx + 1 <= 3 && try_ - tly + 1 <= 3)
    {
        g[posy] = 0;
        for (int i = tlx; i <= trx; ++i)
        {
            for (int j = tly; j <= try_; ++j)
            {
                if (mp.find(m_p(i, j)) != mp.end())
                    g[posy] = gcd(g[posy], mp[m_p(i, j)]);
            }
        }
        return;
    }
    if (tly == try_)
    {
        if (tlx == trx)
        {
            g[posy] = k;
            return;
        }
        g[posy] = 0;
        int m = (tlx + trx) / 2;
        if (m - tlx + 1 <= 3)
        {
            for (int i = tlx; i <= m; ++i)
            {
                if (mp.find(m_p(i, tly)) != mp.end())
                    g[posy] = gcd(g[posy], mp[m_p(i, tly)]);
            }
        }
        else
            g[posy] = gcd(g[posy], g[posyl]);
        if (trx - m <= 3)
        {
            for (int i = m + 1; i <= trx; ++i)
            {
                if (mp.find(m_p(i, tly)) != mp.end())
                    g[posy] = gcd(g[posy], mp[m_p(i, tly)]);
            }
        }
        else
            g[posy] = gcd(g[posy], 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 tlx, int trx, 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)
    {
        if (trx - tlx + 1 <= 3 && try_ - tly + 1 <= 3)
        {
            ll g = 0;
            for (int i = tlx; i <= trx; ++i)
            {
                for (int j = tly; j <= try_; ++j)
                {
                    if (mp.find(m_p(i, j)) != mp.end())
                        g = gcd(g, mp[m_p(i, j)]);
                }
            }
            return g;
        }
        return g[posy];
    }
    int m = (tly + try_) / 2;
    return gcd(qryy(tlx, trx, tly, m, ly, min(m, ry), uly[posy]),
               qryy(tlx, trx, 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(tlx, trx, 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)
{
    mp[m_p(P, Q)] = 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 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 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1790 ms 9196 KB Output is correct
5 Correct 1074 ms 9616 KB Output is correct
6 Correct 1114 ms 6392 KB Output is correct
7 Correct 1289 ms 5880 KB Output is correct
8 Correct 861 ms 4984 KB Output is correct
9 Correct 1170 ms 5960 KB Output is correct
10 Correct 1184 ms 5752 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 288 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 1781 ms 10960 KB Output is correct
13 Correct 2333 ms 4456 KB Output is correct
14 Correct 782 ms 1436 KB Output is correct
15 Correct 2767 ms 5752 KB Output is correct
16 Correct 253 ms 10488 KB Output is correct
17 Correct 1457 ms 7288 KB Output is correct
18 Correct 2364 ms 11128 KB Output is correct
19 Correct 2172 ms 10856 KB Output is correct
20 Correct 2131 ms 10232 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 0 ms 384 KB Output is correct
2 Correct 1 ms 380 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 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 1840 ms 8952 KB Output is correct
13 Correct 1090 ms 9016 KB Output is correct
14 Correct 1057 ms 5980 KB Output is correct
15 Correct 1178 ms 5624 KB Output is correct
16 Correct 838 ms 4600 KB Output is correct
17 Correct 1197 ms 5764 KB Output is correct
18 Correct 1248 ms 5300 KB Output is correct
19 Correct 1777 ms 10488 KB Output is correct
20 Correct 2336 ms 3992 KB Output is correct
21 Correct 757 ms 1144 KB Output is correct
22 Correct 2746 ms 5272 KB Output is correct
23 Correct 264 ms 9976 KB Output is correct
24 Correct 1498 ms 6904 KB Output is correct
25 Correct 2429 ms 10316 KB Output is correct
26 Correct 2139 ms 10616 KB Output is correct
27 Correct 1946 ms 10004 KB Output is correct
28 Correct 2643 ms 126128 KB Output is correct
29 Correct 6036 ms 141228 KB Output is correct
30 Correct 9385 ms 102148 KB Output is correct
31 Correct 8800 ms 78332 KB Output is correct
32 Correct 1803 ms 1104 KB Output is correct
33 Correct 2448 ms 2680 KB Output is correct
34 Correct 573 ms 138232 KB Output is correct
35 Correct 3779 ms 70544 KB Output is correct
36 Correct 6203 ms 138648 KB Output is correct
37 Correct 5277 ms 138812 KB Output is correct
38 Correct 5417 ms 138128 KB Output is correct
39 Correct 4695 ms 106844 KB Output is correct
40 Correct 0 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 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 1769 ms 8568 KB Output is correct
13 Correct 1080 ms 9032 KB Output is correct
14 Correct 1108 ms 5752 KB Output is correct
15 Correct 1287 ms 5496 KB Output is correct
16 Correct 876 ms 4408 KB Output is correct
17 Correct 1294 ms 5660 KB Output is correct
18 Correct 1299 ms 5368 KB Output is correct
19 Correct 2164 ms 10488 KB Output is correct
20 Correct 2415 ms 4052 KB Output is correct
21 Correct 762 ms 1272 KB Output is correct
22 Correct 2737 ms 5224 KB Output is correct
23 Correct 251 ms 9976 KB Output is correct
24 Correct 1528 ms 6716 KB Output is correct
25 Correct 2646 ms 10556 KB Output is correct
26 Correct 2117 ms 10488 KB Output is correct
27 Correct 1998 ms 9816 KB Output is correct
28 Correct 2775 ms 126108 KB Output is correct
29 Correct 6030 ms 141220 KB Output is correct
30 Correct 9405 ms 102116 KB Output is correct
31 Correct 9204 ms 78196 KB Output is correct
32 Correct 1913 ms 1300 KB Output is correct
33 Correct 2486 ms 2464 KB Output is correct
34 Correct 577 ms 138156 KB Output is correct
35 Correct 4056 ms 70588 KB Output is correct
36 Correct 6209 ms 138468 KB Output is correct
37 Correct 5181 ms 138616 KB Output is correct
38 Correct 5213 ms 138104 KB Output is correct
39 Runtime error 2484 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -