oj.uz

Submission #60764

# Submission time Handle Problem Language Result Execution time Memory
60764 2018-07-24T16:11:30 Z aome Game (IOI13_game) C++14
63 / 100
 3045 ms 257024 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define mid ((l + r) >> 1)

struct NodeY {
    long long gcd;
    NodeY *l, *r;

    NodeY() : l(NULL), r(NULL), gcd(0) {}
};

struct NodeX {
    int l, r;
    NodeY *v;

    NodeX() : l(0), r(0), v(NULL) {}
} a[70005];

int cnt = 1;
int R, C;
int P, Q, U, V;
long long K;
long long res;

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

void getY(NodeY *i, int l, int r) {
    if (!i) return;
    if (l > V || U > r) return;
    if (U <= l && r <= V) {
        res = __gcd(res, i -> gcd); return;
    }
    getY(i -> l, l, mid);
    getY(i -> r, mid + 1, r);
}

void getX(int i, int l, int r) {
    if (!i) return;
    if (l > Q || P > r) return;
    if (P <= l && r <= Q) {
        getY(a[i].v, 0, C - 1); return;
    }
    getX(a[i].l, l, mid);
    getX(a[i].r, mid + 1, r);
}

void updateY(NodeY *i, int l, int r) {
    if (l == r) {
        i -> gcd = K; return;
    }
    if (mid >= Q) {
        if (!(i -> l)) i -> l = new NodeY();
        updateY(i -> l, l, mid);
    }
    else {
        if (!(i -> r)) i -> r = new NodeY();
        updateY(i -> r, mid + 1, r);
    }
    long long vl = (!(i -> l) ? 0 : i -> l -> gcd);
    long long vr = (!(i -> r) ? 0 : i -> r -> gcd);
    i -> gcd = __gcd(vl, vr);
}

void updateX(int i, int l, int r) {
    if (l == r) {
        if (!(a[i].v)) a[i].v = new NodeY();
        updateY(a[i].v, 0, C - 1); 
        return;
    }
    if (mid >= P) {
        if (!(a[i].l)) a[i].l = ++cnt;
        updateX(a[i].l, l, mid);
        res = 0;
        if (a[i].r) {
            getY(a[a[i].r].v, 0, C - 1);
        }
        K = __gcd(K, res);
    }
    else {
        if (!(a[i].r)) a[i].r = ++cnt;
        updateX(a[i].r, mid + 1, r);
        res = 0;
        if (a[i].l) {
            getY(a[a[i].l].v, 0, C - 1);
        }
        K = __gcd(K, res);
    }
    if (!(a[i].v)) a[i].v = new NodeY();
    updateY(a[i].v, 0, C - 1);
}

void update(int _P, int _Q, long long _K) {
    P = _P, Q = U = V = _Q, K = _K;
    updateX(1, 0, R - 1);
}

long long calculate(int _P, int _U, int _Q, int _V) {
    res = 0;
    P = _P, Q = _Q, U = _U, V = _V;
    getX(1, 0, R - 1);
    return res;
}

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;
      ^~~
game.cpp: In constructor 'NodeY::NodeY()':
game.cpp:10:16: warning: 'NodeY::r' will be initialized after [-Wreorder]
     NodeY *l, *r;
                ^
game.cpp:9:15: warning:   'long long int NodeY::gcd' [-Wreorder]
     long long gcd;
               ^~~
game.cpp:12:5: warning:   when initialized here [-Wreorder]
     NodeY() : l(NULL), r(NULL), gcd(0) {}
     ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1400 KB Output is correct
2 Correct 4 ms 1684 KB Output is correct
3 Correct 5 ms 1684 KB Output is correct
4 Correct 3 ms 1684 KB Output is correct
5 Correct 4 ms 1684 KB Output is correct
6 Correct 5 ms 1684 KB Output is correct
7 Correct 5 ms 1684 KB Output is correct
8 Correct 4 ms 1684 KB Output is correct
9 Correct 5 ms 1744 KB Output is correct
10 Correct 4 ms 1748 KB Output is correct
11 Correct 4 ms 1748 KB Output is correct
12 Correct 3 ms 1748 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1784 KB Output is correct
2 Correct 4 ms 1784 KB Output is correct
3 Correct 4 ms 1784 KB Output is correct
4 Correct 998 ms 18440 KB Output is correct
5 Correct 714 ms 22724 KB Output is correct
6 Correct 876 ms 24276 KB Output is correct
7 Correct 1069 ms 28692 KB Output is correct
8 Correct 624 ms 29976 KB Output is correct
9 Correct 1060 ms 37696 KB Output is correct
10 Correct 904 ms 41876 KB Output is correct
11 Correct 4 ms 41876 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 41876 KB Output is correct
2 Correct 4 ms 41876 KB Output is correct
3 Correct 4 ms 41876 KB Output is correct
4 Correct 4 ms 41876 KB Output is correct
5 Correct 5 ms 41876 KB Output is correct
6 Correct 5 ms 41876 KB Output is correct
7 Correct 4 ms 41876 KB Output is correct
8 Correct 4 ms 41876 KB Output is correct
9 Correct 5 ms 41876 KB Output is correct
10 Correct 5 ms 41876 KB Output is correct
11 Correct 5 ms 41876 KB Output is correct
12 Correct 2035 ms 52608 KB Output is correct
13 Correct 2898 ms 52608 KB Output is correct
14 Correct 364 ms 52608 KB Output is correct
15 Correct 2967 ms 58388 KB Output is correct
16 Correct 436 ms 72136 KB Output is correct
17 Correct 1617 ms 72136 KB Output is correct
18 Correct 3045 ms 82836 KB Output is correct
19 Correct 2687 ms 88208 KB Output is correct
20 Correct 2413 ms 92928 KB Output is correct
21 Correct 4 ms 92928 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 92928 KB Output is correct
2 Correct 5 ms 92928 KB Output is correct
3 Correct 5 ms 92928 KB Output is correct
4 Correct 4 ms 92928 KB Output is correct
5 Correct 5 ms 92928 KB Output is correct
6 Correct 6 ms 92928 KB Output is correct
7 Correct 4 ms 92928 KB Output is correct
8 Correct 4 ms 92928 KB Output is correct
9 Correct 5 ms 92928 KB Output is correct
10 Correct 5 ms 92928 KB Output is correct
11 Correct 4 ms 92928 KB Output is correct
12 Correct 1089 ms 92928 KB Output is correct
13 Correct 814 ms 96224 KB Output is correct
14 Correct 981 ms 97788 KB Output is correct
15 Correct 1148 ms 102096 KB Output is correct
16 Correct 642 ms 103532 KB Output is correct
17 Correct 1165 ms 111292 KB Output is correct
18 Correct 937 ms 115340 KB Output is correct
19 Correct 1853 ms 125844 KB Output is correct
20 Correct 2696 ms 125844 KB Output is correct
21 Correct 429 ms 125844 KB Output is correct
22 Correct 2868 ms 131868 KB Output is correct
23 Correct 363 ms 145564 KB Output is correct
24 Correct 1633 ms 145564 KB Output is correct
25 Correct 3043 ms 156020 KB Output is correct
26 Correct 2631 ms 161520 KB Output is correct
27 Correct 2427 ms 166172 KB Output is correct
28 Runtime error 564 ms 257024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -