Submission #565562

#	Time	Username	Problem	Language	Result	Execution time	Memory
565562		pls33	Game (IOI13_game)	C++17	80 / 100	3911 ms	256000 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

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int8_t ranges(p32 a, p32 b){
    if(a.first >= b.second || a.second <= b.first){
        return 0;
    }

    if(a.first >= b.first && a.second <= b.second){
        return 1;
    }

    return 2;
}

struct cnode_t;
struct rnode_t;

deque<cnode_t> cnodes;
deque<rnode_t> rnodes;

cnode_t* fetch_cnode(){
    cnodes.emplace_back();
    return &cnodes.back();
}
rnode_t* fetch_rnode(){
    rnodes.emplace_back();
    return &rnodes.back();
}

// column node
struct cnode_t {
    int64_t val = 0;

    cnode_t* left = nullptr;
    cnode_t* right = nullptr;

    void expand(p32 range, p32 dest){
        if(range.second - range.first == 1){
            return;
        }

        int mid = (range.first + range.second) / 2;
        if(!left && ranges({range.first, mid}, dest)){
            left = fetch_cnode();
        }
        if(!right && ranges({mid, range.second}, dest)){
            right = fetch_cnode();
        }
    }
};

// row node
struct rnode_t {
    cnode_t* col = nullptr;

    rnode_t* left = nullptr;
    rnode_t* right = nullptr;

    rnode_t(){
        col = fetch_cnode();
    }

    void expand(p32 range, p32 dest){
        if(range.second - range.first == 1){
            return;
        }

        int mid = (range.first + range.second) / 2;
        if(!left && ranges({range.first, mid}, dest)){
            left = fetch_rnode();
        }
        if(!right && ranges({mid, range.second}, dest)){
            right = fetch_rnode();
        }
    }
};

rnode_t* tree;
p32 __row_range;
p32 __col_range;

int64_t query_col(cnode_t *node, p32 range, p32 dest);

int64_t get_val(cnode_t *node){
    if(!node){
        return 0;
    }

    return gcd2((node->left)  ? node->left->val  : 0,
                (node->right) ? node->right->val : 0);
}

int64_t get_val(cnode_t *left, cnode_t *right){
    return gcd2((left)  ? left->val  : 0,
                (right) ? right->val : 0);
}

void update_base(cnode_t *node, int64_t val, p32 range, p32 dest){
    if(!node){
        return;
    }

    int8_t type = ranges(range, dest);
    if(!type){
        return;
    }

    if(type == 1){
        node->val = val;

        return;
    }

    node->expand(range, dest);

    int mid = (range.first + range.second) / 2;
    update_base(node->left, val, {range.first, mid}, dest);
    update_base(node->right, val, {mid, range.second}, dest);

    node->val = get_val(node);
    return;
}

int merge_count = 0;

void update_merge(cnode_t *node, cnode_t *left, cnode_t *right, p32 range, p32 dest){
    if(!node){
        return;
    }
    int8_t type = ranges(range, dest);

    if(!type){
        return;
    }

    if(type == 1){
        node->val = get_val(left, right);

        return;
    }

    bool add_left = !(node->left), add_right = !(node->right);
    node->expand(range, dest);
    add_left = add_left && node->left;
    add_right = add_right && node->right;

    merge_count = merge_count + add_left + add_right;
    

    int mid = (range.first + range.second) / 2;
    update_merge(node->left, 
                    (left) ? left->left : nullptr,
                    (right) ? right->left : nullptr,
                    {range.first, mid}, dest);

    update_merge(node->right, 
                    (left) ? left->right : nullptr,
                    (right) ? right->right : nullptr,
                    {mid, range.second}, dest);

    node->val = get_val(left, right);
}

void update_row(rnode_t *node, int64_t val, p32 range, p32 dest, p32 col_dest){
    if(!node){
        return;
    }

    int8_t type = ranges(range, dest);
    if(!type){
        return;
    }

    if(type == 1){
        update_base(node->col, val, __col_range, col_dest);

        return;
    }

    node->expand(range, dest);

    int mid = (range.first + range.second) / 2;
    update_row(node->left, val, {range.first, mid}, dest, col_dest);
    update_row(node->right, val, {mid, range.second}, dest, col_dest);

    // update_merge(node->col, 
    //              (node->left) ? node->left->col : nullptr,
    //              (node->right) ? node->right->col : nullptr,
    //              __col_range, col_dest);

    int64_t cur = gcd2(node->left ? query_col(node->left->col, __col_range, col_dest) : 0,
                       node->right ? query_col(node->right->col, __col_range, col_dest) : 0);

    update_base(node->col, cur, __col_range, col_dest);
}

int64_t query_col(cnode_t *node, p32 range, p32 dest){
    if(!node){
        return 0;
    }

    int8_t type = ranges(range, dest);

    if(!type){
        return 0;
    }

    if(type == 1){
        return node->val;
    }

    int mid = (range.first + range.second) / 2;
    int64_t left = query_col(node->left, {range.first, mid}, dest);
    int64_t right = query_col(node->right, {mid, range.second}, dest);

    return gcd2(left, right);
}

int64_t query_row(rnode_t *node, p32 range, p32 dest, p32 col_dest){
    if(!node){
        return 0;
    }

    int8_t type = ranges(range, dest);
    if(!type){
        return 0;
    }

    if(type == 1){
        return query_col(node->col, __col_range, col_dest);
    }

    int mid = (range.first + range.second) / 2;
    int64_t left = query_row(node->left, {range.first, mid}, dest, col_dest);
    int64_t right = query_row(node->right, {mid, range.second}, dest, col_dest);

    return gcd2(left, right);
}

void init(int row_count, int col_count) {
    tree = fetch_rnode();
    //row_count = 1 << int(log2(row_count) + 1);
    //col_count = 1 << int(log2(col_count) + 1);
    
    __row_range = {0, row_count};
    __col_range = {0, col_count};
}

void update(int row, int col, long long val) {
    // ciuj taip reik:
    // * perskaiciuot tame specifiniame medyje gcd (tos eilutes)
    // * perskaiciuot visu eiluciu gabalu reiksmes

    update_row(tree, (int64_t)val, __row_range, {row, row + 1}, {col, col + 1});
}

long long calculate(int row0, int col0, int row1, int col1) {
    return query_row(tree, __row_range, {row0, row1 + 1}, {col0, col1 + 1});
}

#ifdef _AAAAAAAAA
void at_end(){
    cout << "rnode: " << rnodes.size() << '\n';
    cout << "cnode: " << cnodes.size() << '\n';
    cout << "del merge: " << merge_count << '\n';
}
#endif

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: 0 / 20