oj.uz

Submission #93864

# Submission time Handle Problem Language Result Execution time Memory
93864 2019-01-12T13:57:29 Z alexpetrescu Game (IOI13_game) C++14
37 / 100
 13000 ms 45500 KB 
#include "game.h"
#include <cstring>
#include <algorithm>

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;
    }
    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;
    }
}

void update(int P, int Q, long long K) {
    poz = Q;
    val = K;
    update(aintX[P], 1, 0, c - 1);
}

long long calculate(int P, int Q, int U, int V) {
    ans = 0;
    left = Q;
    right = V;
    for (int i = P; i <= U; i++)
        query(aintX[i], 1, 0, c - 1);
    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 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1118 ms 43880 KB Output is correct
5 Correct 712 ms 44268 KB Output is correct
6 Correct 834 ms 43520 KB Output is correct
7 Correct 870 ms 45140 KB Output is correct
8 Correct 824 ms 45500 KB Output is correct
9 Correct 933 ms 45180 KB Output is correct
10 Correct 837 ms 44664 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Execution timed out 13097 ms 40332 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 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 17 ms 760 KB Output is correct
12 Correct 1086 ms 43512 KB Output is correct
13 Correct 711 ms 43792 KB Output is correct
14 Correct 779 ms 43000 KB Output is correct
15 Correct 769 ms 45088 KB Output is correct
16 Correct 730 ms 45372 KB Output is correct
17 Correct 759 ms 45048 KB Output is correct
18 Correct 683 ms 44584 KB Output is correct
19 Execution timed out 13043 ms 41108 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 2 ms 764 KB Output is correct
12 Correct 1224 ms 43512 KB Output is correct
13 Correct 729 ms 44024 KB Output is correct
14 Correct 885 ms 42876 KB Output is correct
15 Correct 862 ms 45036 KB Output is correct
16 Correct 785 ms 45432 KB Output is correct
17 Correct 880 ms 45084 KB Output is correct
18 Correct 783 ms 44664 KB Output is correct
19 Execution timed out 13058 ms 41164 KB Time limit exceeded
20 Halted 0 ms 0 KB -