oj.uz

Submission #101866

# Submission time Handle Problem Language Result Execution time Memory
101866 2019-03-20T15:10:42 Z naoai Game (IOI13_game) C++14
63 / 100
 4323 ms 257024 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

struct Aint2 {
    i64 d;
    Aint2 *st, *dr;

    Aint2 () {
        d = 0;
        st = dr = NULL;
    }
};

struct Aint1 {
    Aint2 *rep;
    Aint1 *st, *dr;

    Aint1 () {
        rep = NULL;
        st = dr = NULL;
    }
} *root;

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

static int R, C;

int linx, liny;
int linupd, colupd;

i64 query1 (Aint1 *nod, int x, int y, int st, int dr, int a, int b);

Aint2* update2 (Aint2 *nod, int x, int y, int pos, i64 val) {
    if (x == y) {
        nod -> d = val;
        if (linupd - 1 >= linx)
            nod -> d = gcd2(nod -> d, query1(root, 0, R - 1, linx, linupd - 1, colupd, colupd));
        if (linupd + 1 <= liny)
            nod -> d = gcd2(nod -> d, query1(root, 0, R - 1, linupd + 1, liny, colupd, colupd));
        return nod;
    }

    int mij = (x + y) / 2;
    if (pos <= mij) {
        if (nod -> st == NULL)
            nod -> st = new Aint2();
        nod -> st = update2(nod -> st, x, mij, pos, val);
    } else {
        if (nod -> dr == NULL)
            nod -> dr = new Aint2();
        nod -> dr = update2(nod -> dr, mij + 1, y, pos, val);
    }

    nod -> d = 0;
    if (nod -> st != NULL) nod -> d = gcd2(nod -> d, nod -> st -> d);
    if (nod -> dr != NULL) nod -> d = gcd2(nod -> d, nod -> dr -> d);
    return nod;
}

i64 query2 (Aint2 *nod, int x, int y, int st, int dr) {
    if (nod == NULL)
        return 0;
    if (st <= x && y <= dr)
        return nod -> d;

    int mij = (x + y) / 2;
    i64 ans = 0;

    if (st <= mij)
        ans = gcd2(ans, query2(nod -> st, x, mij, st, dr));
    if (mij < dr)
        ans = gcd2(ans, query2(nod -> dr, mij + 1, y, st, dr));
    return ans;
}

Aint1* update1 (Aint1 *nod, int x, int y, int r, int c, i64 val) {
    if (nod -> rep == NULL)
        nod -> rep = new Aint2();

    linx = x;
    liny = y;
    nod -> rep = update2(nod -> rep, 0, C - 1, c, val);

    if (x == y) {
        return nod;
    }

    int mij = (x + y) / 2;
    if (r <= mij) {
        if (nod -> st == NULL)
            nod -> st = new Aint1();
        nod -> st = update1(nod -> st, x, mij, r, c, val);
    } else {
        if (nod -> dr == NULL)
            nod -> dr = new Aint1();
        nod -> dr = update1(nod -> dr, mij + 1, y, r, c, val);
    }

    return nod;
}

i64 query1 (Aint1 *nod, int x, int y, int st, int dr, int a, int b) {
    if (nod == NULL)
        return 0;

    if (st <= x && y <= dr)
        return query2(nod -> rep, 0, C - 1, a, b);

    int mij = (x + y) / 2;
    i64 ans = 0;
    if (st <= mij)
        ans = gcd2(ans, query1(nod -> st, x, mij, st, dr, a, b));
    if (mij < dr)
        ans = gcd2(ans, query1(nod -> dr, mij + 1, y, st, dr, a, b));
    return ans;
}

void init(int _R, int _C) {
    R = _R;
    C = _C;

    root = new Aint1();
}

void update(int P, int Q, long long K) {
    linupd = P;
    colupd = Q;
    root = update1(root, 0, R - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query1(root, 0, R - 1, P, U, Q, V);
}

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 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 748 ms 17040 KB Output is correct
5 Correct 571 ms 16860 KB Output is correct
6 Correct 903 ms 14724 KB Output is correct
7 Correct 954 ms 14276 KB Output is correct
8 Correct 597 ms 11156 KB Output is correct
9 Correct 1067 ms 14468 KB Output is correct
10 Correct 854 ms 14072 KB Output is correct
11 Correct 3 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1189 ms 19836 KB Output is correct
13 Correct 2792 ms 10204 KB Output is correct
14 Correct 537 ms 5752 KB Output is correct
15 Correct 3355 ms 13260 KB Output is correct
16 Correct 429 ms 22736 KB Output is correct
17 Correct 1931 ms 16692 KB Output is correct
18 Correct 3233 ms 24020 KB Output is correct
19 Correct 2640 ms 24252 KB Output is correct
20 Correct 2420 ms 23548 KB Output is correct
21 Correct 5 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 368 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 789 ms 17016 KB Output is correct
13 Correct 569 ms 16888 KB Output is correct
14 Correct 908 ms 14724 KB Output is correct
15 Correct 1026 ms 14484 KB Output is correct
16 Correct 682 ms 10984 KB Output is correct
17 Correct 1041 ms 14312 KB Output is correct
18 Correct 949 ms 14028 KB Output is correct
19 Correct 1292 ms 19968 KB Output is correct
20 Correct 2831 ms 10352 KB Output is correct
21 Correct 511 ms 5756 KB Output is correct
22 Correct 3251 ms 13212 KB Output is correct
23 Correct 552 ms 22600 KB Output is correct
24 Correct 1843 ms 16524 KB Output is correct
25 Correct 3216 ms 23980 KB Output is correct
26 Correct 2949 ms 24168 KB Output is correct
27 Correct 2697 ms 23656 KB Output is correct
28 Runtime error 4323 ms 257024 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 356 KB Output is correct
12 Correct 805 ms 17272 KB Output is correct
13 Correct 542 ms 16924 KB Output is correct
14 Correct 894 ms 14604 KB Output is correct
15 Correct 1053 ms 14388 KB Output is correct
16 Correct 563 ms 10988 KB Output is correct
17 Correct 867 ms 14456 KB Output is correct
18 Correct 907 ms 14020 KB Output is correct
19 Correct 1313 ms 19900 KB Output is correct
20 Correct 2861 ms 10172 KB Output is correct
21 Correct 507 ms 5808 KB Output is correct
22 Correct 3461 ms 13304 KB Output is correct
23 Correct 416 ms 22752 KB Output is correct
24 Correct 1767 ms 16560 KB Output is correct
25 Correct 3021 ms 24180 KB Output is correct
26 Correct 2659 ms 24208 KB Output is correct
27 Correct 2514 ms 23680 KB Output is correct
28 Runtime error 3272 ms 257024 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
29 Halted 0 ms 0 KB -