oj.uz

Submission #136965

# Submission time Handle Problem Language Result Execution time Memory
136965 2019-07-26T17:01:36 Z Juney Game (IOI13_game) C++14
100 / 100
 7142 ms 177184 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, data; ll val;
    CNODE() : l(0), r(0), val(0), data(-1) {}
};

int ct_sz = 1;
CNODE CT[QUERY_SIZE * 300];

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 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(CT[n].data != -1) {
            if(CT[n].data <= mid) {
                CT[n].l = ++ct_sz;
                CT[CT[n].l].data = CT[n].data, CT[CT[n].l].val = CT[n].val;
            }
            else {
                CT[n].r = ++ct_sz;
                CT[CT[n].r].data = CT[n].data, CT[CT[n].r].val = CT[n].val;
            }
            CT[n].data = -1;
        }
        if(y <= mid) {
            if(CT[n].l == 0) {
                CT[n].l = ++ct_sz;
                CT[CT[n].l].data = y, CT[CT[n].l].val = val;
            }
            else update(y, val, l, mid , CT[n].l);
        }
        else {
            if(CT[n].r == 0) {
                CT[n].r = ++ct_sz;
                CT[CT[n].r].data = y, CT[CT[n].r].val = val;
            }
            else 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;
        if(CT[n].data != -1) {
            if(c1 <= CT[n].data && CT[n].data <= c2) return CT[n].val;
            return 0;
        }
        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 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;
      ^~~
game.cpp: In constructor 'CNODE::CNODE()':
game.cpp:12:24: warning: 'CNODE::val' will be initialized after [-Wreorder]
     int l, r, data; ll val;
                        ^~~
game.cpp:12:15: warning:   'int CNODE::data' [-Wreorder]
     int l, r, data; ll val;
               ^~~~
game.cpp:13:5: warning:   when initialized here [-Wreorder]
     CNODE() : l(0), r(0), val(0), data(-1) {}
     ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 163832 KB Output is correct
2 Correct 163 ms 163832 KB Output is correct
3 Correct 137 ms 163872 KB Output is correct
4 Correct 134 ms 163868 KB Output is correct
5 Correct 135 ms 163760 KB Output is correct
6 Correct 137 ms 163844 KB Output is correct
7 Correct 154 ms 163944 KB Output is correct
8 Correct 134 ms 163800 KB Output is correct
9 Correct 143 ms 163832 KB Output is correct
10 Correct 136 ms 163960 KB Output is correct
11 Correct 136 ms 163832 KB Output is correct
12 Correct 135 ms 163804 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 163780 KB Output is correct
2 Correct 135 ms 163832 KB Output is correct
3 Correct 135 ms 163868 KB Output is correct
4 Correct 1368 ms 169724 KB Output is correct
5 Correct 1119 ms 169756 KB Output is correct
6 Correct 1432 ms 165172 KB Output is correct
7 Correct 1506 ms 165128 KB Output is correct
8 Correct 993 ms 165888 KB Output is correct
9 Correct 1514 ms 165156 KB Output is correct
10 Correct 1418 ms 164624 KB Output is correct
11 Correct 135 ms 163832 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 163860 KB Output is correct
2 Correct 137 ms 163880 KB Output is correct
3 Correct 136 ms 163832 KB Output is correct
4 Correct 137 ms 163860 KB Output is correct
5 Correct 154 ms 163960 KB Output is correct
6 Correct 138 ms 163884 KB Output is correct
7 Correct 138 ms 163916 KB Output is correct
8 Correct 140 ms 163836 KB Output is correct
9 Correct 140 ms 163832 KB Output is correct
10 Correct 166 ms 163836 KB Output is correct
11 Correct 148 ms 163832 KB Output is correct
12 Correct 2207 ms 169416 KB Output is correct
13 Correct 3142 ms 165016 KB Output is correct
14 Correct 1057 ms 164748 KB Output is correct
15 Correct 3495 ms 165044 KB Output is correct
16 Correct 1093 ms 164968 KB Output is correct
17 Correct 1848 ms 165752 KB Output is correct
18 Correct 2996 ms 165668 KB Output is correct
19 Correct 2760 ms 166036 KB Output is correct
20 Correct 2595 ms 164872 KB Output is correct
21 Correct 134 ms 163832 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 163864 KB Output is correct
2 Correct 137 ms 163804 KB Output is correct
3 Correct 137 ms 163784 KB Output is correct
4 Correct 134 ms 163832 KB Output is correct
5 Correct 136 ms 163780 KB Output is correct
6 Correct 165 ms 163832 KB Output is correct
7 Correct 161 ms 163932 KB Output is correct
8 Correct 148 ms 163936 KB Output is correct
9 Correct 173 ms 163812 KB Output is correct
10 Correct 159 ms 163844 KB Output is correct
11 Correct 178 ms 163940 KB Output is correct
12 Correct 1520 ms 169732 KB Output is correct
13 Correct 1091 ms 169712 KB Output is correct
14 Correct 1425 ms 165256 KB Output is correct
15 Correct 1502 ms 165004 KB Output is correct
16 Correct 992 ms 165804 KB Output is correct
17 Correct 1458 ms 165168 KB Output is correct
18 Correct 1390 ms 164632 KB Output is correct
19 Correct 2035 ms 169336 KB Output is correct
20 Correct 3142 ms 164952 KB Output is correct
21 Correct 1058 ms 164808 KB Output is correct
22 Correct 3505 ms 165020 KB Output is correct
23 Correct 1096 ms 164956 KB Output is correct
24 Correct 1864 ms 165792 KB Output is correct
25 Correct 3085 ms 165688 KB Output is correct
26 Correct 2723 ms 166040 KB Output is correct
27 Correct 2545 ms 164652 KB Output is correct
28 Correct 855 ms 168312 KB Output is correct
29 Correct 2041 ms 172620 KB Output is correct
30 Correct 5618 ms 165224 KB Output is correct
31 Correct 5245 ms 165376 KB Output is correct
32 Correct 971 ms 166708 KB Output is correct
33 Correct 1268 ms 166648 KB Output is correct
34 Correct 507 ms 165460 KB Output is correct
35 Correct 1437 ms 167580 KB Output is correct
36 Correct 2500 ms 167272 KB Output is correct
37 Correct 2017 ms 167444 KB Output is correct
38 Correct 2135 ms 166164 KB Output is correct
39 Correct 1756 ms 167416 KB Output is correct
40 Correct 134 ms 163960 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 163832 KB Output is correct
2 Correct 140 ms 163812 KB Output is correct
3 Correct 138 ms 163832 KB Output is correct
4 Correct 134 ms 163832 KB Output is correct
5 Correct 152 ms 163824 KB Output is correct
6 Correct 137 ms 163932 KB Output is correct
7 Correct 134 ms 163804 KB Output is correct
8 Correct 135 ms 163832 KB Output is correct
9 Correct 135 ms 163832 KB Output is correct
10 Correct 140 ms 163960 KB Output is correct
11 Correct 152 ms 163760 KB Output is correct
12 Correct 1347 ms 169552 KB Output is correct
13 Correct 1091 ms 169808 KB Output is correct
14 Correct 1590 ms 165368 KB Output is correct
15 Correct 1501 ms 165112 KB Output is correct
16 Correct 986 ms 165756 KB Output is correct
17 Correct 1506 ms 164980 KB Output is correct
18 Correct 1403 ms 164740 KB Output is correct
19 Correct 2027 ms 169468 KB Output is correct
20 Correct 3165 ms 164856 KB Output is correct
21 Correct 1059 ms 164728 KB Output is correct
22 Correct 3529 ms 165012 KB Output is correct
23 Correct 1105 ms 165116 KB Output is correct
24 Correct 1935 ms 165988 KB Output is correct
25 Correct 3073 ms 165760 KB Output is correct
26 Correct 2590 ms 165936 KB Output is correct
27 Correct 2531 ms 165136 KB Output is correct
28 Correct 764 ms 167928 KB Output is correct
29 Correct 1844 ms 172792 KB Output is correct
30 Correct 5588 ms 164960 KB Output is correct
31 Correct 5182 ms 165340 KB Output is correct
32 Correct 984 ms 166376 KB Output is correct
33 Correct 1223 ms 166904 KB Output is correct
34 Correct 432 ms 164856 KB Output is correct
35 Correct 1388 ms 167312 KB Output is correct
36 Correct 2471 ms 167160 KB Output is correct
37 Correct 2171 ms 167540 KB Output is correct
38 Correct 2269 ms 166508 KB Output is correct
39 Correct 989 ms 175124 KB Output is correct
40 Correct 2769 ms 177184 KB Output is correct
41 Correct 7142 ms 171896 KB Output is correct
42 Correct 6969 ms 171984 KB Output is correct
43 Correct 738 ms 171912 KB Output is correct
44 Correct 1388 ms 174064 KB Output is correct
45 Correct 1760 ms 175404 KB Output is correct
46 Correct 3200 ms 176168 KB Output is correct
47 Correct 3390 ms 176192 KB Output is correct
48 Correct 3322 ms 175652 KB Output is correct
49 Correct 137 ms 163960 KB Output is correct