oj.uz

Submission #136958

# Submission time Handle Problem Language Result Execution time Memory
136958 2019-07-26T16:39:15 Z Juney Game (IOI13_game) C++14
80 / 100
 6071 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

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

typedef long long ll;

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 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);
        }
        ll nval = gcd(cdst.query(y, y, RT[RT[n].l].get_root()), cdst.query(y, y, RT[RT[n].r].get_root()));
        cdst.update(y, nval, RT[n].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 206 ms 249936 KB Output is correct
2 Correct 250 ms 249984 KB Output is correct
3 Correct 241 ms 249952 KB Output is correct
4 Correct 228 ms 249952 KB Output is correct
5 Correct 204 ms 249948 KB Output is correct
6 Correct 209 ms 250044 KB Output is correct
7 Correct 205 ms 249880 KB Output is correct
8 Correct 210 ms 249944 KB Output is correct
9 Correct 208 ms 249976 KB Output is correct
10 Correct 208 ms 249976 KB Output is correct
11 Correct 208 ms 249976 KB Output is correct
12 Correct 205 ms 249976 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 249928 KB Output is correct
2 Correct 206 ms 249984 KB Output is correct
3 Correct 207 ms 249956 KB Output is correct
4 Correct 1528 ms 256000 KB Output is correct
5 Correct 1208 ms 256000 KB Output is correct
6 Correct 1547 ms 255620 KB Output is correct
7 Correct 1600 ms 255520 KB Output is correct
8 Correct 1166 ms 255836 KB Output is correct
9 Correct 1595 ms 255756 KB Output is correct
10 Correct 1517 ms 255444 KB Output is correct
11 Correct 205 ms 249976 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 249964 KB Output is correct
2 Correct 208 ms 249884 KB Output is correct
3 Correct 208 ms 249908 KB Output is correct
4 Correct 206 ms 250024 KB Output is correct
5 Correct 206 ms 249976 KB Output is correct
6 Correct 210 ms 250068 KB Output is correct
7 Correct 205 ms 249948 KB Output is correct
8 Correct 205 ms 249976 KB Output is correct
9 Correct 210 ms 249872 KB Output is correct
10 Correct 208 ms 249948 KB Output is correct
11 Correct 214 ms 250052 KB Output is correct
12 Correct 2118 ms 256000 KB Output is correct
13 Correct 3096 ms 254724 KB Output is correct
14 Correct 1104 ms 255224 KB Output is correct
15 Correct 3461 ms 255148 KB Output is correct
16 Correct 1153 ms 254864 KB Output is correct
17 Correct 2078 ms 256000 KB Output is correct
18 Correct 3232 ms 256000 KB Output is correct
19 Correct 2858 ms 256000 KB Output is correct
20 Correct 2742 ms 255984 KB Output is correct
21 Correct 205 ms 249980 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 249956 KB Output is correct
2 Correct 208 ms 249976 KB Output is correct
3 Correct 208 ms 249880 KB Output is correct
4 Correct 215 ms 249976 KB Output is correct
5 Correct 206 ms 249976 KB Output is correct
6 Correct 208 ms 249976 KB Output is correct
7 Correct 205 ms 249948 KB Output is correct
8 Correct 206 ms 249976 KB Output is correct
9 Correct 207 ms 249976 KB Output is correct
10 Correct 206 ms 249936 KB Output is correct
11 Correct 216 ms 250064 KB Output is correct
12 Correct 1545 ms 256000 KB Output is correct
13 Correct 1267 ms 256000 KB Output is correct
14 Correct 1552 ms 255812 KB Output is correct
15 Correct 1633 ms 255480 KB Output is correct
16 Correct 1118 ms 255712 KB Output is correct
17 Correct 1787 ms 255664 KB Output is correct
18 Correct 1504 ms 255164 KB Output is correct
19 Correct 2126 ms 256000 KB Output is correct
20 Correct 3089 ms 254688 KB Output is correct
21 Correct 1079 ms 255248 KB Output is correct
22 Correct 3492 ms 255248 KB Output is correct
23 Correct 1146 ms 255084 KB Output is correct
24 Correct 2158 ms 256000 KB Output is correct
25 Correct 3325 ms 256000 KB Output is correct
26 Correct 2934 ms 256000 KB Output is correct
27 Correct 2712 ms 255848 KB Output is correct
28 Correct 1075 ms 256000 KB Output is correct
29 Correct 2380 ms 256000 KB Output is correct
30 Correct 6062 ms 256000 KB Output is correct
31 Correct 5756 ms 256000 KB Output is correct
32 Correct 1025 ms 256000 KB Output is correct
33 Correct 1255 ms 256000 KB Output is correct
34 Correct 749 ms 256000 KB Output is correct
35 Correct 1859 ms 256000 KB Output is correct
36 Correct 3232 ms 256000 KB Output is correct
37 Correct 2776 ms 256000 KB Output is correct
38 Correct 2722 ms 256000 KB Output is correct
39 Correct 2302 ms 256000 KB Output is correct
40 Correct 203 ms 249976 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 249916 KB Output is correct
2 Correct 206 ms 249948 KB Output is correct
3 Correct 205 ms 249976 KB Output is correct
4 Correct 204 ms 249932 KB Output is correct
5 Correct 202 ms 249884 KB Output is correct
6 Correct 206 ms 249976 KB Output is correct
7 Correct 204 ms 249892 KB Output is correct
8 Correct 202 ms 249976 KB Output is correct
9 Correct 206 ms 249936 KB Output is correct
10 Correct 203 ms 249968 KB Output is correct
11 Correct 206 ms 249932 KB Output is correct
12 Correct 1503 ms 256000 KB Output is correct
13 Correct 1245 ms 256000 KB Output is correct
14 Correct 1728 ms 255872 KB Output is correct
15 Correct 1592 ms 255564 KB Output is correct
16 Correct 1112 ms 255976 KB Output is correct
17 Correct 1610 ms 255636 KB Output is correct
18 Correct 1540 ms 255276 KB Output is correct
19 Correct 2153 ms 256000 KB Output is correct
20 Correct 3124 ms 254760 KB Output is correct
21 Correct 1079 ms 255356 KB Output is correct
22 Correct 3495 ms 255256 KB Output is correct
23 Correct 1177 ms 255012 KB Output is correct
24 Correct 2126 ms 256000 KB Output is correct
25 Correct 3300 ms 256000 KB Output is correct
26 Correct 2955 ms 256000 KB Output is correct
27 Correct 2775 ms 256000 KB Output is correct
28 Correct 1104 ms 256000 KB Output is correct
29 Correct 2405 ms 256000 KB Output is correct
30 Correct 6071 ms 256000 KB Output is correct
31 Correct 5869 ms 256000 KB Output is correct
32 Correct 1038 ms 256000 KB Output is correct
33 Correct 1259 ms 256000 KB Output is correct
34 Correct 757 ms 256000 KB Output is correct
35 Correct 1950 ms 256000 KB Output is correct
36 Correct 3270 ms 256000 KB Output is correct
37 Correct 2772 ms 256000 KB Output is correct
38 Correct 2742 ms 256000 KB Output is correct
39 Runtime error 1365 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -