oj.uz

Submission #330048

# Submission time Handle Problem Language Result Execution time Memory
330048 2020-11-23T14:35:58 Z 2qbingxuan Game (IOI13_game) C++17
37 / 100
 6199 ms 12244 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_ctz(a | b);
    a >>= s, b >>= s;
    while(a && b) {
        a >>= __builtin_ctz(a);
        b >>= __builtin_ctz(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 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 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 0 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 1594 ms 6408 KB Output is correct
5 Correct 700 ms 6764 KB Output is correct
6 Correct 2521 ms 3564 KB Output is correct
7 Correct 3001 ms 3180 KB Output is correct
8 Correct 1842 ms 2924 KB Output is correct
9 Correct 2883 ms 3468 KB Output is correct
10 Correct 3012 ms 3176 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
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 2 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2531 ms 8468 KB Output is correct
13 Correct 6030 ms 3072 KB Output is correct
14 Incorrect 705 ms 1152 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
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 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 1609 ms 6548 KB Output is correct
13 Correct 687 ms 6636 KB Output is correct
14 Correct 2586 ms 3416 KB Output is correct
15 Correct 3045 ms 3180 KB Output is correct
16 Correct 1845 ms 3052 KB Output is correct
17 Correct 2872 ms 3276 KB Output is correct
18 Correct 3024 ms 2944 KB Output is correct
19 Correct 2574 ms 8416 KB Output is correct
20 Correct 6086 ms 3204 KB Output is correct
21 Incorrect 712 ms 1132 KB Output isn't correct
22 Halted 0 ms 0 KB -

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 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 2 ms 512 KB Output is correct
12 Correct 1768 ms 6404 KB Output is correct
13 Correct 739 ms 7404 KB Output is correct
14 Correct 2772 ms 5012 KB Output is correct
15 Correct 3332 ms 6728 KB Output is correct
16 Correct 1978 ms 7144 KB Output is correct
17 Correct 2959 ms 7764 KB Output is correct
18 Correct 3145 ms 7300 KB Output is correct
19 Correct 2739 ms 12244 KB Output is correct
20 Correct 6199 ms 7104 KB Output is correct
21 Incorrect 722 ms 5360 KB Output isn't correct
22 Halted 0 ms 0 KB -