oj.uz

Submission #1112334

# Submission time Handle Problem Language Result Execution time Memory
1112334 2024-11-14T05:12:52 Z steveonalex Game (IOI13_game) C++17
80 / 100
 2562 ms 256000 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 Trie{
    struct Node{
        int child[2];
        ll g;
        Node(){g = 0; memset(child, -1, sizeof child);}
    };
 
    int l, r;
    vector<Node> a;
 
    Trie(){}
    Trie(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, ll k, int l, int r, int id){
        if (l == r){a[id].g = k; return;}
        int mid = (l + r) >> 1;
        if (i <= mid){
            if (a[id].child[0] == -1) add_child(a[id].child[0]);
            update(i, k, l, mid, a[id].child[0]);
        }
        else{
            if (a[id].child[1] == -1) add_child(a[id].child[1]);
            update(i, k, mid + 1, r, a[id].child[1]);
        }
        a[id].g = 0;
        for(int i = 0; i <= 1; ++i)
        if (a[id].child[i] != -1) a[id].g = gcd(a[id].g, a[a[id].child[i]].g);
    }
 
    void update(int i, ll k){
        update(i, k, l, r, 0);
    }
 
    ll get(int u, int v, int l, int r, int id){
        if (u <= l && r <= v) return a[id].g;
        int mid = (l + r) >> 1;
        ll ans = 0;
        if (u <= mid && a[id].child[0] != -1) ans = gcd(ans, get(u, v, l, mid, a[id].child[0]));
        if (v > mid && a[id].child[1] != -1) ans = gcd(ans, get(u, v, mid + 1, r, a[id].child[1]));
        return ans;
    }
 
    ll get(int u, int v){return get(u, v, l, r, 0);}
};
 
struct Trie2D{
    struct Node{
        int child[2];
        Trie g;
        Node(){g = Trie(0, INF); 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 3 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 444 KB Output is correct
9 Correct 2 ms 1028 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 1 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 561 ms 33460 KB Output is correct
5 Correct 470 ms 33940 KB Output is correct
6 Correct 544 ms 30748 KB Output is correct
7 Correct 573 ms 30268 KB Output is correct
8 Correct 376 ms 20668 KB Output is correct
9 Correct 580 ms 30640 KB Output is correct
10 Correct 536 ms 30500 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 2 ms 592 KB Output is correct
3 Correct 2 ms 700 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 2 ms 592 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 592 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 828 ms 18860 KB Output is correct
13 Correct 944 ms 9796 KB Output is correct
14 Correct 357 ms 5704 KB Output is correct
15 Correct 1054 ms 13896 KB Output is correct
16 Correct 410 ms 21332 KB Output is correct
17 Correct 695 ms 16836 KB Output is correct
18 Correct 984 ms 22744 KB Output is correct
19 Correct 910 ms 22688 KB Output is correct
20 Correct 943 ms 22048 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 2 ms 696 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 2 ms 700 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 577 ms 33284 KB Output is correct
13 Correct 490 ms 34112 KB Output is correct
14 Correct 578 ms 30780 KB Output is correct
15 Correct 590 ms 30268 KB Output is correct
16 Correct 393 ms 20648 KB Output is correct
17 Correct 564 ms 30524 KB Output is correct
18 Correct 550 ms 30312 KB Output is correct
19 Correct 750 ms 18796 KB Output is correct
20 Correct 954 ms 10532 KB Output is correct
21 Correct 358 ms 5940 KB Output is correct
22 Correct 1031 ms 13896 KB Output is correct
23 Correct 385 ms 21320 KB Output is correct
24 Correct 687 ms 16968 KB Output is correct
25 Correct 1111 ms 22712 KB Output is correct
26 Correct 918 ms 22736 KB Output is correct
27 Correct 856 ms 22088 KB Output is correct
28 Correct 566 ms 160024 KB Output is correct
29 Correct 1185 ms 174392 KB Output is correct
30 Correct 2562 ms 124792 KB Output is correct
31 Correct 2260 ms 104100 KB Output is correct
32 Correct 336 ms 10492 KB Output is correct
33 Correct 491 ms 12664 KB Output is correct
34 Correct 701 ms 169156 KB Output is correct
35 Correct 832 ms 91644 KB Output is correct
36 Correct 1457 ms 172996 KB Output is correct
37 Correct 1262 ms 173504 KB Output is correct
38 Correct 1188 ms 172664 KB Output is correct
39 Correct 991 ms 137292 KB Output is correct
40 Correct 1 ms 336 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 2 ms 592 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 604 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 580 ms 33500 KB Output is correct
13 Correct 484 ms 34216 KB Output is correct
14 Correct 573 ms 30856 KB Output is correct
15 Correct 542 ms 30268 KB Output is correct
16 Correct 385 ms 20896 KB Output is correct
17 Correct 579 ms 30780 KB Output is correct
18 Correct 553 ms 30272 KB Output is correct
19 Correct 817 ms 18864 KB Output is correct
20 Correct 916 ms 10456 KB Output is correct
21 Correct 365 ms 5704 KB Output is correct
22 Correct 1067 ms 13812 KB Output is correct
23 Correct 439 ms 21320 KB Output is correct
24 Correct 720 ms 16852 KB Output is correct
25 Correct 1092 ms 22620 KB Output is correct
26 Correct 975 ms 22856 KB Output is correct
27 Correct 892 ms 22088 KB Output is correct
28 Correct 574 ms 159260 KB Output is correct
29 Correct 1127 ms 174916 KB Output is correct
30 Correct 2323 ms 125484 KB Output is correct
31 Correct 2263 ms 104196 KB Output is correct
32 Correct 344 ms 10512 KB Output is correct
33 Correct 463 ms 12628 KB Output is correct
34 Correct 733 ms 169664 KB Output is correct
35 Correct 789 ms 91740 KB Output is correct
36 Correct 1448 ms 172548 KB Output is correct
37 Correct 1249 ms 173428 KB Output is correct
38 Correct 1208 ms 173168 KB Output is correct
39 Runtime error 815 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -