oj.uz

Submission #1112655

# Submission time Handle Problem Language Result Execution time Memory
1112655 2024-11-14T14:00:11 Z steveonalex Game (IOI13_game) C++17
100 / 100
 2349 ms 51268 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());
    }
 
    void update(int i, int j, ll k, int l, int r, int id){
        if (l == r) {a[id].g.update(j, k); return;}
        int mid = (l + r) >> 1;
        if (i <= mid){
            if (a[id].child[0] == -1) add_child(a[id].child[0]);
            update(i, j, k, l, mid, a[id].child[0]);
        }
        else{
            if (a[id].child[1] == -1) add_child(a[id].child[1]);
            update(i, j, k, mid + 1, r, a[id].child[1]);
        }
        ll ans = 0;
        for(int i = 0; i <= 1; ++i)
        if (a[id].child[i] != -1) ans = gcd(ans, a[a[id].child[i]].g.get(j, j));
        a[id].g.update(j, 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 4 ms 440 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 4 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 2 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 1 ms 336 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 752 ms 22592 KB Output is correct
5 Correct 528 ms 22336 KB Output is correct
6 Correct 1060 ms 19956 KB Output is correct
7 Correct 1133 ms 19808 KB Output is correct
8 Correct 605 ms 12872 KB Output is correct
9 Correct 1109 ms 19680 KB Output is correct
10 Correct 1002 ms 19528 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 4 ms 336 KB Output is correct
3 Correct 4 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 2 ms 480 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 732 ms 12996 KB Output is correct
13 Correct 967 ms 7888 KB Output is correct
14 Correct 321 ms 5704 KB Output is correct
15 Correct 1030 ms 9712 KB Output is correct
16 Correct 537 ms 11592 KB Output is correct
17 Correct 837 ms 10468 KB Output is correct
18 Correct 1448 ms 13136 KB Output is correct
19 Correct 1377 ms 13128 KB Output is correct
20 Correct 1195 ms 12616 KB Output is correct
21 Correct 1 ms 504 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 472 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 2 ms 336 KB Output is correct
12 Correct 720 ms 22716 KB Output is correct
13 Correct 558 ms 22528 KB Output is correct
14 Correct 1109 ms 19868 KB Output is correct
15 Correct 1080 ms 19744 KB Output is correct
16 Correct 621 ms 12932 KB Output is correct
17 Correct 1136 ms 19872 KB Output is correct
18 Correct 986 ms 19528 KB Output is correct
19 Correct 774 ms 13124 KB Output is correct
20 Correct 1051 ms 8008 KB Output is correct
21 Correct 321 ms 5708 KB Output is correct
22 Correct 1096 ms 9800 KB Output is correct
23 Correct 509 ms 11592 KB Output is correct
24 Correct 836 ms 10380 KB Output is correct
25 Correct 1457 ms 13164 KB Output is correct
26 Correct 1353 ms 13304 KB Output is correct
27 Correct 1167 ms 12720 KB Output is correct
28 Correct 468 ms 28592 KB Output is correct
29 Correct 925 ms 31392 KB Output is correct
30 Correct 1305 ms 22956 KB Output is correct
31 Correct 1155 ms 19876 KB Output is correct
32 Correct 316 ms 10056 KB Output is correct
33 Correct 413 ms 10312 KB Output is correct
34 Correct 567 ms 24824 KB Output is correct
35 Correct 781 ms 20588 KB Output is correct
36 Correct 1538 ms 29104 KB Output is correct
37 Correct 1260 ms 29320 KB Output is correct
38 Correct 1280 ms 28788 KB Output is correct
39 Correct 950 ms 25908 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 440 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 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 2 ms 440 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 814 ms 22748 KB Output is correct
13 Correct 623 ms 22500 KB Output is correct
14 Correct 1095 ms 20040 KB Output is correct
15 Correct 1088 ms 19676 KB Output is correct
16 Correct 607 ms 12984 KB Output is correct
17 Correct 1192 ms 19784 KB Output is correct
18 Correct 961 ms 19560 KB Output is correct
19 Correct 717 ms 13084 KB Output is correct
20 Correct 986 ms 8008 KB Output is correct
21 Correct 311 ms 5704 KB Output is correct
22 Correct 1006 ms 9544 KB Output is correct
23 Correct 495 ms 11592 KB Output is correct
24 Correct 815 ms 10516 KB Output is correct
25 Correct 1517 ms 13140 KB Output is correct
26 Correct 1364 ms 13152 KB Output is correct
27 Correct 1140 ms 12408 KB Output is correct
28 Correct 467 ms 28804 KB Output is correct
29 Correct 980 ms 31364 KB Output is correct
30 Correct 1271 ms 23020 KB Output is correct
31 Correct 1147 ms 19896 KB Output is correct
32 Correct 298 ms 10312 KB Output is correct
33 Correct 429 ms 10312 KB Output is correct
34 Correct 667 ms 25080 KB Output is correct
35 Correct 758 ms 20664 KB Output is correct
36 Correct 1386 ms 29316 KB Output is correct
37 Correct 1337 ms 29360 KB Output is correct
38 Correct 1245 ms 28904 KB Output is correct
39 Correct 617 ms 49180 KB Output is correct
40 Correct 1711 ms 51268 KB Output is correct
41 Correct 2108 ms 39600 KB Output is correct
42 Correct 1769 ms 31668 KB Output is correct
43 Correct 979 ms 45976 KB Output is correct
44 Correct 468 ms 10572 KB Output is correct
45 Correct 991 ms 25964 KB Output is correct
46 Correct 2349 ms 50172 KB Output is correct
47 Correct 2079 ms 50008 KB Output is correct
48 Correct 2302 ms 49524 KB Output is correct
49 Correct 1 ms 336 KB Output is correct