oj.uz

Submission #136818

# Submission time Handle Problem Language Result Execution time Memory
136818 2019-07-26T10:15:59 Z Juney Game (IOI13_game) C++14
63 / 100
 3402 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define MAX_RANGE 1000000000
#define QUERY_SIZE 250000
#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 * 30];
struct CDST {
    int root = 0;
    int get_root() {
        if(root == 0) root = ++ct_sz;
        return root;
    }
    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);
    }
};

struct RNODE {
    int l, r, croot; CDST val;
    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) {
            RT[n].val.update(y, val, RT[n].val.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].val.get_root(), RT[RT[n].l].val.get_root(), RT[RT[n].r].val.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 RT[n].val.query(c1, c2, RT[n].val.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 113 ms 133368 KB Output is correct
2 Correct 118 ms 133436 KB Output is correct
3 Correct 116 ms 133500 KB Output is correct
4 Correct 113 ms 133364 KB Output is correct
5 Correct 115 ms 133420 KB Output is correct
6 Correct 115 ms 133388 KB Output is correct
7 Correct 113 ms 133372 KB Output is correct
8 Correct 122 ms 133396 KB Output is correct
9 Correct 115 ms 133416 KB Output is correct
10 Correct 113 ms 133368 KB Output is correct
11 Correct 113 ms 133436 KB Output is correct
12 Correct 116 ms 133340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 133368 KB Output is correct
2 Correct 113 ms 133368 KB Output is correct
3 Correct 113 ms 133332 KB Output is correct
4 Correct 1136 ms 138616 KB Output is correct
5 Correct 867 ms 138988 KB Output is correct
6 Correct 1186 ms 135672 KB Output is correct
7 Correct 1237 ms 135488 KB Output is correct
8 Correct 907 ms 136568 KB Output is correct
9 Correct 1243 ms 135720 KB Output is correct
10 Correct 1104 ms 135164 KB Output is correct
11 Correct 111 ms 133388 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 133368 KB Output is correct
2 Correct 114 ms 133468 KB Output is correct
3 Correct 121 ms 133384 KB Output is correct
4 Correct 112 ms 133368 KB Output is correct
5 Correct 113 ms 133380 KB Output is correct
6 Correct 113 ms 133496 KB Output is correct
7 Correct 112 ms 133368 KB Output is correct
8 Correct 112 ms 133496 KB Output is correct
9 Correct 114 ms 133384 KB Output is correct
10 Correct 114 ms 133372 KB Output is correct
11 Correct 137 ms 133368 KB Output is correct
12 Correct 1747 ms 138856 KB Output is correct
13 Correct 3004 ms 135544 KB Output is correct
14 Correct 893 ms 135344 KB Output is correct
15 Correct 3344 ms 135492 KB Output is correct
16 Correct 848 ms 135400 KB Output is correct
17 Correct 1902 ms 136056 KB Output is correct
18 Correct 2847 ms 135720 KB Output is correct
19 Correct 2554 ms 135768 KB Output is correct
20 Correct 2323 ms 135376 KB Output is correct
21 Correct 112 ms 133368 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 133376 KB Output is correct
2 Correct 114 ms 133416 KB Output is correct
3 Correct 133 ms 133496 KB Output is correct
4 Correct 126 ms 133500 KB Output is correct
5 Correct 112 ms 133368 KB Output is correct
6 Correct 119 ms 133424 KB Output is correct
7 Correct 112 ms 133368 KB Output is correct
8 Correct 112 ms 133384 KB Output is correct
9 Correct 113 ms 133480 KB Output is correct
10 Correct 112 ms 133424 KB Output is correct
11 Correct 112 ms 133496 KB Output is correct
12 Correct 1179 ms 138824 KB Output is correct
13 Correct 892 ms 138996 KB Output is correct
14 Correct 1177 ms 135788 KB Output is correct
15 Correct 1270 ms 135536 KB Output is correct
16 Correct 925 ms 136124 KB Output is correct
17 Correct 1395 ms 135564 KB Output is correct
18 Correct 1188 ms 135172 KB Output is correct
19 Correct 1718 ms 138740 KB Output is correct
20 Correct 2944 ms 135508 KB Output is correct
21 Correct 883 ms 135160 KB Output is correct
22 Correct 3395 ms 135500 KB Output is correct
23 Correct 852 ms 135416 KB Output is correct
24 Correct 1937 ms 135888 KB Output is correct
25 Correct 2938 ms 135672 KB Output is correct
26 Correct 2605 ms 135892 KB Output is correct
27 Correct 2370 ms 135152 KB Output is correct
28 Runtime error 1008 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 112 ms 133368 KB Output is correct
2 Correct 120 ms 133352 KB Output is correct
3 Correct 114 ms 133416 KB Output is correct
4 Correct 113 ms 133348 KB Output is correct
5 Correct 112 ms 133432 KB Output is correct
6 Correct 114 ms 133372 KB Output is correct
7 Correct 112 ms 133368 KB Output is correct
8 Correct 112 ms 133440 KB Output is correct
9 Correct 113 ms 133368 KB Output is correct
10 Correct 112 ms 133444 KB Output is correct
11 Correct 113 ms 133336 KB Output is correct
12 Correct 1170 ms 138332 KB Output is correct
13 Correct 866 ms 138692 KB Output is correct
14 Correct 1211 ms 135428 KB Output is correct
15 Correct 1559 ms 134948 KB Output is correct
16 Correct 916 ms 135788 KB Output is correct
17 Correct 1278 ms 135204 KB Output is correct
18 Correct 1095 ms 134692 KB Output is correct
19 Correct 1746 ms 138232 KB Output is correct
20 Correct 2946 ms 135044 KB Output is correct
21 Correct 894 ms 134776 KB Output is correct
22 Correct 3402 ms 135008 KB Output is correct
23 Correct 932 ms 135060 KB Output is correct
24 Correct 2117 ms 135740 KB Output is correct
25 Correct 3022 ms 135400 KB Output is correct
26 Correct 2689 ms 135316 KB Output is correct
27 Correct 2363 ms 134976 KB Output is correct
28 Runtime error 1014 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -