oj.uz

답안 #93857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93857 2019-01-12T13:34:03 Z alexpetrescu 게임 (IOI13_game) C++14
10 / 100
 13000 ms 92984 KB 
#include "game.h"
#include <cstring>
#include <vector>
#include <algorithm>

#define W 6

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 1020 KB Output is correct
3 Correct 6 ms 1148 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 1144 KB Output is correct
6 Correct 8 ms 1144 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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 9637 ms 80280 KB Output is correct
5 Correct 4725 ms 80452 KB Output is correct
6 Execution timed out 13012 ms 76816 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 7 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 6 ms 1144 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 6 ms 1016 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 13056 ms 92984 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 7 ms 1144 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 1016 KB Output is correct
6 Correct 6 ms 1016 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 6 ms 1144 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 9197 ms 80964 KB Output is correct
13 Correct 4676 ms 80912 KB Output is correct
14 Execution timed out 13014 ms 77396 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 1 ms 252 KB Output is correct
5 Correct 2 ms 1064 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 6 ms 1060 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 9447 ms 80356 KB Output is correct
13 Correct 4770 ms 80868 KB Output is correct
14 Execution timed out 13025 ms 77480 KB Time limit exceeded
15 Halted 0 ms 0 KB -