oj.uz

답안 #136823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136823 2019-07-26T10:22:27 Z Juney 게임 (IOI13_game) C++14
80 / 100
 6222 ms 256004 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 * 60];
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 * 5];

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

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 254704 KB Output is correct
2 Correct 218 ms 254712 KB Output is correct
3 Correct 227 ms 254788 KB Output is correct
4 Correct 231 ms 254940 KB Output is correct
5 Correct 212 ms 254712 KB Output is correct
6 Correct 218 ms 254720 KB Output is correct
7 Correct 213 ms 254784 KB Output is correct
8 Correct 213 ms 254768 KB Output is correct
9 Correct 216 ms 254692 KB Output is correct
10 Correct 216 ms 254824 KB Output is correct
11 Correct 217 ms 254748 KB Output is correct
12 Correct 236 ms 254664 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 254760 KB Output is correct
2 Correct 273 ms 254760 KB Output is correct
3 Correct 214 ms 254716 KB Output is correct
4 Correct 1256 ms 256000 KB Output is correct
5 Correct 986 ms 256000 KB Output is correct
6 Correct 1369 ms 256000 KB Output is correct
7 Correct 1398 ms 256000 KB Output is correct
8 Correct 1025 ms 256000 KB Output is correct
9 Correct 1346 ms 256000 KB Output is correct
10 Correct 1225 ms 256000 KB Output is correct
11 Correct 215 ms 254712 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 254740 KB Output is correct
2 Correct 217 ms 254764 KB Output is correct
3 Correct 216 ms 254680 KB Output is correct
4 Correct 214 ms 254752 KB Output is correct
5 Correct 215 ms 254840 KB Output is correct
6 Correct 215 ms 254764 KB Output is correct
7 Correct 218 ms 254844 KB Output is correct
8 Correct 236 ms 254860 KB Output is correct
9 Correct 216 ms 254716 KB Output is correct
10 Correct 215 ms 254824 KB Output is correct
11 Correct 214 ms 254684 KB Output is correct
12 Correct 1868 ms 256000 KB Output is correct
13 Correct 3139 ms 256000 KB Output is correct
14 Correct 990 ms 256000 KB Output is correct
15 Correct 3458 ms 256000 KB Output is correct
16 Correct 995 ms 256000 KB Output is correct
17 Correct 2235 ms 256000 KB Output is correct
18 Correct 3122 ms 256000 KB Output is correct
19 Correct 2742 ms 256000 KB Output is correct
20 Correct 2520 ms 256000 KB Output is correct
21 Correct 214 ms 254712 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 254708 KB Output is correct
2 Correct 252 ms 254664 KB Output is correct
3 Correct 217 ms 254840 KB Output is correct
4 Correct 214 ms 254708 KB Output is correct
5 Correct 219 ms 254712 KB Output is correct
6 Correct 219 ms 254744 KB Output is correct
7 Correct 219 ms 254888 KB Output is correct
8 Correct 222 ms 254812 KB Output is correct
9 Correct 214 ms 254840 KB Output is correct
10 Correct 215 ms 254852 KB Output is correct
11 Correct 216 ms 254704 KB Output is correct
12 Correct 1262 ms 256000 KB Output is correct
13 Correct 1053 ms 256000 KB Output is correct
14 Correct 1318 ms 256000 KB Output is correct
15 Correct 1381 ms 256000 KB Output is correct
16 Correct 1040 ms 256000 KB Output is correct
17 Correct 1342 ms 256000 KB Output is correct
18 Correct 1206 ms 256000 KB Output is correct
19 Correct 1887 ms 256000 KB Output is correct
20 Correct 3085 ms 256000 KB Output is correct
21 Correct 1002 ms 256000 KB Output is correct
22 Correct 3470 ms 256000 KB Output is correct
23 Correct 962 ms 256000 KB Output is correct
24 Correct 2074 ms 256000 KB Output is correct
25 Correct 3017 ms 256000 KB Output is correct
26 Correct 2708 ms 256000 KB Output is correct
27 Correct 2511 ms 256000 KB Output is correct
28 Correct 994 ms 256000 KB Output is correct
29 Correct 2089 ms 256000 KB Output is correct
30 Correct 6222 ms 256000 KB Output is correct
31 Correct 5829 ms 256000 KB Output is correct
32 Correct 978 ms 256000 KB Output is correct
33 Correct 1213 ms 256000 KB Output is correct
34 Correct 665 ms 256000 KB Output is correct
35 Correct 1866 ms 256000 KB Output is correct
36 Correct 3311 ms 256000 KB Output is correct
37 Correct 2862 ms 256000 KB Output is correct
38 Correct 2574 ms 256000 KB Output is correct
39 Correct 2329 ms 256000 KB Output is correct
40 Correct 280 ms 254840 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 255 ms 254728 KB Output is correct
2 Correct 215 ms 254712 KB Output is correct
3 Correct 216 ms 254844 KB Output is correct
4 Correct 216 ms 254712 KB Output is correct
5 Correct 249 ms 254740 KB Output is correct
6 Correct 216 ms 254712 KB Output is correct
7 Correct 215 ms 254712 KB Output is correct
8 Correct 214 ms 254764 KB Output is correct
9 Correct 217 ms 254768 KB Output is correct
10 Correct 213 ms 254808 KB Output is correct
11 Correct 214 ms 254724 KB Output is correct
12 Correct 1272 ms 256000 KB Output is correct
13 Correct 989 ms 256000 KB Output is correct
14 Correct 1359 ms 256000 KB Output is correct
15 Correct 1359 ms 256000 KB Output is correct
16 Correct 1044 ms 256000 KB Output is correct
17 Correct 1369 ms 256000 KB Output is correct
18 Correct 1219 ms 256000 KB Output is correct
19 Correct 1887 ms 256000 KB Output is correct
20 Correct 3052 ms 256000 KB Output is correct
21 Correct 996 ms 256000 KB Output is correct
22 Correct 3465 ms 256000 KB Output is correct
23 Correct 960 ms 256000 KB Output is correct
24 Correct 2096 ms 256000 KB Output is correct
25 Correct 3326 ms 256000 KB Output is correct
26 Correct 2798 ms 256000 KB Output is correct
27 Correct 2532 ms 256000 KB Output is correct
28 Correct 991 ms 256000 KB Output is correct
29 Correct 2091 ms 256000 KB Output is correct
30 Correct 6163 ms 256000 KB Output is correct
31 Correct 5811 ms 256000 KB Output is correct
32 Correct 980 ms 256000 KB Output is correct
33 Correct 1182 ms 256000 KB Output is correct
34 Correct 634 ms 256000 KB Output is correct
35 Correct 1916 ms 256000 KB Output is correct
36 Correct 3219 ms 256000 KB Output is correct
37 Correct 2659 ms 256000 KB Output is correct
38 Correct 2694 ms 256000 KB Output is correct
39 Runtime error 1251 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -