oj.uz

Submission #774183

# Submission time Handle Problem Language Result Execution time Memory
774183 2023-07-05T12:43:48 Z alontanay Game (IOI13_game) C++14
100 / 100
 5392 ms 73260 KB 
#include "game.h"

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using pi = pair<int, int>;

ll safe_gcd(ll a, ll b) {
    if (a == 0 || b == 0) {
        return a + b;
    }
    return __gcd(a, b);
}

template <typename T>
struct node {
    T val, gc;
    int prior;
    pi pos;
    node *l = nullptr, *r = nullptr;
    node(T v, pi pos) : val(v), gc(v), pos(pos), prior(rand()) {}
};

template <typename T>
using node_ptr = struct node<T> *;

template <typename T>
void print(node_ptr<T> t, int id = 0) {
    for (int i = 0; i < id; i++) {
        cout << "  ";
    }
    if (!t) {
        cout << "-" << endl;
        return;
    }
    cout << t->val << endl;
    print(t->l, id + 1);
    print(t->r, id + 1);
}

template <typename T>
T gc(node_ptr<T> t) {
    return t ? t->gc : 0;
}
template <typename T>
void pull(node_ptr<T> t) {
    if (t) {
        t->gc = safe_gcd(t->val, safe_gcd(gc(t->l), gc(t->r)));
    }
}
template <typename T>
void merge(node_ptr<T> &t, node_ptr<T> l, node_ptr<T> r) {
    if (!l || !r) {
        t = l ? l : r;
        return;
    }
    if (l->prior > r->prior) {
        merge(l->r, l->r, r);
        t = l;
    } else {
        merge(r->l, l, r->l);
        t = r;
    }
    pull(t);
}
template <typename T>
void split(node_ptr<T> t, node_ptr<T> &l, node_ptr<T> &r, pi key) {
    if (!t) {
        return void(l = r = 0);
    }
    if (t->pos >= key) {
        split(t->l, l, t->l, key);
        r = t;
    } else {
        split(t->r, t->r, r, key);
        l = t;
    }
    pull(t);
}
template <typename T>
void insert(node_ptr<T> &t, node_ptr<T> val) {
    node_ptr<T> l = nullptr, m = nullptr, r = nullptr;
    // cout << "A" << endl;
    split(t, l, r, val->pos);
    // cout << "B" << endl;
    split(r, m, r, {val->pos.f, val->pos.s + 1});
    m = val;
    // cout << "D" << endl;
    merge(r, m, r);
    // cout << "X" << endl;
    // cout << gc(l) << " " << gc(r) << " " << gc(t) << endl;
    merge(t, l, r);
    // cout << "A" << endl;
}
template <typename T>
ll query(node_ptr<T> &t, pi a, pi b) {
    node_ptr<T> l = nullptr, m = nullptr, r = nullptr;
    split(t, m, r, b);
    split(m, l, m, a);
    // print(m);
    ll res = gc(m);
    merge(m, l, m);
    merge(t, m, r);
    return res;
}

struct SegTreap {
    node_ptr<ll> val = nullptr;
    int l, r, mid;
    SegTreap *ls, *rs;
    SegTreap(int l, int r) : l(l), r(r), mid((l + r) / 2) {}
    ll query_rect(int a, int b, int c, int d) {
        // cout << "~ QUERY" << endl;
        if (a >= r || b <= l) {
            return 0;
        }
        if (a <= l && b >= r) {
            return query<ll>(val, {c, a}, {d - 1, b});
        }
        return safe_gcd(ls ? ls->query_rect(a, b, c, d) : 0,
                        rs ? rs->query_rect(a, b, c, d) : 0);
    }
    void update(int a, pi pos, ll k) {
        node_ptr<ll> new_node = new node<ll>(k, pos);
        // cout << "~ INSERT " << l << " - " << r << endl;
        insert<ll>(val, new_node);
        // cout << "DONE" << endl;
        // print(val);
        if (l + 1 == r) {
            return;
        }
        if (a < mid) {
            if (!ls) {
                ls = new SegTreap(l, mid);
            }
            ls->update(a, pos, k);
        } else {
            if (!rs) {
                rs = new SegTreap(mid, r);
            }
            rs->update(a, pos, k);
        }
    }
};

const int INF = 1e9 + 1;
SegTreap seg2d(0, INF);
void init(int R, int C) { srand(time(0)); }
void update(int P, int Q, long long K) {
    // cout << "ADD " << P << " " << Q << " " << K << endl;
    seg2d.update(P, {Q, P}, K);
}
long long calculate(int P, int Q, int U, int V) {
    // cout << "CALC " << P << " " << Q << " " << U << " " << V << endl;
    return seg2d.query_rect(P, U + 1, Q, V + 1);
}

Compilation message

game.cpp: In instantiation of 'node<T>::node(T, pi) [with T = long long int; pi = std::pair<int, int>]':
game.cpp:126:52:   required from here
game.cpp:21:8: warning: 'node<long long int>::pos' will be initialized after [-Wreorder]
   21 |     pi pos;
      |        ^~~
game.cpp:20:9: warning:   'int node<long long int>::prior' [-Wreorder]
   20 |     int prior;
      |         ^~~~~
game.cpp:23:5: warning:   when initialized here [-Wreorder]
   23 |     node(T v, pi pos) : val(v), gc(v), pos(pos), prior(rand()) {}
      |     ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1010 ms 28008 KB Output is correct
5 Correct 598 ms 27824 KB Output is correct
6 Correct 1462 ms 25240 KB Output is correct
7 Correct 1579 ms 25148 KB Output is correct
8 Correct 883 ms 15640 KB Output is correct
9 Correct 1570 ms 25012 KB Output is correct
10 Correct 1386 ms 24832 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 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1056 ms 28056 KB Output is correct
13 Correct 2526 ms 24360 KB Output is correct
14 Correct 627 ms 24820 KB Output is correct
15 Correct 2676 ms 24968 KB Output is correct
16 Correct 903 ms 24780 KB Output is correct
17 Correct 1551 ms 15904 KB Output is correct
18 Correct 2853 ms 26120 KB Output is correct
19 Correct 2507 ms 26312 KB Output is correct
20 Correct 2398 ms 25688 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 424 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 968 ms 28048 KB Output is correct
13 Correct 600 ms 27820 KB Output is correct
14 Correct 1397 ms 25196 KB Output is correct
15 Correct 1516 ms 25036 KB Output is correct
16 Correct 878 ms 15388 KB Output is correct
17 Correct 1525 ms 25024 KB Output is correct
18 Correct 1357 ms 24676 KB Output is correct
19 Correct 1150 ms 27936 KB Output is correct
20 Correct 2418 ms 24416 KB Output is correct
21 Correct 630 ms 24816 KB Output is correct
22 Correct 2761 ms 24896 KB Output is correct
23 Correct 783 ms 24884 KB Output is correct
24 Correct 1556 ms 15992 KB Output is correct
25 Correct 2848 ms 26144 KB Output is correct
26 Correct 2448 ms 26428 KB Output is correct
27 Correct 2307 ms 25904 KB Output is correct
28 Correct 769 ms 39052 KB Output is correct
29 Correct 1361 ms 41784 KB Output is correct
30 Correct 3485 ms 31748 KB Output is correct
31 Correct 3055 ms 30752 KB Output is correct
32 Correct 596 ms 29512 KB Output is correct
33 Correct 917 ms 29528 KB Output is correct
34 Correct 1152 ms 35472 KB Output is correct
35 Correct 1548 ms 25220 KB Output is correct
36 Correct 2738 ms 39616 KB Output is correct
37 Correct 2256 ms 39804 KB Output is correct
38 Correct 2220 ms 39368 KB Output is correct
39 Correct 1948 ms 32944 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 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 424 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 272 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 963 ms 27996 KB Output is correct
13 Correct 633 ms 27820 KB Output is correct
14 Correct 1466 ms 25252 KB Output is correct
15 Correct 1578 ms 25024 KB Output is correct
16 Correct 901 ms 15332 KB Output is correct
17 Correct 1519 ms 25076 KB Output is correct
18 Correct 1372 ms 24748 KB Output is correct
19 Correct 1094 ms 27968 KB Output is correct
20 Correct 2480 ms 24368 KB Output is correct
21 Correct 676 ms 24872 KB Output is correct
22 Correct 2857 ms 24936 KB Output is correct
23 Correct 829 ms 24768 KB Output is correct
24 Correct 1619 ms 15848 KB Output is correct
25 Correct 2990 ms 26364 KB Output is correct
26 Correct 2555 ms 26348 KB Output is correct
27 Correct 2356 ms 25756 KB Output is correct
28 Correct 818 ms 39088 KB Output is correct
29 Correct 1374 ms 41816 KB Output is correct
30 Correct 3561 ms 31648 KB Output is correct
31 Correct 3082 ms 30764 KB Output is correct
32 Correct 593 ms 29360 KB Output is correct
33 Correct 897 ms 29464 KB Output is correct
34 Correct 1029 ms 35464 KB Output is correct
35 Correct 1538 ms 25364 KB Output is correct
36 Correct 2793 ms 39628 KB Output is correct
37 Correct 2249 ms 39812 KB Output is correct
38 Correct 2209 ms 39108 KB Output is correct
39 Correct 1041 ms 71296 KB Output is correct
40 Correct 2216 ms 73260 KB Output is correct
41 Correct 5392 ms 60228 KB Output is correct
42 Correct 4942 ms 57944 KB Output is correct
43 Correct 1583 ms 68132 KB Output is correct
44 Correct 1055 ms 53072 KB Output is correct
45 Correct 1934 ms 33104 KB Output is correct
46 Correct 3745 ms 72076 KB Output is correct
47 Correct 3712 ms 72040 KB Output is correct
48 Correct 3402 ms 71648 KB Output is correct
49 Correct 0 ms 212 KB Output is correct