oj.uz

Submission #93856

# Submission time Handle Problem Language Result Execution time Memory
93856 2019-01-12T13:31:42 Z alexpetrescu Game (IOI13_game) C++14
10 / 100
 13000 ms 89012 KB 
#include "game.h"
#include <cstring>
#include <vector>
#include <algorithm>

#define W 7

long long **mat;
long long ****rmq;
long long **aintX, **aintY, val, ans;
int nrlin, nrcol, r, c, lg2[100001], left, right, poz;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

void query(long long aint[], int p, int st, int dr) {
    if (left <= st && dr <= right)
        ans = gcd2(aint[p], ans);
    else {
        int m = (st + dr) / 2;
        if (left <= m) query(aint, 2 * p, st, m);
        if (m < right) query(aint, 2 * p + 1, m + 1, dr);
    }
}

void update(long long aint[], int p, int st, int dr) {
    if (st == dr)
        aint[p] = val;
    else {
        int m = (st + dr) / 2;
        if (poz <= m) update(aint, 2 * p, st, m);
        else update(aint, 2 * p + 1, m + 1, dr);
        aint[p] = gcd2(aint[2 * p], aint[2 * p + 1]);
    }
}

void init(int R, int C) {
    r = R;
    c = C;
    mat = new long long*[R];
    for (int i = 0; i < R; i++) {
        mat[i] = new long long[C];
        for (int j = 0; j < C; j++)
            mat[i][j] = 0;
    }
    nrlin = R / W;
    nrcol = C / W;
    int n = std::max(nrlin, nrcol);
    for (int i = 2; i <= n; i++)
        if ((1 << (lg2[i - 1] + 1)) == i)
            lg2[i] = lg2[i - 1] + 1;
        else
            lg2[i] = lg2[i - 1];
    aintX = new long long*[R];
    for (int i = 0; i < R; i++) {
        aintX[i] = new long long[4 * C];
        for (int j = 0; j < 4 * C; j++)
            aintX[i][j] = 0;
    }
    aintY = new long long*[C];
    for (int i = 0; i < C; i++) {
        aintY[i] = new long long[4 * R];
        for (int j = 0; j < 4 * R; j++)
            aintY[i][j] = 0;
    }
    rmq = new long long***[nrlin];
    for (int i = 0; i < nrlin; i++) {
        rmq[i] = new long long**[nrcol];
        for (int j = 0; j < nrcol; j++) {
            rmq[i][j] = new long long*[lg2[nrlin] + 1];
            for (int a = 0; a <= lg2[nrlin]; a++) {
                rmq[i][j][a] = new long long[lg2[nrcol] + 1];
                for (int b = 0; b <= lg2[nrcol]; b++)
                    rmq[i][j][a][b] = 0;
            }
        }
    }
}

void update(int P, int Q, long long K) {
    poz = Q;
    val = K;
    update(aintX[P], 1, 0, c - 1);
    poz = P;
    update(aintY[Q], 1, 0, r - 1);
    mat[P][Q] = K;
    P /= W;
    Q /= W;
    if (P < nrlin && Q < nrcol) {
        rmq[P][Q][0][0] = 0;
        for (int i = W * P; i < W * P + W; i++)
            for (int j = W * Q; j < W * Q + W; j++)
                rmq[P][Q][0][0] = gcd2(rmq[P][Q][0][0], mat[i][j]);
        for (int i = P; i < nrlin; i++) {
            for (int j = Q; j < nrcol; j++) {
                for (int b = 1; (1 << b) <= j + 1; b++)
                    rmq[i][j][0][b] = gcd2(rmq[i][j][0][b - 1], rmq[i][j - (1 << (b - 1))][0][b - 1]);
                for (int a = 1; (1 << a) <= i + 1; a++)
                    for (int b = 0; (1 << b) <= j + 1; b++)
                        rmq[i][j][a][b] = gcd2(rmq[i][j][a - 1][b], rmq[i - (1 << (a - 1))][j][a - 1][b]);
            }
        }
    }
}

long long calculate(int p, int q, int u, int v) {
    ans = 0;
    int P = p / W + bool(p % W), Q = q / W + bool(q % W), U = u / W - 1 + bool(u % W == W - 1), V = v / W - 1 + bool(v % W == W - 1);
    left = q;
    right = v;
    if (P > U) {
        for (int i = p; i <= u; i++)
            query(aintX[i], 1, 0, c - 1);
    } else {
        if (p % W)
            for (int i = p; i % W; i++)
                query(aintX[i], 1, 0, c - 1);
        if (u % W != W - 1)
            for (int i = u - u % W; i <= u; i++)
                query(aintX[i], 1, 0, c - 1);
    }
    left = p;
    right = u;
    if (Q > V) {
        for (int i = q; i <= v; i++)
            query(aintY[i], 1, 0, r - 1);
    } else {
        if (q % W)
            for (int i = q; i % W; i++)
                query(aintY[i], 1, 0, r - 1);
        if (v % W != W - 1)
            for (int i = v - v % W; i <= v; i++)
                query(aintY[i], 1, 0, r - 1);
    }

    if (P <= U && Q <= V) {
        int a = lg2[U - P + 1], b = lg2[V - Q + 1];
        ans = gcd2(ans, gcd2(gcd2(gcd2(rmq[U][V][a][b], rmq[P + (1 << a) - 1][V][a][b]), rmq[U][Q + (1 << b) - 1][a][b]), rmq[P + (1 << a) - 1][Q + (1 << b) - 1][a][b]));
    }
    return ans;
}

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 2 ms 376 KB Output is correct
2 Correct 6 ms 1144 KB Output is correct
3 Correct 6 ms 1016 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 1016 KB Output is correct
6 Correct 5 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct
11 Correct 3 ms 1144 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 10640 ms 82496 KB Output is correct
5 Correct 6520 ms 84036 KB Output is correct
6 Execution timed out 13014 ms 78592 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 5 ms 1016 KB Output is correct
3 Correct 5 ms 1144 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 1016 KB Output is correct
6 Correct 5 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 5 ms 1144 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1144 KB Output is correct
12 Execution timed out 13061 ms 89012 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 1016 KB Output is correct
3 Correct 5 ms 1144 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 1016 KB Output is correct
6 Correct 5 ms 1016 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 5 ms 1020 KB Output is correct
10 Correct 3 ms 1172 KB Output is correct
11 Correct 3 ms 1020 KB Output is correct
12 Correct 10702 ms 82532 KB Output is correct
13 Correct 6448 ms 83912 KB Output is correct
14 Execution timed out 13058 ms 78668 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 6 ms 1144 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 1144 KB Output is correct
6 Correct 5 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 10893 ms 82404 KB Output is correct
13 Correct 6494 ms 83948 KB Output is correct
14 Execution timed out 13009 ms 78644 KB Time limit exceeded
15 Halted 0 ms 0 KB -