답안 #265209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
265209	2020-08-14T13:58:27 Z	evpipis	게임 (IOI13_game)	C++11	100 / 100	9872 ms	57020 KB

game

#include "game.h"

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;
const int inf = 1e9+10;

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 treap{
    struct node{
        ii pos;
        int prior;
        ll val, res;
        node *lef, *rig;

        node(ii p = mp(0, 0), ll v = 0){
            pos = p;
            prior = rand();
            val = v;
            res = v;

            lef = NULL;
            rig = NULL;
        }
    };

    // try using my own null
    typedef node *pnode;
    pnode root;

    treap(){
        root = NULL;
    }

    void upd(pnode t){
        if (t == NULL)
            return;

        t->res = t->val;
        if (t->lef != NULL)
            t->res = gcd2(t->res, t->lef->res);
        if (t->rig != NULL)
            t->res = gcd2(t->res, t->rig->res);
    }

    void split(pnode t, pnode &l, pnode &r, ii k){
        if (t == NULL)
            return void(l = r = NULL);

        if (t->pos <= k)
            split(t->rig, t->rig, r, k), l = t;
        else
            split(t->lef, l, t->lef, k), r = t;

        upd(t);
    }

    void join(pnode &t, pnode l, pnode r){
        if (l == NULL)
            return void(t = r);
        if (r == NULL)
            return void(t = l);

        if (l->prior > r->prior)
            join(l->rig, l->rig, r), t = l;
        else
            join(r->lef, l, r->lef), t = r;

        upd(t);
    }

    void add(ii p, ll v){
        pnode l = NULL, mid = NULL, r = NULL;

        split(root, l, r, p);
        split(l, l, mid, mp(p.fi, p.se-1));

        mid = new node(p, v);

        join(l, l, mid);
        join(root, l, r);
    }

    ll ask(int a, int b){
        pnode l = NULL, mid = NULL, r = NULL;

        split(root, l, r, mp(b, inf));
        split(l, l, mid, mp(a-1, inf));

        ll ans = 0;
        if (mid != NULL)
            ans = mid->res;

        join(l, l, mid);
        join(root, l, r);

        return ans;
    }
};

struct seg_tree{
    struct node{
        treap tree;
        node *lef, *rig;

        node(node *l = NULL, node *r = NULL){
            tree = treap();

            lef = l;
            rig = r;
        }
    };

    typedef node *pnode;
    pnode root, null;
    int mx;

    seg_tree(int m = 0){
        null = new node();
        null->lef = null->rig = null;
        root = null;
        mx = m;
    }

    pnode update(pnode t, int l, int r, int i, int j, ll v){
        if (t == null)
            t = new node(null, null);
        t->tree.add(mp(j, i), v);

        if (l == r)
            return t;

        int mid = (l+r)/2;
        if (i <= mid)
            t->lef = update(t->lef, l, mid, i, j, v);
        else
            t->rig = update(t->rig, mid+1, r, i, j, v);
        return t;
    }

    void add(int r, int c, ll v){
        root = update(root, 0, mx-1, r, c, v);
    }

    ll query(pnode t, int l, int r, int i, int j, int a, int b){
        if (r < i || j < l)
            return 0;
        if (i <= l && r <= j)
            return t->tree.ask(a, b);

        int mid = (l+r)/2;
        return gcd2(query(t->lef, l, mid, i, j, a, b), query(t->rig, mid+1, r, i, j, a, b));
    }

    ll ask(int ar, int br, int ac, int bc){
        return query(root, 0, mx-1, ar, br, ac, bc);
    }
};

seg_tree data;

void init(int R, int C) {
    data = seg_tree(R);
}

void update(int P, int Q, long long K) {
    data.add(P, Q, K);
}

long long calculate(int ar, int ac, int br, int bc) {
    return data.ask(ar, br, ac, bc);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	416 KB	Output is correct
4	Correct	1044 ms	7192 KB	Output is correct
5	Correct	438 ms	7416 KB	Output is correct
6	Correct	1397 ms	4220 KB	Output is correct
7	Correct	1537 ms	3976 KB	Output is correct
8	Correct	1045 ms	3280 KB	Output is correct
9	Correct	1497 ms	4088 KB	Output is correct
10	Correct	1332 ms	3576 KB	Output is correct
11	Correct	1 ms	256 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1661 ms	11688 KB	Output is correct
13	Correct	4542 ms	8104 KB	Output is correct
14	Correct	756 ms	8684 KB	Output is correct
15	Correct	4661 ms	8648 KB	Output is correct
16	Correct	570 ms	8748 KB	Output is correct
17	Correct	2282 ms	5368 KB	Output is correct
18	Correct	4556 ms	8952 KB	Output is correct
19	Correct	3727 ms	9176 KB	Output is correct
20	Correct	3689 ms	8580 KB	Output is correct
21	Correct	1 ms	256 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1032 ms	7288 KB	Output is correct
13	Correct	453 ms	7416 KB	Output is correct
14	Correct	1441 ms	4376 KB	Output is correct
15	Correct	1651 ms	4004 KB	Output is correct
16	Correct	1111 ms	3428 KB	Output is correct
17	Correct	1576 ms	4092 KB	Output is correct
18	Correct	1362 ms	3736 KB	Output is correct
19	Correct	1739 ms	11304 KB	Output is correct
20	Correct	4522 ms	7928 KB	Output is correct
21	Correct	838 ms	8416 KB	Output is correct
22	Correct	4706 ms	8772 KB	Output is correct
23	Correct	562 ms	8696 KB	Output is correct
24	Correct	2394 ms	5472 KB	Output is correct
25	Correct	4548 ms	9088 KB	Output is correct
26	Correct	3524 ms	9168 KB	Output is correct
27	Correct	3530 ms	8752 KB	Output is correct
28	Correct	1710 ms	26092 KB	Output is correct
29	Correct	2576 ms	28928 KB	Output is correct
30	Correct	6245 ms	23412 KB	Output is correct
31	Correct	5710 ms	22896 KB	Output is correct
32	Correct	1272 ms	20332 KB	Output is correct
33	Correct	1593 ms	20452 KB	Output is correct
34	Correct	585 ms	26104 KB	Output is correct
35	Correct	2920 ms	14164 KB	Output is correct
36	Correct	5298 ms	26440 KB	Output is correct
37	Correct	4451 ms	26652 KB	Output is correct
38	Correct	4440 ms	26248 KB	Output is correct
39	Correct	3509 ms	20980 KB	Output is correct
40	Correct	1 ms	256 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1057 ms	7132 KB	Output is correct
13	Correct	459 ms	7544 KB	Output is correct
14	Correct	1477 ms	4388 KB	Output is correct
15	Correct	1580 ms	3960 KB	Output is correct
16	Correct	1048 ms	3448 KB	Output is correct
17	Correct	1578 ms	3972 KB	Output is correct
18	Correct	1364 ms	3700 KB	Output is correct
19	Correct	1694 ms	11512 KB	Output is correct
20	Correct	4538 ms	8000 KB	Output is correct
21	Correct	781 ms	8492 KB	Output is correct
22	Correct	4860 ms	8728 KB	Output is correct
23	Correct	541 ms	8696 KB	Output is correct
24	Correct	2412 ms	5420 KB	Output is correct
25	Correct	4579 ms	9120 KB	Output is correct
26	Correct	3680 ms	9276 KB	Output is correct
27	Correct	3598 ms	8636 KB	Output is correct
28	Correct	1675 ms	25900 KB	Output is correct
29	Correct	2604 ms	28920 KB	Output is correct
30	Correct	6173 ms	23420 KB	Output is correct
31	Correct	5748 ms	22820 KB	Output is correct
32	Correct	1264 ms	20376 KB	Output is correct
33	Correct	1706 ms	20380 KB	Output is correct
34	Correct	564 ms	25976 KB	Output is correct
35	Correct	2977 ms	14260 KB	Output is correct
36	Correct	5514 ms	26368 KB	Output is correct
37	Correct	4162 ms	26576 KB	Output is correct
38	Correct	4460 ms	25852 KB	Output is correct
39	Correct	2205 ms	54904 KB	Output is correct
40	Correct	4388 ms	57020 KB	Output is correct
41	Correct	9872 ms	49708 KB	Output is correct
42	Correct	8848 ms	48164 KB	Output is correct
43	Correct	1008 ms	55248 KB	Output is correct
44	Correct	2029 ms	43476 KB	Output is correct
45	Correct	3681 ms	20676 KB	Output is correct
46	Correct	6965 ms	55384 KB	Output is correct
47	Correct	6725 ms	55544 KB	Output is correct
48	Correct	6655 ms	54880 KB	Output is correct
49	Correct	1 ms	256 KB	Output is correct