oj.uz

Submission #330036

# Submission time Handle Problem Language Result Execution time Memory
330036 2020-11-23T13:56:35 Z 2qbingxuan Game (IOI13_game) C++14
80 / 100
 6575 ms 53612 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;

int R, C;
/*
class Segtree1d {
    // 1d, dynamic
private:
    struct node {
        ll ans;
        node *l, *r;
        node() : ans(0), l(nullptr), r(nullptr) {}
        void pull() {
            ans = __gcd( l ? l->ans : 0, r ? r->ans : 0);
        }
    } *root;
    void modify(int pos, ll v, node *&cur, int l, int r) {
        if(!cur) cur = new node();
        if(l+1 == r) {
            cur->ans = v;
            return;
        }
        int m = l+(r-l)/2;
        if(pos < m)
            modify(pos, v, cur->l, l, m);
        else
            modify(pos, v, cur->r, m, r);
        cur->pull();
    }
    ll query(int ql, int qr, node *cur, int l, int r) {
        if(l >= qr || r <= ql || !cur) return 0;
        if(ql <= l && r <= qr) return cur->ans;
        int m = l+(r-l)/2;
        return __gcd(query(ql, qr, cur->l, l, m), query(ql, qr, cur->r, m, r));
    }
public:
    Segtree1d() : root(nullptr) {}
    void modify(int pos, ll v) {
        modify(pos, v, root, 0, C);
    }
    ll query(int l, int r) {
        return query(l, r, root, 0, C);
    }
};
*/
struct Splay {
    struct node {
        int key;
        ll val, ans;
        node *ch[2], *pa;
        node(int k, ll v) : key(k), val(v), ans(v), ch{}, pa(0) {}
        node() : key(-1), val(0), ans(0), ch{}, pa(0) {}
        void pull() {
            ans = __gcd(val, __gcd(ch[0] ? ch[0]->ans : 0, ch[1] ? ch[1]->ans : 0));
        }
        friend bool dir(node *x) { return x->pa && x->pa->ch[1] == x; }
    } *root;
    void rot(node *x) {
        bool d = dir(x);
        node *y = x->pa, *z = (y ? y->pa : nullptr);
        x->pa = z;
        if(z) z->ch[dir(y)] = x;
        if(x->ch[!d]) x->ch[!d]->pa = y;
        y->ch[d] = x->ch[!d];
        y->pa = x;
        x->ch[!d] = y;
        y->pull(), x->pull();
    }
    void splay(node *x) {
        while(node *y = x->pa) {
            if(y->pa)
                rot(dir(x) != dir(y) ? x : y);
            rot(x);
        }
    }
    void split(int k, node *x, node *&a, node *&b) {
        // a: key < k, b: key >= k
        node *y = nullptr, *last = nullptr;
        while(x) {
            last = x;
            if(x->key < k) {
                x = x->ch[1];
            } else {
                y = x;
                x = x->ch[0];
            }
        }
        if(last) splay(last);
        if(!y) return a = last, b = nullptr, void();
        splay(y);
        a = y->ch[0];
        if(a) a->pa = nullptr;
        y->ch[0] = nullptr;
        b = y;
        b->pull();
    }
    node *join(node *a, node *b) {
        if(!a || !b) return a ? a : b;
        while(a->ch[1]) a = a->ch[1];
        while(b->ch[0]) b = b->ch[0];
        splay(a), splay(b);
        b->ch[0] = a;
        a->pa = b;
        b->pull();
        return b;
    }
    static node mem[N * LG], *ptr;
    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 (ptr++) 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;
    }
    Splay() : root(nullptr) {}
};
Splay::node Splay::mem[N * LG], *Splay::ptr = Splay::mem;

class Segtree2d {
private:
    struct node {
        Splay 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));
    }
public:
    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() {
    ;
}
#endif // local

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31340 KB Output is correct
2 Correct 15 ms 31340 KB Output is correct
3 Correct 16 ms 31340 KB Output is correct
4 Correct 1485 ms 35468 KB Output is correct
5 Correct 410 ms 35692 KB Output is correct
6 Correct 1826 ms 32492 KB Output is correct
7 Correct 2139 ms 32460 KB Output is correct
8 Correct 1416 ms 33044 KB Output is correct
9 Correct 2156 ms 32396 KB Output is correct
10 Correct 1788 ms 31900 KB Output is correct
11 Correct 16 ms 31340 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31264 KB Output is correct
2 Correct 17 ms 31340 KB Output is correct
3 Correct 17 ms 31340 KB Output is correct
4 Correct 19 ms 31340 KB Output is correct
5 Correct 17 ms 31340 KB Output is correct
6 Correct 18 ms 31340 KB Output is correct
7 Correct 18 ms 31340 KB Output is correct
8 Correct 16 ms 31340 KB Output is correct
9 Correct 19 ms 31340 KB Output is correct
10 Correct 17 ms 31340 KB Output is correct
11 Correct 17 ms 31340 KB Output is correct
12 Correct 2036 ms 35436 KB Output is correct
13 Correct 4783 ms 32080 KB Output is correct
14 Correct 591 ms 31852 KB Output is correct
15 Correct 5128 ms 32236 KB Output is correct
16 Correct 443 ms 32364 KB Output is correct
17 Correct 2932 ms 32752 KB Output is correct
18 Correct 5236 ms 32660 KB Output is correct
19 Correct 4332 ms 32704 KB Output is correct
20 Correct 3545 ms 32108 KB Output is correct
21 Correct 16 ms 31360 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31340 KB Output is correct
2 Correct 18 ms 31340 KB Output is correct
3 Correct 17 ms 31340 KB Output is correct
4 Correct 16 ms 31340 KB Output is correct
5 Correct 16 ms 31340 KB Output is correct
6 Correct 17 ms 31340 KB Output is correct
7 Correct 18 ms 31340 KB Output is correct
8 Correct 17 ms 31340 KB Output is correct
9 Correct 17 ms 31340 KB Output is correct
10 Correct 17 ms 31340 KB Output is correct
11 Correct 16 ms 31340 KB Output is correct
12 Correct 1483 ms 35440 KB Output is correct
13 Correct 416 ms 35692 KB Output is correct
14 Correct 1821 ms 32492 KB Output is correct
15 Correct 2081 ms 32300 KB Output is correct
16 Correct 1362 ms 33068 KB Output is correct
17 Correct 2036 ms 32540 KB Output is correct
18 Correct 1706 ms 31936 KB Output is correct
19 Correct 1983 ms 35500 KB Output is correct
20 Correct 4642 ms 32108 KB Output is correct
21 Correct 589 ms 31852 KB Output is correct
22 Correct 5176 ms 32200 KB Output is correct
23 Correct 439 ms 32204 KB Output is correct
24 Correct 2938 ms 32816 KB Output is correct
25 Correct 5212 ms 32584 KB Output is correct
26 Correct 4359 ms 32620 KB Output is correct
27 Correct 3591 ms 32064 KB Output is correct
28 Correct 843 ms 43464 KB Output is correct
29 Correct 2939 ms 50668 KB Output is correct
30 Correct 6345 ms 41964 KB Output is correct
31 Correct 5802 ms 41412 KB Output is correct
32 Correct 805 ms 41196 KB Output is correct
33 Correct 1343 ms 41180 KB Output is correct
34 Correct 640 ms 44652 KB Output is correct
35 Correct 3600 ms 45400 KB Output is correct
36 Correct 6575 ms 48580 KB Output is correct
37 Correct 5199 ms 48708 KB Output is correct
38 Correct 4700 ms 48148 KB Output is correct
39 Correct 4379 ms 47340 KB Output is correct
40 Correct 16 ms 31340 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31340 KB Output is correct
2 Correct 17 ms 31340 KB Output is correct
3 Correct 17 ms 31340 KB Output is correct
4 Correct 16 ms 31468 KB Output is correct
5 Correct 16 ms 31340 KB Output is correct
6 Correct 20 ms 31340 KB Output is correct
7 Correct 16 ms 31340 KB Output is correct
8 Correct 18 ms 31340 KB Output is correct
9 Correct 17 ms 31340 KB Output is correct
10 Correct 16 ms 31340 KB Output is correct
11 Correct 16 ms 31340 KB Output is correct
12 Correct 1463 ms 35436 KB Output is correct
13 Correct 418 ms 35808 KB Output is correct
14 Correct 1857 ms 32440 KB Output is correct
15 Correct 2115 ms 32144 KB Output is correct
16 Correct 1338 ms 33004 KB Output is correct
17 Correct 2029 ms 32364 KB Output is correct
18 Correct 1720 ms 32120 KB Output is correct
19 Correct 2005 ms 35480 KB Output is correct
20 Correct 4653 ms 32212 KB Output is correct
21 Correct 587 ms 32148 KB Output is correct
22 Correct 5148 ms 32492 KB Output is correct
23 Correct 450 ms 32492 KB Output is correct
24 Correct 2922 ms 33120 KB Output is correct
25 Correct 5228 ms 32852 KB Output is correct
26 Correct 4374 ms 32820 KB Output is correct
27 Correct 3582 ms 32064 KB Output is correct
28 Correct 846 ms 43500 KB Output is correct
29 Correct 2970 ms 50804 KB Output is correct
30 Correct 6290 ms 41956 KB Output is correct
31 Correct 5786 ms 41708 KB Output is correct
32 Correct 781 ms 41068 KB Output is correct
33 Correct 1280 ms 41196 KB Output is correct
34 Correct 619 ms 44396 KB Output is correct
35 Correct 3398 ms 45480 KB Output is correct
36 Correct 6574 ms 48604 KB Output is correct
37 Correct 5185 ms 48856 KB Output is correct
38 Correct 4726 ms 48192 KB Output is correct
39 Execution timed out 969 ms 53612 KB Time limit exceeded (wall clock)
40 Halted 0 ms 0 KB -