oj.uz

Submission #261076

# Submission time Handle Problem Language Result Execution time Memory
261076 2020-08-11T11:17:37 Z SamAnd Game (IOI13_game) C++17
80 / 100
 9666 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;

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

int zy;
int uly[T], ury[T];
ll g[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 (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 512 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 0 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 1767 ms 9512 KB Output is correct
5 Correct 1073 ms 9592 KB Output is correct
6 Correct 1060 ms 6496 KB Output is correct
7 Correct 1194 ms 6264 KB Output is correct
8 Correct 849 ms 4984 KB Output is correct
9 Correct 1208 ms 6360 KB Output is correct
10 Correct 1116 ms 5884 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 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 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 1808 ms 11328 KB Output is correct
13 Correct 2351 ms 4664 KB Output is correct
14 Correct 777 ms 1784 KB Output is correct
15 Correct 2768 ms 5852 KB Output is correct
16 Correct 252 ms 10616 KB Output is correct
17 Correct 1462 ms 7380 KB Output is correct
18 Correct 2412 ms 11160 KB Output is correct
19 Correct 2178 ms 11256 KB Output is correct
20 Correct 1969 ms 10680 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 416 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 416 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1763 ms 9476 KB Output is correct
13 Correct 1102 ms 9616 KB Output is correct
14 Correct 1129 ms 6432 KB Output is correct
15 Correct 1445 ms 6632 KB Output is correct
16 Correct 916 ms 5548 KB Output is correct
17 Correct 1381 ms 6696 KB Output is correct
18 Correct 1219 ms 6300 KB Output is correct
19 Correct 1843 ms 11588 KB Output is correct
20 Correct 2432 ms 5208 KB Output is correct
21 Correct 795 ms 2256 KB Output is correct
22 Correct 3179 ms 6336 KB Output is correct
23 Correct 277 ms 11176 KB Output is correct
24 Correct 1592 ms 7928 KB Output is correct
25 Correct 2521 ms 11700 KB Output is correct
26 Correct 2514 ms 11932 KB Output is correct
27 Correct 2123 ms 11152 KB Output is correct
28 Correct 2710 ms 126992 KB Output is correct
29 Correct 5967 ms 142252 KB Output is correct
30 Correct 9360 ms 102844 KB Output is correct
31 Correct 9123 ms 78864 KB Output is correct
32 Correct 1844 ms 1572 KB Output is correct
33 Correct 2451 ms 2680 KB Output is correct
34 Correct 564 ms 138364 KB Output is correct
35 Correct 3928 ms 71044 KB Output is correct
36 Correct 6296 ms 138976 KB Output is correct
37 Correct 5493 ms 139264 KB Output is correct
38 Correct 5642 ms 138340 KB Output is correct
39 Correct 4915 ms 107000 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 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 1780 ms 9188 KB Output is correct
13 Correct 1076 ms 9304 KB Output is correct
14 Correct 1086 ms 6136 KB Output is correct
15 Correct 1222 ms 5808 KB Output is correct
16 Correct 847 ms 4728 KB Output is correct
17 Correct 1170 ms 5880 KB Output is correct
18 Correct 1152 ms 5496 KB Output is correct
19 Correct 1775 ms 11000 KB Output is correct
20 Correct 2699 ms 4288 KB Output is correct
21 Correct 832 ms 1420 KB Output is correct
22 Correct 2908 ms 5568 KB Output is correct
23 Correct 276 ms 10360 KB Output is correct
24 Correct 1497 ms 7156 KB Output is correct
25 Correct 2726 ms 10732 KB Output is correct
26 Correct 2094 ms 10984 KB Output is correct
27 Correct 2103 ms 10256 KB Output is correct
28 Correct 2714 ms 126200 KB Output is correct
29 Correct 6087 ms 141512 KB Output is correct
30 Correct 9666 ms 102604 KB Output is correct
31 Correct 8904 ms 79216 KB Output is correct
32 Correct 1884 ms 2060 KB Output is correct
33 Correct 2590 ms 3452 KB Output is correct
34 Correct 565 ms 138744 KB Output is correct
35 Correct 3987 ms 71032 KB Output is correct
36 Correct 6492 ms 139336 KB Output is correct
37 Correct 5891 ms 139372 KB Output is correct
38 Correct 5356 ms 138716 KB Output is correct
39 Runtime error 3315 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -