oj.uz

Submission #136842

# Submission time Handle Problem Language Result Execution time Memory
136842 2019-07-26T10:48:31 Z Juney Game (IOI13_game) C++14
80 / 100
 6336 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 * 30];

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 206 ms 249208 KB Output is correct
2 Correct 209 ms 249196 KB Output is correct
3 Correct 208 ms 249204 KB Output is correct
4 Correct 208 ms 249180 KB Output is correct
5 Correct 208 ms 249124 KB Output is correct
6 Correct 209 ms 249136 KB Output is correct
7 Correct 205 ms 249080 KB Output is correct
8 Correct 209 ms 249208 KB Output is correct
9 Correct 224 ms 249316 KB Output is correct
10 Correct 208 ms 249300 KB Output is correct
11 Correct 208 ms 249208 KB Output is correct
12 Correct 207 ms 249176 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 249184 KB Output is correct
2 Correct 206 ms 249180 KB Output is correct
3 Correct 207 ms 249208 KB Output is correct
4 Correct 1322 ms 253432 KB Output is correct
5 Correct 994 ms 253600 KB Output is correct
6 Correct 1296 ms 250496 KB Output is correct
7 Correct 1375 ms 250088 KB Output is correct
8 Correct 1014 ms 250820 KB Output is correct
9 Correct 1330 ms 250244 KB Output is correct
10 Correct 1298 ms 249768 KB Output is correct
11 Correct 209 ms 249148 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 249292 KB Output is correct
2 Correct 213 ms 249176 KB Output is correct
3 Correct 216 ms 249300 KB Output is correct
4 Correct 207 ms 249204 KB Output is correct
5 Correct 208 ms 249180 KB Output is correct
6 Correct 214 ms 249208 KB Output is correct
7 Correct 215 ms 249208 KB Output is correct
8 Correct 206 ms 249208 KB Output is correct
9 Correct 211 ms 249084 KB Output is correct
10 Correct 215 ms 249336 KB Output is correct
11 Correct 210 ms 249224 KB Output is correct
12 Correct 1859 ms 253284 KB Output is correct
13 Correct 3176 ms 250188 KB Output is correct
14 Correct 988 ms 249740 KB Output is correct
15 Correct 3522 ms 250168 KB Output is correct
16 Correct 954 ms 249976 KB Output is correct
17 Correct 2052 ms 250576 KB Output is correct
18 Correct 3160 ms 250452 KB Output is correct
19 Correct 2887 ms 250724 KB Output is correct
20 Correct 2608 ms 249820 KB Output is correct
21 Correct 207 ms 249208 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 249160 KB Output is correct
2 Correct 208 ms 249196 KB Output is correct
3 Correct 208 ms 249168 KB Output is correct
4 Correct 212 ms 249208 KB Output is correct
5 Correct 211 ms 249208 KB Output is correct
6 Correct 209 ms 249212 KB Output is correct
7 Correct 206 ms 249092 KB Output is correct
8 Correct 206 ms 249168 KB Output is correct
9 Correct 208 ms 249236 KB Output is correct
10 Correct 207 ms 249168 KB Output is correct
11 Correct 210 ms 249264 KB Output is correct
12 Correct 1245 ms 253344 KB Output is correct
13 Correct 1037 ms 253528 KB Output is correct
14 Correct 1312 ms 250364 KB Output is correct
15 Correct 1348 ms 250044 KB Output is correct
16 Correct 1010 ms 250848 KB Output is correct
17 Correct 1397 ms 250224 KB Output is correct
18 Correct 1187 ms 249892 KB Output is correct
19 Correct 1851 ms 253484 KB Output is correct
20 Correct 3068 ms 250012 KB Output is correct
21 Correct 995 ms 249780 KB Output is correct
22 Correct 3544 ms 250080 KB Output is correct
23 Correct 951 ms 250008 KB Output is correct
24 Correct 2036 ms 250444 KB Output is correct
25 Correct 3071 ms 250504 KB Output is correct
26 Correct 2647 ms 250488 KB Output is correct
27 Correct 2504 ms 250020 KB Output is correct
28 Correct 1089 ms 252340 KB Output is correct
29 Correct 2062 ms 256000 KB Output is correct
30 Correct 6205 ms 251268 KB Output is correct
31 Correct 5901 ms 251748 KB Output is correct
32 Correct 964 ms 253544 KB Output is correct
33 Correct 1229 ms 253208 KB Output is correct
34 Correct 622 ms 251384 KB Output is correct
35 Correct 1836 ms 255032 KB Output is correct
36 Correct 3308 ms 255568 KB Output is correct
37 Correct 2674 ms 255968 KB Output is correct
38 Correct 2825 ms 254964 KB Output is correct
39 Correct 2319 ms 255468 KB Output is correct
40 Correct 208 ms 249080 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 249248 KB Output is correct
2 Correct 209 ms 249192 KB Output is correct
3 Correct 208 ms 249216 KB Output is correct
4 Correct 206 ms 249120 KB Output is correct
5 Correct 205 ms 249208 KB Output is correct
6 Correct 208 ms 249228 KB Output is correct
7 Correct 209 ms 249208 KB Output is correct
8 Correct 207 ms 249228 KB Output is correct
9 Correct 208 ms 249228 KB Output is correct
10 Correct 207 ms 249152 KB Output is correct
11 Correct 207 ms 249336 KB Output is correct
12 Correct 1253 ms 253272 KB Output is correct
13 Correct 987 ms 253816 KB Output is correct
14 Correct 1289 ms 250388 KB Output is correct
15 Correct 1360 ms 250128 KB Output is correct
16 Correct 1024 ms 250876 KB Output is correct
17 Correct 1407 ms 250292 KB Output is correct
18 Correct 1253 ms 249800 KB Output is correct
19 Correct 1906 ms 253536 KB Output is correct
20 Correct 3087 ms 250148 KB Output is correct
21 Correct 991 ms 249744 KB Output is correct
22 Correct 3504 ms 250196 KB Output is correct
23 Correct 965 ms 249976 KB Output is correct
24 Correct 2097 ms 250484 KB Output is correct
25 Correct 3071 ms 250236 KB Output is correct
26 Correct 2814 ms 250480 KB Output is correct
27 Correct 2516 ms 250056 KB Output is correct
28 Correct 1084 ms 252280 KB Output is correct
29 Correct 2057 ms 256000 KB Output is correct
30 Correct 6336 ms 251372 KB Output is correct
31 Correct 6071 ms 251568 KB Output is correct
32 Correct 950 ms 253336 KB Output is correct
33 Correct 1163 ms 253288 KB Output is correct
34 Correct 707 ms 251484 KB Output is correct
35 Correct 1869 ms 255280 KB Output is correct
36 Correct 3174 ms 255880 KB Output is correct
37 Correct 2741 ms 255408 KB Output is correct
38 Correct 2617 ms 254720 KB Output is correct
39 Runtime error 1540 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -