oj.uz

Submission #261081

# Submission time Handle Problem Language Result Execution time Memory
261081 2020-08-11T11:19:57 Z SamAnd Game (IOI13_game) C++17
80 / 100
 9569 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 / 2], ury[T / 2];
ll g[T / 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 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 0 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 1868 ms 8976 KB Output is correct
5 Correct 1076 ms 9464 KB Output is correct
6 Correct 1140 ms 6112 KB Output is correct
7 Correct 1330 ms 5736 KB Output is correct
8 Correct 892 ms 4740 KB Output is correct
9 Correct 1150 ms 6112 KB Output is correct
10 Correct 1218 ms 5588 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 1845 ms 10780 KB Output is correct
13 Correct 2545 ms 4336 KB Output is correct
14 Correct 781 ms 1400 KB Output is correct
15 Correct 2844 ms 5684 KB Output is correct
16 Correct 262 ms 10488 KB Output is correct
17 Correct 1478 ms 7280 KB Output is correct
18 Correct 2430 ms 10696 KB Output is correct
19 Correct 2460 ms 11176 KB Output is correct
20 Correct 2117 ms 10716 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 2 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 1757 ms 9596 KB Output is correct
13 Correct 1112 ms 9780 KB Output is correct
14 Correct 1077 ms 6596 KB Output is correct
15 Correct 1363 ms 5764 KB Output is correct
16 Correct 867 ms 4536 KB Output is correct
17 Correct 1184 ms 5736 KB Output is correct
18 Correct 1159 ms 5252 KB Output is correct
19 Correct 1850 ms 10624 KB Output is correct
20 Correct 2336 ms 4092 KB Output is correct
21 Correct 762 ms 1144 KB Output is correct
22 Correct 2754 ms 5284 KB Output is correct
23 Correct 251 ms 10108 KB Output is correct
24 Correct 1539 ms 6936 KB Output is correct
25 Correct 2459 ms 10384 KB Output is correct
26 Correct 2164 ms 10620 KB Output is correct
27 Correct 2165 ms 10104 KB Output is correct
28 Correct 2829 ms 126016 KB Output is correct
29 Correct 6067 ms 141344 KB Output is correct
30 Correct 9369 ms 102688 KB Output is correct
31 Correct 8985 ms 78604 KB Output is correct
32 Correct 1915 ms 1580 KB Output is correct
33 Correct 2506 ms 2928 KB Output is correct
34 Correct 672 ms 138616 KB Output is correct
35 Correct 3943 ms 70936 KB Output is correct
36 Correct 6316 ms 139040 KB Output is correct
37 Correct 5474 ms 138948 KB Output is correct
38 Correct 5407 ms 138580 KB Output is correct
39 Correct 4629 ms 107000 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 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 1879 ms 9152 KB Output is correct
13 Correct 1097 ms 9464 KB Output is correct
14 Correct 1127 ms 6264 KB Output is correct
15 Correct 1188 ms 5920 KB Output is correct
16 Correct 850 ms 4984 KB Output is correct
17 Correct 1159 ms 6264 KB Output is correct
18 Correct 1113 ms 5752 KB Output is correct
19 Correct 1786 ms 11076 KB Output is correct
20 Correct 2345 ms 4432 KB Output is correct
21 Correct 805 ms 1528 KB Output is correct
22 Correct 2792 ms 5624 KB Output is correct
23 Correct 253 ms 10488 KB Output is correct
24 Correct 1423 ms 7332 KB Output is correct
25 Correct 2494 ms 11032 KB Output is correct
26 Correct 2174 ms 11056 KB Output is correct
27 Correct 2264 ms 10488 KB Output is correct
28 Correct 2700 ms 126536 KB Output is correct
29 Correct 6102 ms 141732 KB Output is correct
30 Correct 9569 ms 102736 KB Output is correct
31 Correct 8858 ms 78324 KB Output is correct
32 Correct 1806 ms 1600 KB Output is correct
33 Correct 2483 ms 3016 KB Output is correct
34 Correct 574 ms 138120 KB Output is correct
35 Correct 4070 ms 70732 KB Output is correct
36 Correct 6161 ms 138492 KB Output is correct
37 Correct 5484 ms 138616 KB Output is correct
38 Correct 5265 ms 137980 KB Output is correct
39 Runtime error 1587 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -