Submission #1160958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160958		SmuggingSpun	Game (IOI13_game)	C++20	100 / 100	2173 ms	62780 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd2(ll X, ll Y){
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
struct Treap_Node{
    int pri, mn, mx, pos;
    ll val, g;
    Treap_Node *l, *r;
    Treap_Node(){
        this->l = this->r = nullptr;
    }
    Treap_Node(int pos, ll val){
        this->l = this->r = nullptr;
        this->pri = rng();
        this->mn = this->mx = this->pos = pos;
        this->val = this->g = val;
    }
    void update(){
        g = val;
        mn = mx = pos;
        if(l != nullptr){
            g = gcd2(g, l->g);
            mn = l->mn;
        }
        if(r != nullptr){
            g = gcd2(g, r->g);
            mx = r->mx;
        }
    }
};
struct Treap{
    Treap_Node *root;
    Treap(){
        this->root = nullptr;
    }
    void split(Treap_Node *n, Treap_Node *&l, Treap_Node *&r, int pos){
        if(n == nullptr){
            l = r = nullptr;
            return;
        }
        if(n->pos < pos){
            split(n->r, n->r, r, pos);
            l = n;
        }
        else{
            split(n->l, l, n->l, pos);
            r = n;
        }
        n->update();
    }
    void merge(Treap_Node *&n, Treap_Node *l, Treap_Node *r){
        if(l == nullptr){
            n = r;
            return;
        }
        if(r == nullptr){
            n = l;
            return;
        }
        if(l->pri < r->pri){
            merge(l->r, l->r, r);
            n = l;
        }
        else{
            merge(r->l, l, r->l);
            n = r;
        }
        n->update();
    }
    bool find(int pos){
        Treap_Node *n = root;
        while(n != nullptr){
            if(n->pos == pos){
                return true;
            }
            n = (n->pos < pos ? n->r : n->l);
        }
        return false;
    }
    void update(Treap_Node *n, int pos, ll val){
        if(n->pos == pos){
            n->val = val;
        }
        else if(n->pos < pos){
            update(n->r, pos, val);
        }
        else{
            update(n->l, pos, val);
        }
        n->update();
    }
    void insert(int pos, ll val){
        if(find(pos)){
            update(root, pos, val);
            return;
        }
        Treap_Node *a, *b;
        split(root, a, b, pos);
        merge(root, a, new Treap_Node(pos, val));
        merge(root, root, b);
    }
    ll query(Treap_Node *n, int u, int v){
        if(n != nullptr){
            //cout << u << " " << v << " " << n->mx << " " << n->mn << " | " << n->pos << " " << n->val << " " << n->g << endl;
        }
        if(n == nullptr || n->mx < u || n->mn > v){
            return 0;
        }
        if(u <= n->mn && v >= n->mx){
            return n->g;
        }
        ll ans = gcd2(query(n->l, u, v), query(n->r, u, v));
        if(u <= n->pos && v >= n->pos){
            ans = gcd2(ans, n->val);
        }
        return ans;
    }
    ll query(int u, int v){
        return root == nullptr ? 0 : query(root, u, v);
    }
};
int cnt_st_node = 0;
struct Segment_Tree{
    Treap treap;
    Segment_Tree *l, *r;
    int low, high;
    Segment_Tree(){
        this->l = this->r = nullptr;
    }
    Segment_Tree(int low, int high){
        this->l = this->r = nullptr;
        this->low = low;
        this->high = high;
    }
    void fix(int pos){
        ll val = 0;
        if(l != nullptr){
            val = gcd2(val, l->treap.query(pos, pos));
        }
        if(r != nullptr){
            val = gcd2(val, r->treap.query(pos, pos));
        }
        treap.insert(pos, val);
    }
    void new_left(){
        if(l == nullptr){
            l = new Segment_Tree(low, (low + high) >> 1);
        }       
    }
    void new_right(){
        if(r == nullptr){
            r = new Segment_Tree(((low + high) >> 1) + 1, high);
        }
    }
    void update(int x, int y, ll val){
        if(low == high){
            treap.insert(y, val);
            return;
        }
        if(x > ((low + high) >> 1)){
            new_right();
            r->update(x, y, val);
        }
        else{
            new_left();
            l->update(x, y, val);
        }
        fix(y);
    }
    ll query(int x, int y, int u, int v){
        if(low > u || high < x){
            return 0;
        }
        if(x <= low && u >= high){
            return treap.query(y, v);
        }
        ll g = 0;
        if(l != nullptr){
            g = gcd2(g, l->query(x, y, u, v));
        }
        if(r != nullptr){
            g = gcd2(g, r->query(x, y, u, v));
        }
        return g;
    }
};
Segment_Tree st;
void init(int R, int C){
    st = Segment_Tree(0, R - 1);
}
void update(int P, int Q, ll K){
    st.update(P, Q, K);
    // cout << " ||| " << endl;
    // ll temp = st.query(P, Q, P, Q);
    // cout << temp << " ||||| " << endl;
}
ll calculate(int P, int Q, int U, int V){
    return st.query(P, Q, U, V);
}

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