oj.uz

Submission #136828

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

#define MAX_RANGE 1000000000
#define QUERY_SIZE 250000
#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 * 60];
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);
    }
};

struct RNODE {
    int l, r, croot; CDST val;
    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 * 4];

struct RDST {
    void mrg(int y, int n, int ln, int rn, int l=1, int r=MAX_RANGE) {
        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) {
            RT[n].val.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 RT[n].val.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 213 ms 250832 KB Output is correct
2 Correct 216 ms 250896 KB Output is correct
3 Correct 214 ms 250772 KB Output is correct
4 Correct 214 ms 250872 KB Output is correct
5 Correct 217 ms 250876 KB Output is correct
6 Correct 212 ms 250856 KB Output is correct
7 Correct 211 ms 250812 KB Output is correct
8 Correct 211 ms 250816 KB Output is correct
9 Correct 240 ms 250804 KB Output is correct
10 Correct 235 ms 250836 KB Output is correct
11 Correct 210 ms 250744 KB Output is correct
12 Correct 211 ms 250860 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 250872 KB Output is correct
2 Correct 214 ms 250740 KB Output is correct
3 Correct 209 ms 250744 KB Output is correct
4 Correct 1248 ms 256000 KB Output is correct
5 Correct 987 ms 256000 KB Output is correct
6 Correct 1365 ms 254340 KB Output is correct
7 Correct 1361 ms 254116 KB Output is correct
8 Correct 1018 ms 255180 KB Output is correct
9 Correct 1364 ms 254392 KB Output is correct
10 Correct 1277 ms 253872 KB Output is correct
11 Correct 209 ms 250744 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 250872 KB Output is correct
2 Correct 210 ms 250800 KB Output is correct
3 Correct 211 ms 250776 KB Output is correct
4 Correct 210 ms 250864 KB Output is correct
5 Correct 210 ms 250744 KB Output is correct
6 Correct 214 ms 250872 KB Output is correct
7 Correct 266 ms 250896 KB Output is correct
8 Correct 219 ms 250968 KB Output is correct
9 Correct 215 ms 250948 KB Output is correct
10 Correct 212 ms 250744 KB Output is correct
11 Correct 223 ms 250976 KB Output is correct
12 Correct 1860 ms 256000 KB Output is correct
13 Correct 3100 ms 254216 KB Output is correct
14 Correct 999 ms 253888 KB Output is correct
15 Correct 3552 ms 254224 KB Output is correct
16 Correct 963 ms 254164 KB Output is correct
17 Correct 2133 ms 254832 KB Output is correct
18 Correct 3023 ms 254724 KB Output is correct
19 Correct 2780 ms 254688 KB Output is correct
20 Correct 2589 ms 253920 KB Output is correct
21 Correct 211 ms 250872 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 250872 KB Output is correct
2 Correct 210 ms 250844 KB Output is correct
3 Correct 212 ms 250876 KB Output is correct
4 Correct 211 ms 250972 KB Output is correct
5 Correct 209 ms 250768 KB Output is correct
6 Correct 210 ms 250848 KB Output is correct
7 Correct 209 ms 250872 KB Output is correct
8 Correct 234 ms 250840 KB Output is correct
9 Correct 212 ms 250872 KB Output is correct
10 Correct 211 ms 250784 KB Output is correct
11 Correct 211 ms 250948 KB Output is correct
12 Correct 1328 ms 256000 KB Output is correct
13 Correct 978 ms 256000 KB Output is correct
14 Correct 1314 ms 254288 KB Output is correct
15 Correct 1359 ms 254420 KB Output is correct
16 Correct 1091 ms 255244 KB Output is correct
17 Correct 1363 ms 254028 KB Output is correct
18 Correct 1196 ms 253996 KB Output is correct
19 Correct 1859 ms 256000 KB Output is correct
20 Correct 3104 ms 254044 KB Output is correct
21 Correct 1109 ms 253660 KB Output is correct
22 Correct 3587 ms 254096 KB Output is correct
23 Correct 979 ms 254228 KB Output is correct
24 Correct 2049 ms 254968 KB Output is correct
25 Correct 3151 ms 254432 KB Output is correct
26 Correct 2734 ms 254532 KB Output is correct
27 Correct 2516 ms 253784 KB Output is correct
28 Correct 973 ms 256000 KB Output is correct
29 Correct 2059 ms 256000 KB Output is correct
30 Correct 6476 ms 256000 KB Output is correct
31 Correct 6116 ms 256000 KB Output is correct
32 Correct 972 ms 256000 KB Output is correct
33 Correct 1220 ms 256000 KB Output is correct
34 Correct 707 ms 256000 KB Output is correct
35 Correct 1962 ms 256000 KB Output is correct
36 Correct 3217 ms 256000 KB Output is correct
37 Correct 2635 ms 256000 KB Output is correct
38 Correct 2499 ms 256000 KB Output is correct
39 Correct 2320 ms 256000 KB Output is correct
40 Correct 207 ms 250824 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 250832 KB Output is correct
2 Correct 210 ms 250868 KB Output is correct
3 Correct 211 ms 250968 KB Output is correct
4 Correct 218 ms 250872 KB Output is correct
5 Correct 215 ms 250872 KB Output is correct
6 Correct 254 ms 250816 KB Output is correct
7 Correct 268 ms 250744 KB Output is correct
8 Correct 206 ms 250872 KB Output is correct
9 Correct 240 ms 250844 KB Output is correct
10 Correct 209 ms 250820 KB Output is correct
11 Correct 207 ms 250928 KB Output is correct
12 Correct 1299 ms 256000 KB Output is correct
13 Correct 974 ms 256000 KB Output is correct
14 Correct 1313 ms 254160 KB Output is correct
15 Correct 1321 ms 253716 KB Output is correct
16 Correct 994 ms 254840 KB Output is correct
17 Correct 1338 ms 254056 KB Output is correct
18 Correct 1183 ms 253308 KB Output is correct
19 Correct 1874 ms 256000 KB Output is correct
20 Correct 3159 ms 253656 KB Output is correct
21 Correct 1012 ms 253380 KB Output is correct
22 Correct 3488 ms 253616 KB Output is correct
23 Correct 956 ms 253712 KB Output is correct
24 Correct 2061 ms 254308 KB Output is correct
25 Correct 3134 ms 254272 KB Output is correct
26 Correct 2738 ms 254216 KB Output is correct
27 Correct 2435 ms 253692 KB Output is correct
28 Correct 1058 ms 256000 KB Output is correct
29 Correct 2111 ms 256000 KB Output is correct
30 Correct 6183 ms 256000 KB Output is correct
31 Correct 5876 ms 256000 KB Output is correct
32 Correct 976 ms 256000 KB Output is correct
33 Correct 1203 ms 256000 KB Output is correct
34 Correct 617 ms 256000 KB Output is correct
35 Correct 1936 ms 256000 KB Output is correct
36 Correct 3357 ms 256000 KB Output is correct
37 Correct 2592 ms 256000 KB Output is correct
38 Correct 2634 ms 256000 KB Output is correct
39 Runtime error 1523 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -