oj.uz

Submission #330039

# Submission time Handle Problem Language Result Execution time Memory
330039 2020-11-23T14:01:45 Z 2qbingxuan Game (IOI13_game) C++14
80 / 100
 6794 ms 42988 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) {
    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;
/*
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 15 ms 31340 KB Output is correct
6 Correct 17 ms 31340 KB Output is correct
7 Correct 15 ms 31340 KB Output is correct
8 Correct 19 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 15 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 15 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 1490 ms 35408 KB Output is correct
5 Correct 418 ms 35932 KB Output is correct
6 Correct 1802 ms 32364 KB Output is correct
7 Correct 2118 ms 32460 KB Output is correct
8 Correct 1354 ms 32960 KB Output is correct
9 Correct 2043 ms 32260 KB Output is correct
10 Correct 1697 ms 31852 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 16 ms 31340 KB Output is correct
2 Correct 17 ms 31340 KB Output is correct
3 Correct 18 ms 31340 KB Output is correct
4 Correct 15 ms 31340 KB Output is correct
5 Correct 15 ms 31340 KB Output is correct
6 Correct 19 ms 31340 KB Output is correct
7 Correct 15 ms 31340 KB Output is correct
8 Correct 16 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 1989 ms 35644 KB Output is correct
13 Correct 4691 ms 32348 KB Output is correct
14 Correct 593 ms 31980 KB Output is correct
15 Correct 5163 ms 32480 KB Output is correct
16 Correct 443 ms 32364 KB Output is correct
17 Correct 2917 ms 33028 KB Output is correct
18 Correct 5234 ms 32796 KB Output is correct
19 Correct 4352 ms 32620 KB Output is correct
20 Correct 3573 ms 32296 KB Output is correct
21 Correct 16 ms 31340 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 31468 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 20 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 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 1487 ms 35564 KB Output is correct
13 Correct 411 ms 35692 KB Output is correct
14 Correct 1831 ms 32700 KB Output is correct
15 Correct 2176 ms 32296 KB Output is correct
16 Correct 1351 ms 33012 KB Output is correct
17 Correct 2039 ms 32468 KB Output is correct
18 Correct 1687 ms 31852 KB Output is correct
19 Correct 1993 ms 35564 KB Output is correct
20 Correct 4702 ms 32472 KB Output is correct
21 Correct 579 ms 31852 KB Output is correct
22 Correct 5181 ms 32312 KB Output is correct
23 Correct 439 ms 32236 KB Output is correct
24 Correct 2960 ms 32892 KB Output is correct
25 Correct 5135 ms 32556 KB Output is correct
26 Correct 4331 ms 32704 KB Output is correct
27 Correct 3587 ms 32240 KB Output is correct
28 Correct 827 ms 37404 KB Output is correct
29 Correct 2956 ms 40664 KB Output is correct
30 Correct 6259 ms 35180 KB Output is correct
31 Correct 5735 ms 34872 KB Output is correct
32 Correct 786 ms 32040 KB Output is correct
33 Correct 1263 ms 32068 KB Output is correct
34 Correct 632 ms 37740 KB Output is correct
35 Correct 3373 ms 35748 KB Output is correct
36 Correct 6617 ms 38308 KB Output is correct
37 Correct 5448 ms 38228 KB Output is correct
38 Correct 4996 ms 37660 KB Output is correct
39 Correct 4600 ms 37024 KB Output is correct
40 Correct 17 ms 31340 KB Output is correct

Subtask #5
0 / 20.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 18 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 16 ms 31340 KB Output is correct
8 Correct 16 ms 31340 KB Output is correct
9 Correct 20 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 1456 ms 35460 KB Output is correct
13 Correct 416 ms 35692 KB Output is correct
14 Correct 1817 ms 32620 KB Output is correct
15 Correct 2111 ms 32492 KB Output is correct
16 Correct 1335 ms 33132 KB Output is correct
17 Correct 2040 ms 32572 KB Output is correct
18 Correct 1696 ms 31944 KB Output is correct
19 Correct 1979 ms 35540 KB Output is correct
20 Correct 4679 ms 32244 KB Output is correct
21 Correct 583 ms 31980 KB Output is correct
22 Correct 5164 ms 32444 KB Output is correct
23 Correct 440 ms 32364 KB Output is correct
24 Correct 2923 ms 33076 KB Output is correct
25 Correct 5211 ms 32764 KB Output is correct
26 Correct 4324 ms 32924 KB Output is correct
27 Correct 3595 ms 32388 KB Output is correct
28 Correct 837 ms 37632 KB Output is correct
29 Correct 2967 ms 40792 KB Output is correct
30 Correct 6289 ms 35080 KB Output is correct
31 Correct 5709 ms 34728 KB Output is correct
32 Correct 762 ms 31896 KB Output is correct
33 Correct 1249 ms 32020 KB Output is correct
34 Correct 607 ms 37708 KB Output is correct
35 Correct 3402 ms 35780 KB Output is correct
36 Correct 6794 ms 38056 KB Output is correct
37 Correct 5508 ms 38120 KB Output is correct
38 Correct 5071 ms 37556 KB Output is correct
39 Execution timed out 1010 ms 42988 KB Time limit exceeded (wall clock)
40 Halted 0 ms 0 KB -