oj.uz

Submission #330046

# Submission time Handle Problem Language Result Execution time Memory
330046 2020-11-23T14:27:47 Z 2qbingxuan Game (IOI13_game) C++17
37 / 100
 5811 ms 8300 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 b -= a;
    }
    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 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 1567 ms 6632 KB Output is correct
5 Correct 689 ms 6972 KB Output is correct
6 Correct 2512 ms 3692 KB Output is correct
7 Correct 3028 ms 3436 KB Output is correct
8 Correct 1827 ms 3308 KB Output is correct
9 Correct 2843 ms 3336 KB Output is correct
10 Correct 3010 ms 3052 KB Output is correct
11 Correct 0 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 4 ms 364 KB Output is correct
3 Correct 2 ms 380 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 2504 ms 8176 KB Output is correct
13 Correct 5803 ms 3272 KB Output is correct
14 Incorrect 725 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 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 1566 ms 6380 KB Output is correct
13 Correct 670 ms 6892 KB Output is correct
14 Correct 2515 ms 3436 KB Output is correct
15 Correct 2923 ms 3180 KB Output is correct
16 Correct 1816 ms 3132 KB Output is correct
17 Correct 2829 ms 3312 KB Output is correct
18 Correct 3073 ms 3092 KB Output is correct
19 Correct 2468 ms 8168 KB Output is correct
20 Correct 5811 ms 3532 KB Output is correct
21 Incorrect 708 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 3 ms 384 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 1626 ms 6408 KB Output is correct
13 Correct 686 ms 6908 KB Output is correct
14 Correct 2541 ms 3692 KB Output is correct
15 Correct 3002 ms 3324 KB Output is correct
16 Correct 1846 ms 2924 KB Output is correct
17 Correct 2813 ms 3308 KB Output is correct
18 Correct 3011 ms 2924 KB Output is correct
19 Correct 2473 ms 8300 KB Output is correct
20 Correct 5794 ms 3324 KB Output is correct
21 Incorrect 714 ms 1072 KB Output isn't correct
22 Halted 0 ms 0 KB -