oj.uz

Submission #261014

# Submission time Handle Problem Language Result Execution time Memory
261014 2020-08-11T09:55:57 Z SamAnd Game (IOI13_game) C++17
63 / 100
 9498 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;

unordered_map<int, unordered_map<int, ll> > g;

void ubdy(int tlx, int trx, int tly, int try_, int x, int y, ll k, int posx, int posy)
{
    if (tly == try_)
    {
        if (tlx == trx)
        {
            g[posx][posy] = k;
            return;
        }
        g[posx][posy] = gcd(g[posx * 2][posy], g[posx * 2 + 1][posy]);
        return;
    }
    int m = (tly + try_) / 2;
    if (y <= m)
        ubdy(tlx, trx, tly, m, x, y, k, posx, posy * 2);
    else
        ubdy(tlx, trx, m + 1, try_, x, y, k, posx, posy * 2 + 1);
    g[posx][posy] = gcd(g[posx][posy * 2], g[posx][posy * 2 + 1]);
}

void ubdx(int tlx, int trx, int x, int y, ll k, int posx)
{
    if (tlx == trx)
    {
        ubdy(tlx, trx, 0, C - 1, x, y, k, posx, 1);
        return;
    }
    int m = (tlx + trx) / 2;
    if (x <= m)
        ubdx(tlx, m, x, y, k, posx * 2);
    else
        ubdx(m + 1, trx, x, y, k, posx * 2 + 1);
    ubdy(tlx, trx, 0, C - 1, x, y, k, posx, 1);
}

ll qryy(int tly, int try_, int ly, int ry, int posx, int posy)
{
    if (ly > ry)
        return 0;
    if (g.find(posx) == g.end())
        return 0;
    if (g[posx].find(posy) == g[posx].end())
        return 0;
    if (tly == ly && try_ == ry)
        return g[posx][posy];
    int m = (tly + try_) / 2;
    return gcd(qryy(tly, m, ly, min(m, ry), posx, posy * 2),
               qryy(m + 1, try_, max(m + 1, ly), ry, posx, posy * 2 + 1));
}

ll qryx(int tlx, int trx, int lx, int rx, int ly, int ry, int posx)
{
    if (lx > rx)
        return 0;
    if (tlx == lx && trx == rx)
    {
        return qryy(0, C - 1, ly, ry, posx, 1);
    }
    int m = (tlx + trx) / 2;
    return gcd(qryx(tlx, m, lx, min(m, rx), ly, ry, posx * 2),
               qryx(m + 1, trx, max(m + 1, lx), rx, ly, ry, posx * 2 + 1));
}

void init(int R, int C)
{
    ::R = R;
    ::C = C;
}

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 256 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 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 0 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 2969 ms 25072 KB Output is correct
5 Correct 2170 ms 25408 KB Output is correct
6 Correct 2235 ms 22504 KB Output is correct
7 Correct 2574 ms 22008 KB Output is correct
8 Correct 1271 ms 14212 KB Output is correct
9 Correct 2440 ms 22604 KB Output is correct
10 Correct 2567 ms 22212 KB Output is correct
11 Correct 0 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 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 4956 ms 31588 KB Output is correct
13 Correct 7192 ms 16820 KB Output is correct
14 Correct 948 ms 6008 KB Output is correct
15 Correct 9498 ms 23984 KB Output is correct
16 Correct 709 ms 47688 KB Output is correct
17 Correct 4177 ms 31556 KB Output is correct
18 Correct 7187 ms 49412 KB Output is correct
19 Correct 6172 ms 49540 KB Output is correct
20 Correct 6286 ms 48752 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 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 2985 ms 25164 KB Output is correct
13 Correct 2141 ms 25324 KB Output is correct
14 Correct 2232 ms 22368 KB Output is correct
15 Correct 2674 ms 22268 KB Output is correct
16 Correct 1341 ms 14372 KB Output is correct
17 Correct 2443 ms 22644 KB Output is correct
18 Correct 2725 ms 22280 KB Output is correct
19 Correct 5055 ms 31488 KB Output is correct
20 Correct 7048 ms 17028 KB Output is correct
21 Correct 958 ms 5880 KB Output is correct
22 Correct 9424 ms 23956 KB Output is correct
23 Correct 668 ms 47608 KB Output is correct
24 Correct 3836 ms 31756 KB Output is correct
25 Correct 8714 ms 48980 KB Output is correct
26 Correct 6419 ms 49348 KB Output is correct
27 Correct 5631 ms 48792 KB Output is correct
28 Runtime error 2101 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 3215 ms 25044 KB Output is correct
13 Correct 2124 ms 25296 KB Output is correct
14 Correct 2086 ms 22256 KB Output is correct
15 Correct 2741 ms 22204 KB Output is correct
16 Correct 1347 ms 14472 KB Output is correct
17 Correct 2400 ms 22652 KB Output is correct
18 Correct 2420 ms 22208 KB Output is correct
19 Correct 4926 ms 31604 KB Output is correct
20 Correct 6768 ms 16852 KB Output is correct
21 Correct 959 ms 5916 KB Output is correct
22 Correct 9026 ms 24032 KB Output is correct
23 Correct 679 ms 47608 KB Output is correct
24 Correct 4019 ms 31752 KB Output is correct
25 Correct 6862 ms 48856 KB Output is correct
26 Correct 5982 ms 49168 KB Output is correct
27 Correct 5549 ms 48756 KB Output is correct
28 Runtime error 2056 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -