oj.uz

Submission #330047

# Submission time Handle Problem Language Result Execution time Memory
330047 2020-11-23T14:32:44 Z 2qbingxuan Game (IOI13_game) C++17
37 / 100
 5833 ms 8172 KB 
#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);
    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

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 0 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 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 1523 ms 6628 KB Output is correct
5 Correct 654 ms 6892 KB Output is correct
6 Correct 2498 ms 3596 KB Output is correct
7 Correct 2951 ms 3212 KB Output is correct
8 Correct 1838 ms 3196 KB Output is correct
9 Correct 2854 ms 3544 KB Output is correct
10 Correct 3070 ms 3096 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 512 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2430 ms 8172 KB Output is correct
13 Correct 5823 ms 3052 KB Output is correct
14 Incorrect 696 ms 1004 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 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 1513 ms 6380 KB Output is correct
13 Correct 657 ms 6892 KB Output is correct
14 Correct 2522 ms 3436 KB Output is correct
15 Correct 2938 ms 3560 KB Output is correct
16 Correct 1840 ms 3308 KB Output is correct
17 Correct 2799 ms 3308 KB Output is correct
18 Correct 2965 ms 2924 KB Output is correct
19 Correct 2429 ms 8172 KB Output is correct
20 Correct 5833 ms 3180 KB Output is correct
21 Incorrect 695 ms 1004 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 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 1516 ms 6464 KB Output is correct
13 Correct 660 ms 6764 KB Output is correct
14 Correct 2492 ms 3436 KB Output is correct
15 Correct 2953 ms 3236 KB Output is correct
16 Correct 1838 ms 2900 KB Output is correct
17 Correct 2820 ms 3396 KB Output is correct
18 Correct 3078 ms 3224 KB Output is correct
19 Correct 2676 ms 8172 KB Output is correct
20 Correct 5817 ms 3180 KB Output is correct
21 Incorrect 709 ms 1132 KB Output isn't correct
22 Halted 0 ms 0 KB -