oj.uz

Submission #136809

# Submission time Handle Problem Language Result Execution time Memory
136809 2019-07-26T10:07:27 Z Juney Game (IOI13_game) C++14
63 / 100
 3362 ms 164908 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 * 16];
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 66 ms 78584 KB Output is correct
2 Correct 68 ms 78584 KB Output is correct
3 Correct 68 ms 78568 KB Output is correct
4 Correct 66 ms 78584 KB Output is correct
5 Correct 67 ms 78640 KB Output is correct
6 Correct 70 ms 78716 KB Output is correct
7 Correct 66 ms 78584 KB Output is correct
8 Correct 67 ms 78588 KB Output is correct
9 Correct 67 ms 78640 KB Output is correct
10 Correct 67 ms 78584 KB Output is correct
11 Correct 68 ms 78584 KB Output is correct
12 Correct 66 ms 78584 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 78584 KB Output is correct
2 Correct 65 ms 78556 KB Output is correct
3 Correct 66 ms 78556 KB Output is correct
4 Correct 1096 ms 87152 KB Output is correct
5 Correct 837 ms 86908 KB Output is correct
6 Correct 1139 ms 84516 KB Output is correct
7 Correct 1204 ms 84220 KB Output is correct
8 Correct 861 ms 84728 KB Output is correct
9 Correct 1188 ms 84344 KB Output is correct
10 Correct 1056 ms 83852 KB Output is correct
11 Correct 67 ms 78712 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 78584 KB Output is correct
2 Correct 78 ms 78644 KB Output is correct
3 Correct 68 ms 78844 KB Output is correct
4 Correct 66 ms 78588 KB Output is correct
5 Correct 66 ms 78588 KB Output is correct
6 Correct 67 ms 78584 KB Output is correct
7 Correct 67 ms 78588 KB Output is correct
8 Correct 66 ms 78584 KB Output is correct
9 Correct 68 ms 78584 KB Output is correct
10 Correct 67 ms 78580 KB Output is correct
11 Correct 67 ms 78624 KB Output is correct
12 Correct 1742 ms 86832 KB Output is correct
13 Correct 2944 ms 83444 KB Output is correct
14 Correct 843 ms 83932 KB Output is correct
15 Correct 3294 ms 84024 KB Output is correct
16 Correct 829 ms 83608 KB Output is correct
17 Correct 2087 ms 84852 KB Output is correct
18 Correct 2972 ms 85124 KB Output is correct
19 Correct 2718 ms 85180 KB Output is correct
20 Correct 2323 ms 84696 KB Output is correct
21 Correct 66 ms 78584 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 78676 KB Output is correct
2 Correct 68 ms 78560 KB Output is correct
3 Correct 68 ms 78684 KB Output is correct
4 Correct 66 ms 78584 KB Output is correct
5 Correct 77 ms 78624 KB Output is correct
6 Correct 90 ms 78584 KB Output is correct
7 Correct 66 ms 78572 KB Output is correct
8 Correct 66 ms 78556 KB Output is correct
9 Correct 67 ms 78584 KB Output is correct
10 Correct 66 ms 78628 KB Output is correct
11 Correct 66 ms 78588 KB Output is correct
12 Correct 1158 ms 87120 KB Output is correct
13 Correct 864 ms 86924 KB Output is correct
14 Correct 1149 ms 84336 KB Output is correct
15 Correct 1406 ms 84300 KB Output is correct
16 Correct 965 ms 84752 KB Output is correct
17 Correct 1196 ms 84284 KB Output is correct
18 Correct 1081 ms 83884 KB Output is correct
19 Correct 1722 ms 86900 KB Output is correct
20 Correct 2975 ms 83244 KB Output is correct
21 Correct 868 ms 83804 KB Output is correct
22 Correct 3362 ms 83880 KB Output is correct
23 Correct 830 ms 83572 KB Output is correct
24 Correct 2016 ms 84788 KB Output is correct
25 Correct 3000 ms 85064 KB Output is correct
26 Correct 2639 ms 85172 KB Output is correct
27 Correct 2398 ms 84800 KB Output is correct
28 Runtime error 453 ms 164908 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 87 ms 78584 KB Output is correct
2 Correct 87 ms 78580 KB Output is correct
3 Correct 70 ms 78712 KB Output is correct
4 Correct 68 ms 78556 KB Output is correct
5 Correct 67 ms 78556 KB Output is correct
6 Correct 69 ms 78584 KB Output is correct
7 Correct 67 ms 78584 KB Output is correct
8 Correct 67 ms 78584 KB Output is correct
9 Correct 69 ms 78520 KB Output is correct
10 Correct 69 ms 78584 KB Output is correct
11 Correct 80 ms 78584 KB Output is correct
12 Correct 1159 ms 87080 KB Output is correct
13 Correct 983 ms 86964 KB Output is correct
14 Correct 1152 ms 84556 KB Output is correct
15 Correct 1277 ms 84216 KB Output is correct
16 Correct 868 ms 84520 KB Output is correct
17 Correct 1204 ms 84216 KB Output is correct
18 Correct 1071 ms 83960 KB Output is correct
19 Correct 1794 ms 86904 KB Output is correct
20 Correct 2907 ms 83412 KB Output is correct
21 Correct 842 ms 83960 KB Output is correct
22 Correct 3304 ms 83960 KB Output is correct
23 Correct 807 ms 83584 KB Output is correct
24 Correct 1918 ms 84884 KB Output is correct
25 Correct 3200 ms 85124 KB Output is correct
26 Correct 2637 ms 85228 KB Output is correct
27 Correct 2921 ms 84588 KB Output is correct
28 Runtime error 464 ms 164764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -