oj.uz

Submission #136849

# Submission time Handle Problem Language Result Execution time Memory
136849 2019-07-26T10:58:41 Z Juney Game (IOI13_game) C++14
54 / 100
 6257 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define MAX_RANGE 1000000000
#define QUERY_SIZE 22000
#define gcd(x, y) gcd2(x, y)

typedef long long ll;

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

struct CNODE {
    int l, r; ll val;
    CNODE() : l(0), r(0), val(0) {}
};

int ct_sz = 1;
CNODE CT[QUERY_SIZE * 700];
struct CDST {
    void update(int y, ll val, int l, int r, int n) {
        if(l == r) {
            CT[n].val = val;
            return;
        }
        int mid = (l + r) >> 1;
        if(y <= mid) {
            if(CT[n].l == 0) CT[n].l = ++ct_sz;
            update(y, val, l, mid , CT[n].l);
        }
        else {
            if(CT[n].r == 0) CT[n].r = ++ct_sz;
            update(y, val, mid+1, r, CT[n].r);
        }
        CT[n].val = gcd(CT[CT[n].l].val, CT[CT[n].r].val);
    }
    void update(int y, ll val, int n) {
        update(y, val, 1, MAX_RANGE, n);
    }
    ll query(int c1, int c2, int l, int r, int n) {
        if(n == 0 || r < c1 || c2 < l) return 0;
        if(c1 <= l && r <= c2) return CT[n].val;
        int mid = (l + r) >> 1;
        return gcd(query(c1, c2, l, mid, CT[n].l), query(c1, c2, mid+1, r, CT[n].r));
    }
    ll query(int c1, int c2, int n) {
        return query(c1, c2, 1, MAX_RANGE, n);
    }
} cdst;

struct RNODE {
    int l, r, croot;
    int get_root() {
        if(croot == 0) croot = ++ct_sz;
        return croot;
    }
    RNODE() : l(0), r(0), croot(0) {}
};

int rt_sz = 1;
RNODE RT[QUERY_SIZE * 45];

struct RDST {
    void mrg(int y, int n, int ln, int rn, int l=1, int r=MAX_RANGE) {
        if(ln == 0 && rn == 0) return;
        CT[n].val = gcd(CT[ln].val, CT[rn].val);
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(y <= mid) {
            if(CT[n].l == 0) CT[n].l = ++ct_sz;
            mrg(y, CT[n].l, CT[ln].l, CT[rn].l, l, mid);
        }
        else {
            if(CT[n].r == 0) CT[n].r = ++ct_sz;
            mrg(y, CT[n].r, CT[ln].r, CT[rn].r, mid+1, r);
        }
    }
    void update(int x, int y, ll val, int l=1, int r=MAX_RANGE, int n=1) {
        if(l == r) {
            cdst.update(y, val, RT[n].get_root());
            return;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) {
            if(RT[n].l == 0) RT[n].l = ++rt_sz;
            update(x, y, val, l, mid, RT[n].l);
        }
        else {
            if(RT[n].r == 0) RT[n].r = ++rt_sz;
            update(x, y, val, mid+1, r, RT[n].r);
        }
        mrg(y, RT[n].get_root(), RT[RT[n].l].get_root(), RT[RT[n].r].get_root());
    }
    ll query(int r1, int c1, int r2, int c2, int l=1, int r=MAX_RANGE, int n=1) {
        if(n == 0 || r < r1 || r2 < l) return 0;
        if(r1 <= l && r <= r2) return cdst.query(c1, c2, RT[n].get_root());
        int mid = (l + r) >> 1;
        return gcd(query(r1, c1, r2, c2, l, mid, RT[n].l), query(r1, c1, r2, c2, mid+1, r, RT[n].r));
    }
} dst;

void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    dst.update(P+1, Q+1, K);
}

long long calculate(int P, int Q, int U, int V) {
    return dst.query(P+1, Q+1, U+1, V+1);
}

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 209 ms 253048 KB Output is correct
2 Correct 212 ms 253024 KB Output is correct
3 Correct 241 ms 253108 KB Output is correct
4 Correct 283 ms 253036 KB Output is correct
5 Correct 257 ms 253168 KB Output is correct
6 Correct 266 ms 253176 KB Output is correct
7 Correct 210 ms 253176 KB Output is correct
8 Correct 210 ms 253020 KB Output is correct
9 Correct 248 ms 253048 KB Output is correct
10 Correct 255 ms 253052 KB Output is correct
11 Correct 210 ms 252964 KB Output is correct
12 Correct 211 ms 253052 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 253048 KB Output is correct
2 Correct 210 ms 253088 KB Output is correct
3 Correct 210 ms 253168 KB Output is correct
4 Correct 1263 ms 256000 KB Output is correct
5 Correct 969 ms 256000 KB Output is correct
6 Correct 1281 ms 254328 KB Output is correct
7 Correct 1343 ms 253944 KB Output is correct
8 Correct 1073 ms 254696 KB Output is correct
9 Correct 1357 ms 254124 KB Output is correct
10 Correct 1212 ms 253604 KB Output is correct
11 Correct 212 ms 253048 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 253048 KB Output is correct
2 Correct 240 ms 253016 KB Output is correct
3 Correct 210 ms 253084 KB Output is correct
4 Correct 208 ms 253080 KB Output is correct
5 Correct 210 ms 253052 KB Output is correct
6 Correct 211 ms 253148 KB Output is correct
7 Correct 209 ms 253148 KB Output is correct
8 Correct 208 ms 253176 KB Output is correct
9 Correct 211 ms 253024 KB Output is correct
10 Correct 210 ms 253188 KB Output is correct
11 Correct 233 ms 253060 KB Output is correct
12 Runtime error 1321 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 253088 KB Output is correct
2 Correct 210 ms 253156 KB Output is correct
3 Correct 210 ms 252992 KB Output is correct
4 Correct 209 ms 253016 KB Output is correct
5 Correct 209 ms 253032 KB Output is correct
6 Correct 211 ms 252984 KB Output is correct
7 Correct 208 ms 253228 KB Output is correct
8 Correct 212 ms 253164 KB Output is correct
9 Correct 210 ms 253048 KB Output is correct
10 Correct 209 ms 253048 KB Output is correct
11 Correct 209 ms 253092 KB Output is correct
12 Correct 1232 ms 256000 KB Output is correct
13 Correct 1010 ms 256000 KB Output is correct
14 Correct 1351 ms 254292 KB Output is correct
15 Correct 1337 ms 253992 KB Output is correct
16 Correct 1002 ms 254696 KB Output is correct
17 Correct 1344 ms 253988 KB Output is correct
18 Correct 1245 ms 253764 KB Output is correct
19 Correct 1852 ms 256000 KB Output is correct
20 Correct 3112 ms 253920 KB Output is correct
21 Correct 984 ms 253688 KB Output is correct
22 Correct 3492 ms 253972 KB Output is correct
23 Correct 1026 ms 253840 KB Output is correct
24 Correct 2049 ms 254568 KB Output is correct
25 Correct 3101 ms 254228 KB Output is correct
26 Correct 2701 ms 254404 KB Output is correct
27 Correct 2443 ms 253816 KB Output is correct
28 Correct 962 ms 253824 KB Output is correct
29 Correct 2033 ms 256000 KB Output is correct
30 Correct 6231 ms 253800 KB Output is correct
31 Correct 5871 ms 253904 KB Output is correct
32 Correct 1027 ms 253720 KB Output is correct
33 Correct 1163 ms 253664 KB Output is correct
34 Correct 622 ms 253928 KB Output is correct
35 Correct 1872 ms 254480 KB Output is correct
36 Correct 3586 ms 254328 KB Output is correct
37 Correct 2728 ms 254380 KB Output is correct
38 Correct 2555 ms 253748 KB Output is correct
39 Correct 2306 ms 254392 KB Output is correct
40 Correct 209 ms 253092 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 253048 KB Output is correct
2 Correct 228 ms 253048 KB Output is correct
3 Correct 246 ms 253176 KB Output is correct
4 Correct 210 ms 253048 KB Output is correct
5 Correct 242 ms 253012 KB Output is correct
6 Correct 216 ms 253036 KB Output is correct
7 Correct 209 ms 253060 KB Output is correct
8 Correct 219 ms 253024 KB Output is correct
9 Correct 212 ms 253064 KB Output is correct
10 Correct 210 ms 253132 KB Output is correct
11 Correct 210 ms 253048 KB Output is correct
12 Correct 1255 ms 256000 KB Output is correct
13 Correct 988 ms 256000 KB Output is correct
14 Correct 1279 ms 254060 KB Output is correct
15 Correct 1341 ms 254072 KB Output is correct
16 Correct 1006 ms 254892 KB Output is correct
17 Correct 1332 ms 254040 KB Output is correct
18 Correct 1198 ms 253560 KB Output is correct
19 Correct 1873 ms 256000 KB Output is correct
20 Correct 3078 ms 253808 KB Output is correct
21 Correct 993 ms 253668 KB Output is correct
22 Correct 3477 ms 254140 KB Output is correct
23 Correct 973 ms 254092 KB Output is correct
24 Correct 2109 ms 254408 KB Output is correct
25 Correct 3052 ms 254080 KB Output is correct
26 Correct 2825 ms 254384 KB Output is correct
27 Correct 2653 ms 253876 KB Output is correct
28 Correct 980 ms 253556 KB Output is correct
29 Correct 2045 ms 256000 KB Output is correct
30 Correct 6257 ms 253892 KB Output is correct
31 Correct 5854 ms 254072 KB Output is correct
32 Correct 987 ms 253676 KB Output is correct
33 Correct 1160 ms 253696 KB Output is correct
34 Correct 619 ms 253816 KB Output is correct
35 Correct 1843 ms 254420 KB Output is correct
36 Correct 3190 ms 254128 KB Output is correct
37 Correct 2650 ms 254456 KB Output is correct
38 Correct 2566 ms 253800 KB Output is correct
39 Runtime error 1548 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -