oj.uz

Submission #863384

# Submission time Handle Problem Language Result Execution time Memory
863384 2023-10-20T06:33:06 Z deepaung Game (IOI13_game) C++14
100 / 100
 5378 ms 67616 KB 
#include <bits/stdc++.h>
#include "game.h"

#define f first
#define s second
#define pll pair<ll, ll>
#define ll long long

using namespace std;

mt19937 rnd(time(NULL));

ll R, C;

ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Treap {
    struct node {
        ll val, gcd, sz, pri;
        pll pos;
        node *l, *r;

        node(ll val=0, pll pos={0, 0}, node *l=NULL, node *r=NULL) : 
            val(val), gcd(val), sz(1), pri(rnd()), pos(pos), l(l), r(r) {}
    };

    node *root;

    Treap() : root(NULL) {}

    void recalc(node *cur) {
        if (cur == NULL) return;

        cur->sz = 1;
        cur->gcd = cur->val;
        if (cur->l != NULL)
            cur->sz += cur->l->sz, cur->gcd = gcd2(cur->gcd, cur->l->gcd);
        if (cur->r != NULL)
            cur->sz += cur->r->sz, cur->gcd = gcd2(cur->gcd, cur->r->gcd);
    }

    void split(node *cur, node *&left, node *&right, pll pos) {
        if (cur == NULL) {
            left = right = NULL;
            return;
        }

        if (cur->pos <= pos) {
            split(cur->r, cur->r, right, pos);
            left = cur;
        } else {
            split(cur->l, left, cur->l, pos);
            right = cur;
        }

        recalc(cur);
    }

    void merge(node *&cur, node *left, node *right) {
        if (left == NULL || right == NULL) {
            cur = (left != NULL ? left : right);
            return;
        }

        if (left->pri >= right->pri) {
            merge(left->r, left->r, right);
            cur = left;
        } else {
            merge(right->l, left, right->l);
            cur = right;
        }

        recalc(cur);
    }

    void update(ll x, ll y, ll val) {
        node *left, *mid, *right;
        split(root, left, mid, {y, x-1});
        split(mid, mid, right, {y, x});

        delete mid;

        merge(root, left, new node(val, {y, x}));
        merge(root, root, right);
    }

    ll gcd_range(ll yl, ll yr) {
        node *left, *mid, *right;
        split(root, left, mid, {yl, -1});
        split(mid, mid, right, {yr+1, -1});

        ll ans = (mid != NULL ? mid->gcd : 0);

        merge(root, left, mid);
        merge(root, root, right);

        return ans;
    }

};

struct Segtree {
    struct node {
        Treap treap;
        node *l, *r;

        node() : 
            treap(Treap()), l(NULL), r(NULL) {}
    };

    node *root;

    void update(ll x, ll y, ll val, node *&cur, ll l, ll r) {
        if (cur == NULL) cur = new node();

        cur->treap.update(x, y, val);
        if (l == r) return;

        ll mid = (l + r) >> 1;
        if (x <= mid) update(x, y, val, cur->l, l, mid);
        else update(x, y, val, cur->r, mid+1, r);
    }

    ll gcd_range(ll xl, ll yl, ll xr, ll yr, node *cur, ll l, ll r) {
        if (cur == NULL) return 0;
        if (xr < l || r < xl) return 0;

        if (xl <= l && r <= xr) {
            return cur->treap.gcd_range(yl, yr);
        }

        ll mid = (l + r) >> 1;
        ll resl = gcd_range(xl, yl, xr, yr, cur->l, l, mid);
        ll resr = gcd_range(xl, yl, xr, yr, cur->r, mid+1, r);

        return gcd2(resl, resr);

        // if (xl == l && r == xr) {
        //     return cur->treap.gcd_range(yl, yr);
        // }

        // ll mid = (l + r) >> 1;
        // if (xr <= mid) {
        //     return gcd_range(xl, yl, xr, yr, cur->l, l, mid);
        // } else if (xl >= mid + 1) {
        //     return gcd_range(xl, yl, xr, yr, cur->r, mid+1, r);
        // } else {
        //     return gcd2(
        //         gcd_range(xl, yl, mid, yr, cur->l, l, mid),
        //         gcd_range(mid+1, yl, xr, yr, cur->r, mid+1, r)
        //     );
        // }
    }

} segtree;

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

void update(int x, int y, ll val) {
    x++, y++;
    segtree.update(x, y, val, segtree.root, 1, R);
}

ll calculate(int xl, int yl, int xr, int yr) {
    xl++, yl++, xr++, yr++;
    return segtree.gcd_range(xl, yl, xr, yr, segtree.root, 1, R);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 603 ms 7872 KB Output is correct
5 Correct 278 ms 8064 KB Output is correct
6 Correct 927 ms 4964 KB Output is correct
7 Correct 1073 ms 4780 KB Output is correct
8 Correct 721 ms 3624 KB Output is correct
9 Correct 1049 ms 4832 KB Output is correct
10 Correct 918 ms 4596 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 908 ms 13280 KB Output is correct
13 Correct 2266 ms 7360 KB Output is correct
14 Correct 476 ms 1668 KB Output is correct
15 Correct 2425 ms 7984 KB Output is correct
16 Correct 345 ms 10788 KB Output is correct
17 Correct 1539 ms 6280 KB Output is correct
18 Correct 2832 ms 11188 KB Output is correct
19 Correct 2388 ms 11264 KB Output is correct
20 Correct 2309 ms 10340 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 590 ms 7764 KB Output is correct
13 Correct 249 ms 8080 KB Output is correct
14 Correct 950 ms 5016 KB Output is correct
15 Correct 1061 ms 4604 KB Output is correct
16 Correct 715 ms 3468 KB Output is correct
17 Correct 1040 ms 4552 KB Output is correct
18 Correct 927 ms 4320 KB Output is correct
19 Correct 955 ms 12908 KB Output is correct
20 Correct 2272 ms 7524 KB Output is correct
21 Correct 445 ms 1924 KB Output is correct
22 Correct 2400 ms 8128 KB Output is correct
23 Correct 339 ms 10956 KB Output is correct
24 Correct 1535 ms 6072 KB Output is correct
25 Correct 2772 ms 10988 KB Output is correct
26 Correct 2308 ms 11032 KB Output is correct
27 Correct 2311 ms 10372 KB Output is correct
28 Correct 779 ms 30672 KB Output is correct
29 Correct 1468 ms 33768 KB Output is correct
30 Correct 3346 ms 27952 KB Output is correct
31 Correct 2890 ms 21408 KB Output is correct
32 Correct 649 ms 1688 KB Output is correct
33 Correct 942 ms 2640 KB Output is correct
34 Correct 347 ms 30804 KB Output is correct
35 Correct 1754 ms 16548 KB Output is correct
36 Correct 3314 ms 31056 KB Output is correct
37 Correct 2592 ms 31384 KB Output is correct
38 Correct 2709 ms 30700 KB Output is correct
39 Correct 2223 ms 24404 KB Output is correct
40 Correct 0 ms 348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 559 ms 8304 KB Output is correct
13 Correct 251 ms 8116 KB Output is correct
14 Correct 929 ms 4856 KB Output is correct
15 Correct 1109 ms 4432 KB Output is correct
16 Correct 721 ms 3684 KB Output is correct
17 Correct 1055 ms 4632 KB Output is correct
18 Correct 891 ms 4436 KB Output is correct
19 Correct 927 ms 13320 KB Output is correct
20 Correct 2192 ms 7244 KB Output is correct
21 Correct 469 ms 1292 KB Output is correct
22 Correct 2345 ms 8284 KB Output is correct
23 Correct 332 ms 10500 KB Output is correct
24 Correct 1566 ms 6168 KB Output is correct
25 Correct 2741 ms 10936 KB Output is correct
26 Correct 2282 ms 11144 KB Output is correct
27 Correct 2227 ms 10288 KB Output is correct
28 Correct 815 ms 30556 KB Output is correct
29 Correct 1345 ms 33936 KB Output is correct
30 Correct 3343 ms 28428 KB Output is correct
31 Correct 2777 ms 21716 KB Output is correct
32 Correct 665 ms 1712 KB Output is correct
33 Correct 919 ms 2584 KB Output is correct
34 Correct 392 ms 30892 KB Output is correct
35 Correct 1719 ms 16668 KB Output is correct
36 Correct 3146 ms 31312 KB Output is correct
37 Correct 2529 ms 31700 KB Output is correct
38 Correct 2607 ms 30696 KB Output is correct
39 Correct 1029 ms 65752 KB Output is correct
40 Correct 2323 ms 67616 KB Output is correct
41 Correct 5378 ms 60616 KB Output is correct
42 Correct 4720 ms 45452 KB Output is correct
43 Correct 658 ms 65652 KB Output is correct
44 Correct 1133 ms 3116 KB Output is correct
45 Correct 2162 ms 24468 KB Output is correct
46 Correct 4078 ms 66228 KB Output is correct
47 Correct 4080 ms 65932 KB Output is correct
48 Correct 4070 ms 66144 KB Output is correct
49 Correct 0 ms 348 KB Output is correct