oj.uz

Submission #136837

# Submission time Handle Problem Language Result Execution time Memory
136837 2019-07-26T10:40:30 Z Juney Game (IOI13_game) C++14
63 / 100
 3511 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 * 600];
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 174 ms 208028 KB Output is correct
2 Correct 173 ms 207992 KB Output is correct
3 Correct 173 ms 207992 KB Output is correct
4 Correct 171 ms 208120 KB Output is correct
5 Correct 175 ms 208120 KB Output is correct
6 Correct 173 ms 207992 KB Output is correct
7 Correct 210 ms 208056 KB Output is correct
8 Correct 193 ms 207964 KB Output is correct
9 Correct 174 ms 208072 KB Output is correct
10 Correct 179 ms 208116 KB Output is correct
11 Correct 173 ms 207960 KB Output is correct
12 Correct 173 ms 207964 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 207960 KB Output is correct
2 Correct 172 ms 208032 KB Output is correct
3 Correct 171 ms 207992 KB Output is correct
4 Correct 1243 ms 213084 KB Output is correct
5 Correct 945 ms 213612 KB Output is correct
6 Correct 1226 ms 209112 KB Output is correct
7 Correct 1337 ms 209080 KB Output is correct
8 Correct 977 ms 209708 KB Output is correct
9 Correct 1607 ms 209072 KB Output is correct
10 Correct 1180 ms 208700 KB Output is correct
11 Correct 171 ms 207992 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 207964 KB Output is correct
2 Correct 175 ms 208000 KB Output is correct
3 Correct 174 ms 208152 KB Output is correct
4 Correct 172 ms 207980 KB Output is correct
5 Correct 172 ms 208092 KB Output is correct
6 Correct 174 ms 207976 KB Output is correct
7 Correct 172 ms 208128 KB Output is correct
8 Correct 173 ms 207944 KB Output is correct
9 Correct 174 ms 208068 KB Output is correct
10 Correct 173 ms 208060 KB Output is correct
11 Correct 206 ms 208172 KB Output is correct
12 Correct 1841 ms 213372 KB Output is correct
13 Correct 3040 ms 208876 KB Output is correct
14 Correct 959 ms 208592 KB Output is correct
15 Correct 3490 ms 208896 KB Output is correct
16 Correct 920 ms 208760 KB Output is correct
17 Correct 2055 ms 209468 KB Output is correct
18 Correct 3045 ms 209256 KB Output is correct
19 Correct 2734 ms 209340 KB Output is correct
20 Correct 2574 ms 208820 KB Output is correct
21 Correct 171 ms 208076 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 208032 KB Output is correct
2 Correct 174 ms 207952 KB Output is correct
3 Correct 177 ms 207992 KB Output is correct
4 Correct 174 ms 208044 KB Output is correct
5 Correct 171 ms 208124 KB Output is correct
6 Correct 173 ms 208024 KB Output is correct
7 Correct 174 ms 208080 KB Output is correct
8 Correct 171 ms 208052 KB Output is correct
9 Correct 172 ms 207996 KB Output is correct
10 Correct 174 ms 207980 KB Output is correct
11 Correct 172 ms 207940 KB Output is correct
12 Correct 1195 ms 213312 KB Output is correct
13 Correct 934 ms 213608 KB Output is correct
14 Correct 1302 ms 209100 KB Output is correct
15 Correct 1289 ms 209112 KB Output is correct
16 Correct 985 ms 209804 KB Output is correct
17 Correct 1295 ms 209036 KB Output is correct
18 Correct 1156 ms 208644 KB Output is correct
19 Correct 1827 ms 213472 KB Output is correct
20 Correct 3042 ms 208960 KB Output is correct
21 Correct 952 ms 208728 KB Output is correct
22 Correct 3511 ms 208908 KB Output is correct
23 Correct 920 ms 208860 KB Output is correct
24 Correct 2049 ms 209376 KB Output is correct
25 Correct 3024 ms 209088 KB Output is correct
26 Correct 2726 ms 209320 KB Output is correct
27 Correct 2397 ms 208724 KB Output is correct
28 Runtime error 755 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 173 ms 207992 KB Output is correct
2 Correct 206 ms 207992 KB Output is correct
3 Correct 176 ms 207940 KB Output is correct
4 Correct 173 ms 208036 KB Output is correct
5 Correct 172 ms 207992 KB Output is correct
6 Correct 174 ms 208060 KB Output is correct
7 Correct 173 ms 208044 KB Output is correct
8 Correct 173 ms 207944 KB Output is correct
9 Correct 176 ms 207932 KB Output is correct
10 Correct 173 ms 208080 KB Output is correct
11 Correct 172 ms 208020 KB Output is correct
12 Correct 1198 ms 213008 KB Output is correct
13 Correct 950 ms 213444 KB Output is correct
14 Correct 1294 ms 209236 KB Output is correct
15 Correct 1332 ms 208948 KB Output is correct
16 Correct 974 ms 209656 KB Output is correct
17 Correct 1320 ms 208892 KB Output is correct
18 Correct 1200 ms 208796 KB Output is correct
19 Correct 1840 ms 212960 KB Output is correct
20 Correct 3051 ms 208860 KB Output is correct
21 Correct 956 ms 208740 KB Output is correct
22 Correct 3498 ms 208908 KB Output is correct
23 Correct 951 ms 209004 KB Output is correct
24 Correct 2031 ms 209448 KB Output is correct
25 Correct 3044 ms 209204 KB Output is correct
26 Correct 2739 ms 209244 KB Output is correct
27 Correct 2453 ms 208736 KB Output is correct
28 Runtime error 741 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -