oj.uz

Submission #330052

# Submission time Handle Problem Language Result Execution time Memory
330052 2020-11-23T14:41:48 Z 2qbingxuan Game (IOI13_game) C++17
100 / 100
 11865 ms 55832 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;

class Treap {
private:
    struct node {
        int key, pri;
        ll val, ans;
        node *l, *r;
        node(int k, ll v) : key(k), pri(rand()), val(v), ans(v), l(0), r(0) {}
        void pull() {
            ans = gcd(val, gcd(l ? l->ans : 0, r ? r->ans : 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(a->pri < b->pri)
            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 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1234 ms 6564 KB Output is correct
5 Correct 624 ms 6892 KB Output is correct
6 Correct 2536 ms 3624 KB Output is correct
7 Correct 3062 ms 3272 KB Output is correct
8 Correct 1855 ms 3132 KB Output is correct
9 Correct 2862 ms 3348 KB Output is correct
10 Correct 3136 ms 2964 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 3 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 2100 ms 8240 KB Output is correct
13 Correct 4762 ms 3380 KB Output is correct
14 Correct 585 ms 1004 KB Output is correct
15 Correct 5040 ms 3956 KB Output is correct
16 Correct 879 ms 5676 KB Output is correct
17 Correct 3502 ms 4252 KB Output is correct
18 Correct 6320 ms 6572 KB Output is correct
19 Correct 5308 ms 6568 KB Output is correct
20 Correct 5814 ms 5632 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 3 ms 364 KB Output is correct
4 Correct 0 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 1233 ms 6672 KB Output is correct
13 Correct 594 ms 6636 KB Output is correct
14 Correct 2407 ms 3696 KB Output is correct
15 Correct 2867 ms 3428 KB Output is correct
16 Correct 1798 ms 3216 KB Output is correct
17 Correct 2695 ms 3468 KB Output is correct
18 Correct 2945 ms 3096 KB Output is correct
19 Correct 1994 ms 8044 KB Output is correct
20 Correct 4728 ms 3372 KB Output is correct
21 Correct 577 ms 1004 KB Output is correct
22 Correct 4964 ms 4036 KB Output is correct
23 Correct 851 ms 5740 KB Output is correct
24 Correct 3400 ms 4276 KB Output is correct
25 Correct 6353 ms 6492 KB Output is correct
26 Correct 5298 ms 6576 KB Output is correct
27 Correct 5743 ms 5976 KB Output is correct
28 Correct 2004 ms 21100 KB Output is correct
29 Correct 3098 ms 24324 KB Output is correct
30 Correct 6876 ms 17312 KB Output is correct
31 Correct 5450 ms 13416 KB Output is correct
32 Correct 803 ms 1132 KB Output is correct
33 Correct 1304 ms 1392 KB Output is correct
34 Correct 1363 ms 21484 KB Output is correct
35 Correct 3916 ms 12200 KB Output is correct
36 Correct 8034 ms 21684 KB Output is correct
37 Correct 6354 ms 21856 KB Output is correct
38 Correct 7293 ms 21388 KB Output is correct
39 Correct 5283 ms 17232 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 1242 ms 6764 KB Output is correct
13 Correct 599 ms 6764 KB Output is correct
14 Correct 2405 ms 3936 KB Output is correct
15 Correct 2900 ms 3408 KB Output is correct
16 Correct 1731 ms 3112 KB Output is correct
17 Correct 2714 ms 3648 KB Output is correct
18 Correct 2918 ms 3188 KB Output is correct
19 Correct 2009 ms 8124 KB Output is correct
20 Correct 4754 ms 3380 KB Output is correct
21 Correct 581 ms 1004 KB Output is correct
22 Correct 5012 ms 4228 KB Output is correct
23 Correct 847 ms 5868 KB Output is correct
24 Correct 3362 ms 4228 KB Output is correct
25 Correct 6308 ms 6340 KB Output is correct
26 Correct 5305 ms 6252 KB Output is correct
27 Correct 5860 ms 5916 KB Output is correct
28 Correct 2021 ms 21216 KB Output is correct
29 Correct 3110 ms 24356 KB Output is correct
30 Correct 6960 ms 17300 KB Output is correct
31 Correct 5439 ms 13612 KB Output is correct
32 Correct 806 ms 1004 KB Output is correct
33 Correct 1305 ms 1404 KB Output is correct
34 Correct 1349 ms 21228 KB Output is correct
35 Correct 3983 ms 11864 KB Output is correct
36 Correct 7979 ms 21712 KB Output is correct
37 Correct 6253 ms 21868 KB Output is correct
38 Correct 7237 ms 21180 KB Output is correct
39 Correct 2871 ms 44396 KB Output is correct
40 Correct 5575 ms 46376 KB Output is correct
41 Correct 11343 ms 35424 KB Output is correct
42 Correct 9554 ms 34184 KB Output is correct
43 Correct 2847 ms 51800 KB Output is correct
44 Correct 1400 ms 10860 KB Output is correct
45 Correct 5365 ms 27300 KB Output is correct
46 Correct 10675 ms 55788 KB Output is correct
47 Correct 10620 ms 55832 KB Output is correct
48 Correct 11865 ms 55444 KB Output is correct
49 Correct 1 ms 492 KB Output is correct