oj.uz

Submission #136840

# Submission time Handle Problem Language Result Execution time Memory
136840 2019-07-26T10:44:05 Z Juney Game (IOI13_game) C++14
63 / 100
 3503 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 * 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) {
            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 200 ms 242552 KB Output is correct
2 Correct 204 ms 242424 KB Output is correct
3 Correct 217 ms 242512 KB Output is correct
4 Correct 208 ms 242544 KB Output is correct
5 Correct 200 ms 242424 KB Output is correct
6 Correct 203 ms 242372 KB Output is correct
7 Correct 221 ms 242388 KB Output is correct
8 Correct 199 ms 242424 KB Output is correct
9 Correct 204 ms 242552 KB Output is correct
10 Correct 227 ms 242596 KB Output is correct
11 Correct 203 ms 242584 KB Output is correct
12 Correct 199 ms 242424 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 242456 KB Output is correct
2 Correct 227 ms 242544 KB Output is correct
3 Correct 211 ms 242552 KB Output is correct
4 Correct 1225 ms 246620 KB Output is correct
5 Correct 996 ms 246892 KB Output is correct
6 Correct 1315 ms 243688 KB Output is correct
7 Correct 1336 ms 243404 KB Output is correct
8 Correct 1000 ms 244216 KB Output is correct
9 Correct 1364 ms 243508 KB Output is correct
10 Correct 1247 ms 243092 KB Output is correct
11 Correct 202 ms 242424 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 242560 KB Output is correct
2 Correct 204 ms 242488 KB Output is correct
3 Correct 205 ms 242500 KB Output is correct
4 Correct 202 ms 242552 KB Output is correct
5 Correct 201 ms 242424 KB Output is correct
6 Correct 204 ms 242380 KB Output is correct
7 Correct 200 ms 242456 KB Output is correct
8 Correct 214 ms 242396 KB Output is correct
9 Correct 204 ms 242472 KB Output is correct
10 Correct 201 ms 242428 KB Output is correct
11 Correct 202 ms 242424 KB Output is correct
12 Correct 1852 ms 246616 KB Output is correct
13 Correct 3076 ms 243304 KB Output is correct
14 Correct 1012 ms 243064 KB Output is correct
15 Correct 3503 ms 243312 KB Output is correct
16 Correct 943 ms 243312 KB Output is correct
17 Correct 2074 ms 243852 KB Output is correct
18 Correct 3124 ms 243612 KB Output is correct
19 Correct 2826 ms 243936 KB Output is correct
20 Correct 2462 ms 243064 KB Output is correct
21 Correct 201 ms 242396 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 242424 KB Output is correct
2 Correct 202 ms 242424 KB Output is correct
3 Correct 213 ms 242516 KB Output is correct
4 Correct 200 ms 242484 KB Output is correct
5 Correct 200 ms 242424 KB Output is correct
6 Correct 208 ms 242424 KB Output is correct
7 Correct 221 ms 242472 KB Output is correct
8 Correct 202 ms 242520 KB Output is correct
9 Correct 205 ms 242560 KB Output is correct
10 Correct 230 ms 242600 KB Output is correct
11 Correct 203 ms 242424 KB Output is correct
12 Correct 1231 ms 246656 KB Output is correct
13 Correct 970 ms 246844 KB Output is correct
14 Correct 1287 ms 243692 KB Output is correct
15 Correct 1342 ms 243480 KB Output is correct
16 Correct 1018 ms 244148 KB Output is correct
17 Correct 1335 ms 243448 KB Output is correct
18 Correct 1204 ms 243168 KB Output is correct
19 Correct 1855 ms 246456 KB Output is correct
20 Correct 3303 ms 243308 KB Output is correct
21 Correct 1004 ms 243128 KB Output is correct
22 Correct 3490 ms 243360 KB Output is correct
23 Correct 945 ms 243192 KB Output is correct
24 Correct 2163 ms 244008 KB Output is correct
25 Correct 3026 ms 243636 KB Output is correct
26 Correct 2795 ms 243840 KB Output is correct
27 Correct 2638 ms 243144 KB Output is correct
28 Runtime error 884 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 242512 KB Output is correct
2 Correct 206 ms 242424 KB Output is correct
3 Correct 207 ms 242516 KB Output is correct
4 Correct 204 ms 242396 KB Output is correct
5 Correct 200 ms 242424 KB Output is correct
6 Correct 203 ms 242508 KB Output is correct
7 Correct 203 ms 242424 KB Output is correct
8 Correct 212 ms 242516 KB Output is correct
9 Correct 202 ms 242492 KB Output is correct
10 Correct 202 ms 242424 KB Output is correct
11 Correct 202 ms 242556 KB Output is correct
12 Correct 1236 ms 246524 KB Output is correct
13 Correct 961 ms 246776 KB Output is correct
14 Correct 1283 ms 243704 KB Output is correct
15 Correct 1337 ms 243268 KB Output is correct
16 Correct 1004 ms 244036 KB Output is correct
17 Correct 1318 ms 243424 KB Output is correct
18 Correct 1225 ms 243192 KB Output is correct
19 Correct 1848 ms 246552 KB Output is correct
20 Correct 3140 ms 243364 KB Output is correct
21 Correct 1014 ms 243240 KB Output is correct
22 Correct 3474 ms 243452 KB Output is correct
23 Correct 976 ms 243316 KB Output is correct
24 Correct 2057 ms 243996 KB Output is correct
25 Correct 3052 ms 243640 KB Output is correct
26 Correct 2686 ms 243764 KB Output is correct
27 Correct 2498 ms 243204 KB Output is correct
28 Runtime error 838 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -