oj.uz

Submission #265209

# Submission time Handle Problem Language Result Execution time Memory
265209 2020-08-14T13:58:27 Z evpipis Game (IOI13_game) C++11
100 / 100
 9872 ms 57020 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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