Submission #566351

#	Time	Username	Problem	Language	Result	Execution time	Memory
566351		pls33	Game (IOI13_game)	C++17	100 / 100	3471 ms	73296 KiB

game

#include "game.h"
#include <bits/stdc++.h>
    
using namespace std;
    
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
    
#pragma endregion
    
int64_t gcd2(int64_t x, int64_t y) {
    return !y ? x : gcd2(y, x % y);
}

int rnd() { 
    return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15));
}

struct tnode_t {
    tnode_t *l, *r;

    int pos, key, min, max;
    int64_t val, g;

    tnode_t(int position, int64_t value){
        l = nullptr;
        r = nullptr;
        
        pos = position;
        min = position;
        max = position;

        key = rnd();
        val = value;
        g = value;
    }

    void update(){
        g = val;
        if(l){
            g = gcd2(g, l->g);
        }
        if(r){
            g = gcd2(g, r->g);
        }

        min = l ? l->min : pos;
        max = r ? r->max : pos;
    }
};

struct treap_t {
    tnode_t *root;

    treap_t(){
        root = nullptr;
        srand(rnd());
    }

    void split(tnode_t *node, int pos, tnode_t* &l, tnode_t* &r){
        if(!node){
            l = nullptr;
            r = nullptr;

            return;
        }

        if(node->pos < pos){
            split(node->r, pos, l, r);

            node->r = l;
            l = node;
        }
        else {
            split(node->l, pos, l, r);
            node->l = r;
            r = node;
        }

        node->update();
    }

    tnode_t* merge(tnode_t *l, tnode_t *r){
        if(!l || !r){
            return l ? l : r;
        }

        if(l->key < r->key){
            l->r = merge(l->r, r);
            l->update();

            return l;
        }

        r->l = merge(l, r->l);
        r->update();

        return r;
    }

    bool find(int pos){
        tnode_t* node = root;
        while(node){
            if(node->pos == pos){
                return true;
            }

            if(node->pos > pos){
                node = node->l;
            }
            else {
                node = node->r;
            }
        }

        return false;
    }

    void update(tnode_t *node, int pos, int64_t val){
        if(node->pos == pos){
            node->val = val;
            node->update();

            return;
        }

        if(node->pos > pos){
            update(node->l, pos, val);
        }
        else {
            update(node->r, pos, val);
        }

        node->update();
    }

    void insert(int pos, int64_t val){
        if(find(pos)){
            update(root, pos, val);

            return;
        }

        tnode_t *l = nullptr, *r = nullptr;
        split(root, pos, l, r);

        tnode_t *merged_left = merge(l, new tnode_t(pos, val));
        root = merge(merged_left, r);
    }

    int64_t query(tnode_t *node, int left, int right){
        if(node->max < left || node->min > right){
            return 0;
        }
        
        if(left <= node->min && node->max <= right){
            return node->g;
        }

        int64_t res = (left <= node->pos && node->pos <= right) ? node->val : 0;
        if(node->l){
            res = gcd2(res, query(node->l, left, right));
        }
        if(node->r){
            res = gcd2(res, query(node->r, left, right));
        }

        return res;
    }

    int64_t query(int left, int right){
        if(!root){
            return 0;
        }

        return query(root, left, right);
    }
};

struct snode_t {
    snode_t *l, *r;
    treap_t treap;
    int left, right;

    snode_t(){
        l = nullptr;
        r = nullptr;
    }

    snode_t(int left_bound, int right_bound){
        l = nullptr;
        r = nullptr;

        left = left_bound;
        right = right_bound;
    }

    void add_left(){
        if(!l){
            l = new snode_t(left, (left + right) / 2);
        }
    }

    void add_right(){
        if(!r){
            r = new snode_t((left + right) / 2 + 1, right);
        }
    }

    void fix(int pos){
        int64_t val = 0;
        if(l){
            val = gcd2(val, l->treap.query(pos, pos));
        }
        if(r){
            val = gcd2(val, r->treap.query(pos, pos));
        }

        treap.insert(pos, val);
    }

    void update(int row, int col, int64_t val){
        if(right < row || row < left){
            return;
        }

        if(left == right){
            treap.insert(col, val);
            return;
        }

        if(row <= (left + right) / 2){
            add_left();
            l->update(row, col, val);
        }
        else {
            add_right();
            r->update(row, col, val);
        }

        fix(col);
    }

    int64_t query(int row0, int row1, int col0, int col1){
        if(row0 > right || row1 < left){
            return 0;
        }

        if(row0 <= left && right <= row1){
            return treap.query(col0, col1);
        }

        int64_t res = 0;
        if(l){
            res = gcd2(res, l->query(row0, row1, col0, col1));
        }
        if(r){
            res = gcd2(res, r->query(row0, row1, col0, col1));
        }

        return res;
    }
};

snode_t tree;

void init(int row_count, int col_count) {
    srand(12341234);

    tree = snode_t(0, row_count);
}
    
void update(int row, int col, long long val) {
    tree.update(row, col, val);
}
    
long long calculate(int row0, int col0, int row1, int col1) {
    return tree.query(row0, row1, col0, col1);
}

Compilation message (stderr)

game.cpp:6: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    6 | #pragma region dalykai
      | 
game.cpp:30: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   30 | #pragma endregion
      |

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