oj.uz

Submission #1112666

# Submission time Handle Problem Language Result Execution time Memory
1112666 2024-11-14T14:20:02 Z steveonalex Game (IOI13_game) C++17
100 / 100
 2155 ms 49184 KB 
#include <bits/stdc++.h>
#include "game.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned int ul;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll gcd(ll a, ll b){return __gcd(a, b);}
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T the_array_itself, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: the_array_itself) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }
 
const int INF = 1e9 + 69;
struct Treap{
    struct Node{
        int val, priority;
        ll g, sum_g; // value of the current node, and value of the entire subtree
        Node* child[2];
        Node(int val): val(val), priority(rngesus(0, MASK(30) - 1)){
            g = sum_g = 0;
            child[0] = child[1] = nullptr;
        }
    };

    Node* root;

    Treap(){
        root = nullptr;
    }

    void merge_children(Node* cur){
        if (cur == nullptr) return;
        ll ans= cur -> g;
        for(int i = 0; i <= 1; ++i) if (cur -> child[i] != nullptr) {
            ans = gcd(ans, cur -> child[i] -> sum_g);
        }
        cur -> sum_g = ans;
    }

    void split(Node* cur, int x, Node*& L, Node*& R){ // split up to a point x
        if (cur == nullptr) {L = R = nullptr;return;}
        if (x < cur -> val){
            split(cur -> child[0], x, L, cur -> child[0]);
            R = cur;
        }
        else{
            split(cur -> child[1], x, cur -> child[1], R);
            L = cur;
        }
        merge_children(L); merge_children(R);
    }       

    void merge(Node*& cur, Node* L, Node* R){
        if (L == nullptr) cur = R;
        else if (R == nullptr) cur = L;
        else{
            if (R -> priority > L -> priority) {
                cur = R;
                merge(cur -> child[0], L, R -> child[0]);
            }
            else{
                cur = L;
                merge(cur -> child[1], L -> child[1], R);
            }
        }
        merge_children(cur);
    }

    void update(int x, ll k){
        Node *L, *mid, *R;
        split(root, x-1, L, mid);
        split(mid, x, mid, R);
        if (mid == nullptr) mid = new Node(x);
        mid -> g = mid -> sum_g = k;
        merge(root, L, mid);
        merge(root, root, R);
    }

    ll get(int u, int v, int l, int r, Node* id){
        if (id == nullptr) return 0;
        if (u <= l && r <= v) return id -> sum_g;
        int mid = id -> val;
        ll ans = 0;
        if (u <= mid && mid <= v) ans = id -> g;
        if (u < mid) ans = gcd(ans, get(u, v, l, mid - 1, id -> child[0]));
        if (v > mid) ans = gcd(ans, get(u, v, mid + 1, r, id -> child[1]));
        return ans;
    }

    ll get(int u, int v){
        return get(u, v, 0, INF, root);
    }

    void clear(Node* cur){
        for(int i = 0; i<= 1; ++i)
        if (cur -> child[i] != nullptr) {
            clear(cur->child[i]);
            delete cur -> child[i];
        }
    }

    void clear(){
        if (root != nullptr){
            clear(root);
            delete root;
        }
    }
};
 
struct Trie2D{
    struct Node{
        int child[2];
        Treap g;
        Node(){g = Treap(); memset(child, -1, sizeof child);}
    };
 
    int l, r;
    vector<Node> a;
 
    Trie2D(){}
    Trie2D(int l, int r): l(l), r(r){
        a.push_back(Node());
    }
 
    void add_child(int &x){
        x = a.size();
        a.push_back(Node());
    }
 
    ll update(int i, int j, ll k, int l, int r, int id){
        if (l == r) {a[id].g.update(j, k); return k;}
        int mid = (l + r) >> 1;
        ll ans = 0;
        if (i <= mid){
            if (a[id].child[0] == -1) add_child(a[id].child[0]);
            ans = update(i, j, k, l, mid, a[id].child[0]);
            if (a[id].child[1] != -1) ans = gcd(ans, a[a[id].child[1]].g.get(j, j));
        }
        else{
            if (a[id].child[1] == -1) add_child(a[id].child[1]);
            ans = update(i, j, k, mid + 1, r, a[id].child[1]);
            if (a[id].child[0] != -1) ans = gcd(ans, a[a[id].child[0]].g.get(j, j));
        }
        a[id].g.update(j, ans);
        return ans;
    }
 
    void update(int i, int j, ll k){
        update(i, j, k, l, r, 0);
    }
 
    ll get(int u, int v, int x, int y, int l, int r, int id){
        if (u <= l && r <= v) return a[id].g.get(x, y);
        int mid = (l + r) >> 1;
        ll ans = 0;
        if (u <= mid && a[id].child[0] != -1) ans = gcd(ans, get(u, v, x, y, l, mid, a[id].child[0]));
        if (v > mid && a[id].child[1] != -1) ans = gcd(ans, get(u, v, x, y, mid + 1, r, a[id].child[1]));
        return ans;
    }
 
    ll get(int u, int v, int x, int y){return get(u, v, x, y, l, r, 0);}
};
 
Trie2D tri;
void init(int R, int C) {
    tri = Trie2D(0, INF);
}
 
void update(int P, int Q, long long K) {
    tri.update(P, Q, K);
    /* ... */
}
 
long long calculate(int P, int Q, int U, int V) {
    if (P > U) swap(P, U);
    if (Q > V) swap(Q, V);
    return tri.get(P, U, Q, V);
}
 
 
// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
//     clock_t start = clock();
 
//     init(2, 3);
//     update(0, 0, 20);
//     update(0, 2, 15);
//     update(1, 1, 12);
//     cout << calculate(0, 0, 0, 2) << "\n";
 
 
 
 
//     cerr << "Time elapsed: " << clock() - start << " ms!\n";
 
//     return 0;
// }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 520 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 504 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 636 ms 22532 KB Output is correct
5 Correct 475 ms 21832 KB Output is correct
6 Correct 1035 ms 20012 KB Output is correct
7 Correct 1098 ms 19016 KB Output is correct
8 Correct 632 ms 11116 KB Output is correct
9 Correct 1101 ms 19824 KB Output is correct
10 Correct 961 ms 19272 KB Output is correct
11 Correct 1 ms 336 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 444 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 3 ms 508 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 721 ms 11336 KB Output is correct
13 Correct 953 ms 7316 KB Output is correct
14 Correct 306 ms 5448 KB Output is correct
15 Correct 1006 ms 8008 KB Output is correct
16 Correct 451 ms 11124 KB Output is correct
17 Correct 827 ms 10240 KB Output is correct
18 Correct 1441 ms 12104 KB Output is correct
19 Correct 1388 ms 12856 KB Output is correct
20 Correct 1124 ms 10056 KB Output is correct
21 Correct 1 ms 336 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 444 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 508 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 643 ms 22108 KB Output is correct
13 Correct 493 ms 22444 KB Output is correct
14 Correct 1097 ms 17992 KB Output is correct
15 Correct 1112 ms 17636 KB Output is correct
16 Correct 601 ms 12752 KB Output is correct
17 Correct 1108 ms 15060 KB Output is correct
18 Correct 965 ms 14712 KB Output is correct
19 Correct 689 ms 13128 KB Output is correct
20 Correct 925 ms 7936 KB Output is correct
21 Correct 308 ms 3656 KB Output is correct
22 Correct 961 ms 5312 KB Output is correct
23 Correct 489 ms 11592 KB Output is correct
24 Correct 868 ms 7496 KB Output is correct
25 Correct 1446 ms 12956 KB Output is correct
26 Correct 1399 ms 12300 KB Output is correct
27 Correct 1162 ms 12476 KB Output is correct
28 Correct 428 ms 29104 KB Output is correct
29 Correct 867 ms 30700 KB Output is correct
30 Correct 1244 ms 22508 KB Output is correct
31 Correct 1149 ms 19592 KB Output is correct
32 Correct 305 ms 9544 KB Output is correct
33 Correct 396 ms 9008 KB Output is correct
34 Correct 572 ms 18608 KB Output is correct
35 Correct 801 ms 18512 KB Output is correct
36 Correct 1488 ms 28468 KB Output is correct
37 Correct 1168 ms 18864 KB Output is correct
38 Correct 1240 ms 26760 KB Output is correct
39 Correct 945 ms 24096 KB Output is correct
40 Correct 1 ms 336 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 4 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 693 ms 20712 KB Output is correct
13 Correct 535 ms 21832 KB Output is correct
14 Correct 1062 ms 19176 KB Output is correct
15 Correct 1065 ms 15048 KB Output is correct
16 Correct 585 ms 12956 KB Output is correct
17 Correct 1067 ms 19016 KB Output is correct
18 Correct 1002 ms 14664 KB Output is correct
19 Correct 684 ms 12360 KB Output is correct
20 Correct 946 ms 7256 KB Output is correct
21 Correct 300 ms 840 KB Output is correct
22 Correct 984 ms 8776 KB Output is correct
23 Correct 432 ms 7496 KB Output is correct
24 Correct 821 ms 9544 KB Output is correct
25 Correct 1393 ms 7636 KB Output is correct
26 Correct 1320 ms 10568 KB Output is correct
27 Correct 1145 ms 9996 KB Output is correct
28 Correct 442 ms 19632 KB Output is correct
29 Correct 937 ms 29104 KB Output is correct
30 Correct 1275 ms 16060 KB Output is correct
31 Correct 1146 ms 12984 KB Output is correct
32 Correct 324 ms 8076 KB Output is correct
33 Correct 369 ms 1352 KB Output is correct
34 Correct 521 ms 23480 KB Output is correct
35 Correct 774 ms 10780 KB Output is correct
36 Correct 1438 ms 19916 KB Output is correct
37 Correct 1145 ms 18932 KB Output is correct
38 Correct 1309 ms 29148 KB Output is correct
39 Correct 685 ms 47012 KB Output is correct
40 Correct 1491 ms 49184 KB Output is correct
41 Correct 1881 ms 35932 KB Output is correct
42 Correct 1717 ms 24400 KB Output is correct
43 Correct 942 ms 42916 KB Output is correct
44 Correct 442 ms 8692 KB Output is correct
45 Correct 1037 ms 24248 KB Output is correct
46 Correct 1971 ms 39076 KB Output is correct
47 Correct 2155 ms 47820 KB Output is correct
48 Correct 1940 ms 38592 KB Output is correct
49 Correct 1 ms 336 KB Output is correct