Submission #1128353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128353		trMatherz	Game (IOI13_game)	C++17	63 / 100	2702 ms	321536 KiB

game

#include "game.h"
// #include <iostream> 
 
 
// #include <fstream>
// std::ifstream cin ("boarding.in");
// std::ofstream cout ("boarding.out");
 
 
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <tuple>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <complex>
#include <tuple> 
 

using namespace std;
using namespace __gnu_pbds;

 
typedef long long ll;
template <typename T, typename U>
bool emin(T &a, const U &b) { return b < a ? a = b, true : false; }
template <typename T, typename U>
bool emax(T &a, const U &b) { return b > a ? a = b, true : false; }
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef uint64_t hash_t;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const ll M = (1LL << 61) - 1;
const ll B = uniform_int_distribution<ll>(0, M - 1)(rng);
__int128 mul(ll a, ll b) { return (__int128)a * b; }
__int128 add(ll a, ll b) { return (__int128)a + b; }
ll mod_mul(ll a, ll b) { return mul(a, b) % M; }
ll mod_add(ll a, ll b) { return add(a, b) % M; }


ll gcd2(ll x, ll y) {
	if (y == 0) return x;
	return gcd2(y, x % y);
}

struct node {
    ll lef, rig; 
    ll v; 
    node *l, *r; 
    node(ll tl, ll tr) : lef(tl), rig(tr), l(NULL), r(NULL), v(0) {}
    node *make(int x) {
        if(x == 0) {
            if(!l) l = new node(lef, (lef + rig) / 2);
            return l;
        } else {
            if(!r) r = new node((lef + rig) / 2 + 1, rig); 
            return r;  
        } 
    }

};

struct seg {
    ll lef, rig; 
    node *root; 
    seg *l, *r; 
    seg(ll tl, ll tr) : lef(tl), rig(tr), l(NULL), r(NULL), root(NULL) {}
    seg *make(int x) {
        if(x == 0) {
            if(!l) l = new seg(lef, (lef + rig) / 2);
            return l;
        } else {
            if(!r) r = new seg((lef + rig) / 2 + 1, rig); 
            return r;  
        } 
    }
    node *make2() {
        if(!root) root = new node(0, (ll) 1e9); 
        return root; 
    }
} *root; 


ll get(node *x) { return x ? x->v : 0; }

void upd(node *x, int c, ll z) {
    if(x->lef == x->rig) return void(x->v = z); 
    ll m = (x->lef + x->rig) / 2; 
    if(c <= m) upd(x->make(0), c, z);
    else upd(x->make(1), c, z); 
    x->v = gcd2(get(x->l), get(x->r)); 
}

ll get(node *x, int rl, int rr) {
    if(!x || rr < x->lef || rl > x->rig) return 0; 
    if(rl <= x->lef && x->rig <= rr) return x->v; 
    return gcd2(get(x->l, rl, rr), get(x->r, rl, rr)); 
}

void upd(seg *x, int c, int y, ll z) {
    if(x->lef == x->rig) { upd(x->make2(), y, z); return; }
    ll m = (x->lef + x->rig) / 2; 
    if(c <= m) upd(x->make(0), c, y, z);
    else upd(x->make(1), c, y, z); 
    ll nz = gcd2(x->l ? get(x->l->root, y, y) : 0, x->r ? get(x->r->root, y, y) : 0); 
    upd(x->make2(), y, nz); 
}

ll get(seg *x, int rl, int rr, int y1, int y2) {
    if(!x || rr < x->lef || rl > x->rig) return 0; 
    if(rl <= x->lef && x->rig <= rr) return get(x->root, y1, y2);
    return gcd2(get(x->l, rl, rr, y1, y2), get(x->r, rl, rr, y1, y2)); 
}

void init(int R, int C) {
    root = new seg(0, (ll) 1e9); 
}

void update(int P, int Q, ll K) {
    upd(root, P, Q, K); 
}

ll calculate(int P, int Q, int U, int V) {
    return get(root, P, U, Q, V); 
}

// int main() {
//     int R, C, N;
//     cin >> R >> C >> N; 
//     init(R, C);
//     for(int i = 0; i < N; i++) {
//         int w; 
//         cin >> w;
//         if(w == 1) {
//             ll P, Q, 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) << endl;
//         }
//     } 
// }

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20