oj.uz

Submission #136843

# Submission time Handle Problem Language Result Execution time Memory
136843 2019-07-26T10:51:55 Z Juney Game (IOI13_game) C++14
80 / 100
 6338 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 * 33];

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) {
            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 210 ms 250104 KB Output is correct
2 Correct 243 ms 249976 KB Output is correct
3 Correct 210 ms 249976 KB Output is correct
4 Correct 208 ms 249976 KB Output is correct
5 Correct 212 ms 249972 KB Output is correct
6 Correct 210 ms 249976 KB Output is correct
7 Correct 207 ms 249912 KB Output is correct
8 Correct 209 ms 250108 KB Output is correct
9 Correct 211 ms 249976 KB Output is correct
10 Correct 209 ms 249948 KB Output is correct
11 Correct 209 ms 249976 KB Output is correct
12 Correct 254 ms 249976 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 249976 KB Output is correct
2 Correct 227 ms 249976 KB Output is correct
3 Correct 208 ms 249968 KB Output is correct
4 Correct 1296 ms 254044 KB Output is correct
5 Correct 972 ms 254336 KB Output is correct
6 Correct 1281 ms 251108 KB Output is correct
7 Correct 1350 ms 250868 KB Output is correct
8 Correct 1018 ms 251740 KB Output is correct
9 Correct 1373 ms 250992 KB Output is correct
10 Correct 1222 ms 250552 KB Output is correct
11 Correct 208 ms 249976 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 249924 KB Output is correct
2 Correct 209 ms 249912 KB Output is correct
3 Correct 208 ms 250000 KB Output is correct
4 Correct 230 ms 250036 KB Output is correct
5 Correct 210 ms 249976 KB Output is correct
6 Correct 209 ms 249936 KB Output is correct
7 Correct 207 ms 249948 KB Output is correct
8 Correct 207 ms 249992 KB Output is correct
9 Correct 207 ms 249980 KB Output is correct
10 Correct 209 ms 250032 KB Output is correct
11 Correct 207 ms 249892 KB Output is correct
12 Correct 1874 ms 254088 KB Output is correct
13 Correct 3121 ms 250744 KB Output is correct
14 Correct 993 ms 250532 KB Output is correct
15 Correct 3506 ms 250768 KB Output is correct
16 Correct 947 ms 250716 KB Output is correct
17 Correct 2028 ms 251568 KB Output is correct
18 Correct 3088 ms 251268 KB Output is correct
19 Correct 2743 ms 251384 KB Output is correct
20 Correct 2483 ms 250744 KB Output is correct
21 Correct 214 ms 250104 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 249916 KB Output is correct
2 Correct 209 ms 249976 KB Output is correct
3 Correct 207 ms 249976 KB Output is correct
4 Correct 207 ms 250004 KB Output is correct
5 Correct 207 ms 250036 KB Output is correct
6 Correct 207 ms 249892 KB Output is correct
7 Correct 225 ms 250108 KB Output is correct
8 Correct 206 ms 249976 KB Output is correct
9 Correct 210 ms 249976 KB Output is correct
10 Correct 206 ms 249976 KB Output is correct
11 Correct 210 ms 249880 KB Output is correct
12 Correct 1292 ms 254036 KB Output is correct
13 Correct 974 ms 254484 KB Output is correct
14 Correct 1270 ms 251212 KB Output is correct
15 Correct 1386 ms 250948 KB Output is correct
16 Correct 1006 ms 251744 KB Output is correct
17 Correct 1353 ms 250968 KB Output is correct
18 Correct 1256 ms 250712 KB Output is correct
19 Correct 1880 ms 254008 KB Output is correct
20 Correct 3078 ms 250796 KB Output is correct
21 Correct 985 ms 250488 KB Output is correct
22 Correct 3483 ms 250884 KB Output is correct
23 Correct 1026 ms 250872 KB Output is correct
24 Correct 2086 ms 251336 KB Output is correct
25 Correct 3365 ms 250948 KB Output is correct
26 Correct 2828 ms 251200 KB Output is correct
27 Correct 2494 ms 250692 KB Output is correct
28 Correct 968 ms 250600 KB Output is correct
29 Correct 2281 ms 255512 KB Output is correct
30 Correct 6338 ms 250660 KB Output is correct
31 Correct 5868 ms 250812 KB Output is correct
32 Correct 990 ms 250840 KB Output is correct
33 Correct 1201 ms 250628 KB Output is correct
34 Correct 659 ms 250768 KB Output is correct
35 Correct 1867 ms 251308 KB Output is correct
36 Correct 3187 ms 251096 KB Output is correct
37 Correct 2707 ms 251184 KB Output is correct
38 Correct 2680 ms 250824 KB Output is correct
39 Correct 2286 ms 251396 KB Output is correct
40 Correct 206 ms 249976 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 249948 KB Output is correct
2 Correct 211 ms 249988 KB Output is correct
3 Correct 210 ms 250020 KB Output is correct
4 Correct 206 ms 249976 KB Output is correct
5 Correct 207 ms 249896 KB Output is correct
6 Correct 210 ms 250036 KB Output is correct
7 Correct 206 ms 250004 KB Output is correct
8 Correct 219 ms 249960 KB Output is correct
9 Correct 209 ms 249976 KB Output is correct
10 Correct 213 ms 249976 KB Output is correct
11 Correct 230 ms 250012 KB Output is correct
12 Correct 1228 ms 253960 KB Output is correct
13 Correct 1070 ms 254384 KB Output is correct
14 Correct 1289 ms 251060 KB Output is correct
15 Correct 1345 ms 250980 KB Output is correct
16 Correct 1018 ms 251532 KB Output is correct
17 Correct 1339 ms 250928 KB Output is correct
18 Correct 1211 ms 250604 KB Output is correct
19 Correct 1902 ms 254148 KB Output is correct
20 Correct 3086 ms 250752 KB Output is correct
21 Correct 986 ms 250696 KB Output is correct
22 Correct 3503 ms 250972 KB Output is correct
23 Correct 943 ms 250732 KB Output is correct
24 Correct 2076 ms 251416 KB Output is correct
25 Correct 3067 ms 251208 KB Output is correct
26 Correct 2748 ms 251304 KB Output is correct
27 Correct 2464 ms 250684 KB Output is correct
28 Correct 956 ms 250544 KB Output is correct
29 Correct 2069 ms 255420 KB Output is correct
30 Correct 6317 ms 250708 KB Output is correct
31 Correct 5953 ms 250872 KB Output is correct
32 Correct 989 ms 250816 KB Output is correct
33 Correct 1159 ms 250528 KB Output is correct
34 Correct 610 ms 250752 KB Output is correct
35 Correct 1936 ms 251452 KB Output is correct
36 Correct 3203 ms 251096 KB Output is correct
37 Correct 2624 ms 251408 KB Output is correct
38 Correct 2595 ms 250672 KB Output is correct
39 Runtime error 1699 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -