oj.uz

Submission #554521

# Submission time Handle Problem Language Result Execution time Memory
554521 2022-04-28T15:15:56 Z elazarkoren Game (IOI13_game) C++17
100 / 100
 6855 ms 64712 KB 
#include "game.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
//#define int ll
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

const int infinity = 1e9;

mt19937 rng(time(0));
auto Dist = uniform_int_distribution<int>(0, infinity);

inline int mrand() {
    return Dist(rng);
}

struct Node {
    int index = 0;
    ll val = 0, gcd = 0;
    int prio;
    Node *l = 0, *r = 0;
    Node(int i, ll x): index(i), val(x), gcd(x), prio(mrand()) {}
    inline void pull() {
        gcd = gcd2(val, gcd2(l ? l->gcd : 0, r ? r->gcd : 0));
    }
};
typedef Node* pnode;

void Merge(pnode &t, pnode l, pnode r) {
    if (!l || !r) {
        t = l ? l : r;
        return;
    }
    if (l->prio > r->prio) {
        t = l;
        Merge(t->r, l->r, r);
    } else {
        t = r;
        Merge(t->l, l, r->l);
    }
    t->pull();
}

void Split(pnode t, pnode &l, pnode &r, int ind) { // <= ind
    if (!t) {
        l = r = t;
        return;
    }
    if (t->index <= ind) {
        l = t;
        Split(t->r, l->r, r, ind);
    } else {
        r = t;
        Split(t->l, l, r->l, ind);
    }
    if (l) l->pull();
    if (r) r->pull();
}

struct Treap {
    pnode t = 0;
    void insert(int i, ll x) {
        pnode l = 0, r = 0, mid = 0;
        Split(t, l, r, i - 1);
        Split(r, mid, r, i);
        if (mid) delete mid;
        Merge(t, l, new Node(i, x));
        Merge(t, t, r);
    }
    ll query(int a, int b) {
        pnode l = 0, r = 0, mid = 0;
        Split(t, l, r, b - 1);
        Split(l, l, mid, a - 1);
        ll x = mid ? mid->gcd : 0;
        Merge(t, l, mid);
        Merge(t, t, r);
        return x;
    }
};

struct Seg {
    int n;
    vector<Treap> seg;
    vi lp, rp;
    Seg () {}
    Seg (int m): n(m) {
        Add();
    }
    inline void Add() {
        seg.push_back(Treap());
        lp.push_back(0);
        rp.push_back(0);
    }
    void update(int i, int j, ll x, int ind, int l, int r) {
        if (l + 1 == r) {
            seg[ind].insert(j, x);
            return;
        }
        if (i < (l + r) >> 1) {
            if (!lp[ind]) {
                lp[ind] = seg.size();
                Add();
            }
            update(i, j, x, lp[ind], l, (l + r) >> 1);
        } else {
            if (!rp[ind]) {
                rp[ind] = seg.size();
                Add();
            }
            update(i, j, x, rp[ind], (l + r) >> 1, r);
        }
        x = gcd2(lp[ind] ? seg[lp[ind]].query(j, j + 1) : 0, rp[ind] ? seg[rp[ind]].query(j, j + 1) : 0);
        seg[ind].insert(j, x);
    }
    inline void update(int i, int j, ll x) {
        update(i, j, x, 0, 0, n);
    }
    ll query(int x1, int y1, int x2, int y2, int ind, int l, int r) {
        if (x1 <= l && r <= x2) return seg[ind].query(y1, y2);
        if (r <= x1 || x2 <= l) return 0;
        return gcd2(lp[ind] ? query(x1, y1, x2, y2, lp[ind], l, (l + r >> 1)) : 0,
                    rp[ind] ? query(x1, y1, x2, y2, rp[ind], (l + r) >> 1, r) : 0);
    }
    inline ll query(int x1, int y1, int x2, int y2) {
        return query(x1, y1, x2, y2, 0, 0, n);
    }
};

int n, m;
Seg seg;

void init(int32_t R, int32_t C) {
    n = R, m = C;
    seg = Seg(n);
}

void update(int32_t p, int32_t q, long long k) {
    seg.update(p, q, k);
}

long long calculate(int32_t p, int32_t q, int32_t u, int32_t v) {
    return seg.query(p, q, u + 1, v + 1);
}

Compilation message

game.cpp: In member function 'll Seg::query(int, int, int, int, int, int, int)':
game.cpp:139:68: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |         return gcd2(lp[ind] ? query(x1, y1, x2, y2, lp[ind], l, (l + r >> 1)) : 0,
      |                                                                  ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 300 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 964 ms 7596 KB Output is correct
5 Correct 464 ms 8124 KB Output is correct
6 Correct 1577 ms 4668 KB Output is correct
7 Correct 1858 ms 4800 KB Output is correct
8 Correct 1181 ms 3744 KB Output is correct
9 Correct 1756 ms 4508 KB Output is correct
10 Correct 1485 ms 4088 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 480 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1582 ms 10604 KB Output is correct
13 Correct 3970 ms 5044 KB Output is correct
14 Correct 500 ms 2312 KB Output is correct
15 Correct 4035 ms 5904 KB Output is correct
16 Correct 508 ms 8496 KB Output is correct
17 Correct 2472 ms 6124 KB Output is correct
18 Correct 4485 ms 8880 KB Output is correct
19 Correct 3805 ms 9000 KB Output is correct
20 Correct 3483 ms 8392 KB Output is correct
21 Correct 1 ms 304 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 1041 ms 7568 KB Output is correct
13 Correct 432 ms 7940 KB Output is correct
14 Correct 1580 ms 4672 KB Output is correct
15 Correct 1883 ms 4424 KB Output is correct
16 Correct 1202 ms 3896 KB Output is correct
17 Correct 1923 ms 4508 KB Output is correct
18 Correct 1515 ms 4056 KB Output is correct
19 Correct 1602 ms 10520 KB Output is correct
20 Correct 3879 ms 5048 KB Output is correct
21 Correct 506 ms 2320 KB Output is correct
22 Correct 4212 ms 5952 KB Output is correct
23 Correct 507 ms 8664 KB Output is correct
24 Correct 2501 ms 6216 KB Output is correct
25 Correct 4680 ms 8840 KB Output is correct
26 Correct 3634 ms 8996 KB Output is correct
27 Correct 3317 ms 8392 KB Output is correct
28 Correct 1405 ms 34896 KB Output is correct
29 Correct 2581 ms 37560 KB Output is correct
30 Correct 5069 ms 27480 KB Output is correct
31 Correct 4529 ms 22772 KB Output is correct
32 Correct 711 ms 10172 KB Output is correct
33 Correct 1096 ms 10472 KB Output is correct
34 Correct 804 ms 31396 KB Output is correct
35 Correct 2755 ms 23080 KB Output is correct
36 Correct 5800 ms 35396 KB Output is correct
37 Correct 4698 ms 35596 KB Output is correct
38 Correct 4731 ms 34968 KB Output is correct
39 Correct 3964 ms 29748 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 304 KB Output is correct
3 Correct 2 ms 300 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 962 ms 7576 KB Output is correct
13 Correct 428 ms 7952 KB Output is correct
14 Correct 1612 ms 4740 KB Output is correct
15 Correct 1852 ms 4360 KB Output is correct
16 Correct 1187 ms 3920 KB Output is correct
17 Correct 1805 ms 4496 KB Output is correct
18 Correct 1494 ms 4144 KB Output is correct
19 Correct 1649 ms 10552 KB Output is correct
20 Correct 3820 ms 5156 KB Output is correct
21 Correct 528 ms 2268 KB Output is correct
22 Correct 4187 ms 5876 KB Output is correct
23 Correct 514 ms 8448 KB Output is correct
24 Correct 2539 ms 6300 KB Output is correct
25 Correct 4522 ms 8832 KB Output is correct
26 Correct 3796 ms 9144 KB Output is correct
27 Correct 3649 ms 8408 KB Output is correct
28 Correct 1446 ms 34916 KB Output is correct
29 Correct 2546 ms 37512 KB Output is correct
30 Correct 5101 ms 27536 KB Output is correct
31 Correct 4461 ms 22728 KB Output is correct
32 Correct 630 ms 10060 KB Output is correct
33 Correct 954 ms 10584 KB Output is correct
34 Correct 623 ms 31316 KB Output is correct
35 Correct 2462 ms 23104 KB Output is correct
36 Correct 5159 ms 35500 KB Output is correct
37 Correct 4035 ms 35640 KB Output is correct
38 Correct 3909 ms 35052 KB Output is correct
39 Correct 1805 ms 62700 KB Output is correct
40 Correct 3948 ms 64712 KB Output is correct
41 Correct 6855 ms 50584 KB Output is correct
42 Correct 6270 ms 40036 KB Output is correct
43 Correct 1373 ms 59472 KB Output is correct
44 Correct 1054 ms 10712 KB Output is correct
45 Correct 3222 ms 29764 KB Output is correct
46 Correct 6251 ms 63540 KB Output is correct
47 Correct 6703 ms 63452 KB Output is correct
48 Correct 6259 ms 63084 KB Output is correct
49 Correct 1 ms 212 KB Output is correct