oj.uz

Submission #1112161

# Submission time Handle Problem Language Result Execution time Memory
1112161 2024-11-13T17:33:19 Z steveonalex Game (IOI13_game) C++17
10 / 100
 13000 ms 9708 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 BIT = 30;
const int INF = MASK(BIT) - 1;

struct QuadTree{
    struct Node{
        int child[4];
        ll g;

        Node(){g = 0; memset(child, -1, sizeof child);}
    };

    vector<Node> a;

    QuadTree(){
        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 bit, int id){
        if (bit == 0){
            a[id].g = k;
            return;
        }
        int digit = GETBIT(i, bit-1) + GETBIT(j, bit-1) * 2;
        if (a[id].child[digit] == -1) add_child(a[id].child[digit]);
        update(i, j, k, bit - 1, a[id].child[digit]);

        a[id].g = 0;
        for(int it = 0; it < 4; ++it) 
            if (a[id].child[it] != -1) a[id].g = gcd(a[id].g, a[a[id].child[it]].g);
    }

    void update(int i, int j, ll k){
        update(i, j, k, BIT, 0);
    }

    ll get(int u, int v, int x, int y, int bit, int id){
        // cout << "Get: " << bit << " " << u << " " << v << " " << x << " " << y << "\n";
        int cu = MASK(bit) - 1;
        if (u == 0 && v == 0 && x == cu && y == cu) return a[id].g;
        ll ans = 0;
        for(int it = 0; it < 4; ++it) if (a[id].child[it] != -1){
            int _u = u, _v = v, _x = x, _y = y;
            int cu = MASK(bit-1);
            if (GETBIT(it, 0)) {
                _u -= cu;
                _x -= cu;
            }
            if (GETBIT(it, 1)){
                _v -= cu;
                _y -= cu;
            }

            maximize(_u, 0); maximize(_v, 0);
            minimize(_x, cu-1); minimize(_y, cu-1);
            if (_u > _x || _v > _y) continue;
            // cout << "Go digit: " << it << "\n";
            // cout << _y << "\n";
            ans = gcd(ans, get(_u, _v, _x, _y, bit - 1, a[id].child[it]));
        }

        return ans;
    }

    ll get(int u, int v, int x, int y){
        return get(u, v, x, y, BIT, 0);
    }
};

QuadTree tri;

void init(int R, int C) {
}

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, Q, U, V);
}


// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     clock_t start = clock();

//     init(10, 10);
//     int q; cin >> q;
//     while(q--){
//         int type; cin >> type;
//         if (type == 1){
//             int p, q; ll k; cin >> p >> q >> k;
//             update(p, q, k);
//         }
//         else{
//             int p, q, u, v; cin >> p >> q >> u >> v;
//             cout << calculate(p, q, u, v) << "\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 1 ms 336 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 448 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 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 336 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Execution timed out 13057 ms 4916 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.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 1 ms 336 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 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 1 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 3110 ms 9708 KB Output is correct
13 Correct 12176 ms 5492 KB Output is correct
14 Correct 250 ms 5704 KB Output is correct
15 Execution timed out 13075 ms 4956 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 1 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 1 ms 336 KB Output is correct
10 Correct 1 ms 508 KB Output is correct
11 Correct 1 ms 552 KB Output is correct
12 Execution timed out 13073 ms 4948 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 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 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 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 Execution timed out 13059 ms 4716 KB Time limit exceeded
13 Halted 0 ms 0 KB -