oj.uz

Submission #261013

# Submission time Handle Problem Language Result Execution time Memory
261013 2020-08-11T09:53:39 Z SamAnd Game (IOI13_game) C++17
37 / 100
 13000 ms 47072 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<int, 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 3 ms 768 KB Output is correct
3 Correct 4 ms 768 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 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 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 5769 ms 38936 KB Output is correct
5 Correct 4166 ms 38680 KB Output is correct
6 Correct 3840 ms 36800 KB Output is correct
7 Correct 4081 ms 36720 KB Output is correct
8 Correct 2371 ms 23708 KB Output is correct
9 Correct 4493 ms 36856 KB Output is correct
10 Correct 4468 ms 36448 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Execution timed out 13043 ms 46872 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 4 ms 768 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 4 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 5687 ms 38756 KB Output is correct
13 Correct 4128 ms 38880 KB Output is correct
14 Correct 3888 ms 36948 KB Output is correct
15 Correct 4062 ms 36616 KB Output is correct
16 Correct 2541 ms 24004 KB Output is correct
17 Correct 4400 ms 36892 KB Output is correct
18 Correct 4416 ms 36216 KB Output is correct
19 Execution timed out 13045 ms 46848 KB Time limit exceeded
20 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 4 ms 768 KB Output is correct
3 Correct 4 ms 768 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 5732 ms 38916 KB Output is correct
13 Correct 4157 ms 38672 KB Output is correct
14 Correct 3818 ms 37112 KB Output is correct
15 Correct 4094 ms 36476 KB Output is correct
16 Correct 2569 ms 23912 KB Output is correct
17 Correct 4382 ms 36988 KB Output is correct
18 Correct 4556 ms 36564 KB Output is correct
19 Execution timed out 13061 ms 47072 KB Time limit exceeded
20 Halted 0 ms 0 KB -