oj.uz

Submission #261110

# Submission time Handle Problem Language Result Execution time Memory
261110 2020-08-11T11:50:19 Z SamAnd Game (IOI13_game) C++17
80 / 100
 9308 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 / 4 * 3], ury[T / 4 * 3];
ll g[T / 4 * 3];

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 2 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 2 ms 384 KB Output is correct
4 Correct 1845 ms 12384 KB Output is correct
5 Correct 1107 ms 12664 KB Output is correct
6 Correct 1108 ms 9464 KB Output is correct
7 Correct 1289 ms 9208 KB Output is correct
8 Correct 923 ms 8276 KB Output is correct
9 Correct 1304 ms 9272 KB Output is correct
10 Correct 1295 ms 9044 KB Output is correct
11 Correct 1 ms 416 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 2 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 1838 ms 14388 KB Output is correct
13 Correct 2413 ms 7792 KB Output is correct
14 Correct 764 ms 4868 KB Output is correct
15 Correct 2830 ms 8964 KB Output is correct
16 Correct 321 ms 13944 KB Output is correct
17 Correct 1529 ms 10744 KB Output is correct
18 Correct 2980 ms 14228 KB Output is correct
19 Correct 2094 ms 14608 KB Output is correct
20 Correct 2058 ms 13916 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 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 1768 ms 12500 KB Output is correct
13 Correct 1067 ms 12824 KB Output is correct
14 Correct 1136 ms 9592 KB Output is correct
15 Correct 1205 ms 9272 KB Output is correct
16 Correct 834 ms 8312 KB Output is correct
17 Correct 1150 ms 9464 KB Output is correct
18 Correct 1166 ms 9108 KB Output is correct
19 Correct 1842 ms 14496 KB Output is correct
20 Correct 2338 ms 7876 KB Output is correct
21 Correct 773 ms 4984 KB Output is correct
22 Correct 2734 ms 9080 KB Output is correct
23 Correct 261 ms 13944 KB Output is correct
24 Correct 1534 ms 10848 KB Output is correct
25 Correct 2480 ms 14200 KB Output is correct
26 Correct 2091 ms 14328 KB Output is correct
27 Correct 1988 ms 13944 KB Output is correct
28 Correct 2660 ms 129844 KB Output is correct
29 Correct 6046 ms 145164 KB Output is correct
30 Correct 9308 ms 105976 KB Output is correct
31 Correct 8611 ms 82072 KB Output is correct
32 Correct 1797 ms 5112 KB Output is correct
33 Correct 2454 ms 6536 KB Output is correct
34 Correct 562 ms 142236 KB Output is correct
35 Correct 3931 ms 74428 KB Output is correct
36 Correct 6667 ms 142172 KB Output is correct
37 Correct 5500 ms 142652 KB Output is correct
38 Correct 5610 ms 141800 KB Output is correct
39 Correct 4870 ms 110328 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 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 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 1793 ms 12784 KB Output is correct
13 Correct 1085 ms 12980 KB Output is correct
14 Correct 1084 ms 10016 KB Output is correct
15 Correct 1211 ms 9416 KB Output is correct
16 Correct 845 ms 8440 KB Output is correct
17 Correct 1205 ms 9800 KB Output is correct
18 Correct 1146 ms 9416 KB Output is correct
19 Correct 1792 ms 14620 KB Output is correct
20 Correct 2318 ms 7800 KB Output is correct
21 Correct 774 ms 5240 KB Output is correct
22 Correct 2725 ms 9304 KB Output is correct
23 Correct 261 ms 14072 KB Output is correct
24 Correct 1490 ms 11060 KB Output is correct
25 Correct 2393 ms 14840 KB Output is correct
26 Correct 2073 ms 14740 KB Output is correct
27 Correct 1982 ms 14068 KB Output is correct
28 Correct 2669 ms 129712 KB Output is correct
29 Correct 5898 ms 145024 KB Output is correct
30 Correct 9299 ms 106100 KB Output is correct
31 Correct 8738 ms 81968 KB Output is correct
32 Correct 1805 ms 5088 KB Output is correct
33 Correct 2513 ms 6552 KB Output is correct
34 Correct 581 ms 141820 KB Output is correct
35 Correct 3951 ms 74168 KB Output is correct
36 Correct 6307 ms 142172 KB Output is correct
37 Correct 5464 ms 142376 KB Output is correct
38 Correct 5675 ms 141312 KB Output is correct
39 Runtime error 3049 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -