oj.uz

Submission #330050

# Submission time Handle Problem Language Result Execution time Memory
330050 2020-11-23T14:37:04 Z 2qbingxuan Game (IOI13_game) C++17
80 / 100
 13000 ms 57108 KB 
#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#ifndef local
#include "game.h"
#endif // local

using namespace std;
using ll = long long;
const int N = 22000, LG = 30;

inline ll gcd(ll a, ll b) {
    if(!a || !b) return a | b;
    int s = __builtin_ctzll(a | b);
    a >>= s, b >>= s;
    while(a && b) {
        a >>= __builtin_ctzll(a);
        b >>= __builtin_ctzll(b);
        if(a > b) a -= b;
        else if(b > a) b -= a;
        else return a << s;
    }
    return (a | b) << s;
}

int R, C;

int cnt;
class Treap {
private:
    struct node {
        int key, sz;
        ll val, ans;
        node *l, *r;
        node(int k, ll v) : key(k), sz(1), val(v), ans(v), l(0), r(0) {}
        void pull() {
            ans = gcd(val, gcd(l ? l->ans : 0, r ? r->ans : 0));
            sz = 1 + (l ? l->sz : 0) + (r ? r->sz : 0);
        }
    } *root;
    void split(int k, node *o, node *&a, node *&b) {
        // a: key < k, b: key >= k
        if(!o) return a = b = nullptr, void();
        if(o->key < k)
            a = o, split(k, o->r, a->r, b), a->pull();
        else
            b = o, split(k, o->l, a, b->l), b->pull();
    }
    node *join(node *a, node *b) {
        if(!a || !b) return a ? a : b;
        if(cnt++ % (a->sz+b->sz) < a->sz)
            return a->r = join(a->r, b), a->pull(), a;
        else
            return b->l = join(a, b->l), b->pull(), b;
    }
public:
    Treap() : root(nullptr) {}
    void modify(int p, ll v) {
        node *a, *b, *c;
        split(p, root, a, b);
        split(p+1, b, b, c);
        if(b == nullptr)
            b = new node(p, v);
        else
            b->val = b->ans = v;
        root = join(a, join(b, c));
    }
    ll query(int l, int r) {
        node *a, *b, *c;
        split(l, root, a, b);
        split(r, b, b, c);
        ll res = b ? b->ans : 0;
        root = join(a, join(b, c));
        return res;
    }
};

struct Segtree2d {
    struct node {
        Treap st;
        node *l, *r;
        node() : l(nullptr), r(nullptr) {}
        // Complexity of pull would TLE
        // Notice that only posy would change
        void pull(int y) {
            st.modify(y, gcd(l ? l->st.query(y, y+1) : 0, r ? r->st.query(y, y+1) : 0));
        }
    } *root;
    void modify(int posx, int posy, ll v, node *&cur, int l, int r) {
        if(!cur) cur = new node();
        if(l+1 == r) {
            cur->st.modify(posy, v);
            return;
        }
        int m = l+(r-l)/2;
        if(posx < m)
            modify(posx, posy, v, cur->l, l, m);
        else
            modify(posx, posy, v, cur->r, m, r);
        cur->pull(posy);
    }
    ll query(int lx, int rx, int ly, int ry, node *cur, int l, int r) {
        if(r <= lx || l >= rx || !cur) return 0;
        if(lx <= l && r <= rx) return cur->st.query(ly, ry);
        int m = l+(r-l)/2;
        return gcd(query(lx, rx, ly, ry, cur->l, l, m), query(lx, rx, ly, ry, cur->r, m, r));
    }
    Segtree2d() : root(nullptr) {}
    void modify(int posx, int posy, ll v) {
        modify(posx, posy, v, root, 0, R);
    }
    ll query(int lx, int rx, int ly, int ry) {
        return query(lx, rx, ly, ry, root, 0, R);
    }
} sgt;

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

void update(int x, int y, ll k) {
    sgt.modify(x, y, k);
}

ll calculate(int lx, int ly, int rx, int ry) {
    if(lx > rx) swap(lx, rx);
    if(ly > ry) swap(ly, ry);
    return sgt.query(lx, rx+1, ly, ry+1);
}
#ifdef local
signed main() {
    int a, b, n;
    cin >> a >> b >> n;
    init(a, b);
    for(int i = 0; i < n; i++) {
        int t;
        cin >> t;
        if(t == 1) {
            int x, y;
            ll k;
            cin >> x >> y >> k;
            update(x, y, k);
        } else {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << calculate(x1, y1, x2, y2) << '\n';
        }
    }
}
#endif // local

Compilation message

game.cpp:2: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
    2 | #pragma loop_opt(on)
      |

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1658 ms 10812 KB Output is correct
5 Correct 700 ms 10568 KB Output is correct
6 Correct 2668 ms 8156 KB Output is correct
7 Correct 3227 ms 7660 KB Output is correct
8 Correct 1905 ms 7192 KB Output is correct
9 Correct 2995 ms 7784 KB Output is correct
10 Correct 3104 ms 7436 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2518 ms 12136 KB Output is correct
13 Correct 5917 ms 7088 KB Output is correct
14 Correct 728 ms 5484 KB Output is correct
15 Correct 6494 ms 8544 KB Output is correct
16 Correct 913 ms 10040 KB Output is correct
17 Correct 3605 ms 8756 KB Output is correct
18 Correct 6496 ms 10476 KB Output is correct
19 Correct 5605 ms 10612 KB Output is correct
20 Correct 6023 ms 10140 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1587 ms 11068 KB Output is correct
13 Correct 684 ms 10604 KB Output is correct
14 Correct 2567 ms 8428 KB Output is correct
15 Correct 3149 ms 7820 KB Output is correct
16 Correct 1866 ms 7532 KB Output is correct
17 Correct 2865 ms 7916 KB Output is correct
18 Correct 3056 ms 7896 KB Output is correct
19 Correct 2519 ms 12332 KB Output is correct
20 Correct 5936 ms 7304 KB Output is correct
21 Correct 716 ms 5484 KB Output is correct
22 Correct 6502 ms 8532 KB Output is correct
23 Correct 913 ms 9964 KB Output is correct
24 Correct 3581 ms 8768 KB Output is correct
25 Correct 6557 ms 10956 KB Output is correct
26 Correct 5581 ms 10992 KB Output is correct
27 Correct 5969 ms 10344 KB Output is correct
28 Correct 2151 ms 30188 KB Output is correct
29 Correct 3659 ms 28352 KB Output is correct
30 Correct 8306 ms 21612 KB Output is correct
31 Correct 7195 ms 17652 KB Output is correct
32 Correct 952 ms 5228 KB Output is correct
33 Correct 1528 ms 5616 KB Output is correct
34 Correct 1402 ms 25872 KB Output is correct
35 Correct 4175 ms 16164 KB Output is correct
36 Correct 8460 ms 25508 KB Output is correct
37 Correct 6679 ms 25996 KB Output is correct
38 Correct 7576 ms 25144 KB Output is correct
39 Correct 5529 ms 21332 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1582 ms 10860 KB Output is correct
13 Correct 702 ms 10732 KB Output is correct
14 Correct 2570 ms 7900 KB Output is correct
15 Correct 3053 ms 4152 KB Output is correct
16 Correct 1861 ms 3052 KB Output is correct
17 Correct 2871 ms 3488 KB Output is correct
18 Correct 3084 ms 3216 KB Output is correct
19 Correct 2506 ms 8300 KB Output is correct
20 Correct 5932 ms 3308 KB Output is correct
21 Correct 841 ms 1008 KB Output is correct
22 Correct 6599 ms 8396 KB Output is correct
23 Correct 923 ms 9964 KB Output is correct
24 Correct 3567 ms 8864 KB Output is correct
25 Correct 6698 ms 10692 KB Output is correct
26 Correct 5642 ms 11004 KB Output is correct
27 Correct 6036 ms 10376 KB Output is correct
28 Correct 2148 ms 30224 KB Output is correct
29 Correct 3647 ms 28512 KB Output is correct
30 Correct 8178 ms 21672 KB Output is correct
31 Correct 7192 ms 17916 KB Output is correct
32 Correct 953 ms 5484 KB Output is correct
33 Correct 1528 ms 5668 KB Output is correct
34 Correct 1373 ms 25836 KB Output is correct
35 Correct 4137 ms 16112 KB Output is correct
36 Correct 8522 ms 25508 KB Output is correct
37 Correct 7147 ms 25652 KB Output is correct
38 Correct 7931 ms 25340 KB Output is correct
39 Correct 3227 ms 48764 KB Output is correct
40 Correct 6570 ms 57108 KB Output is correct
41 Execution timed out 13064 ms 42952 KB Time limit exceeded
42 Halted 0 ms 0 KB -