Submission #565381

#	Time	Username	Problem	Language	Result	Execution time	Memory
565381		pls33	Game (IOI13_game)	C++17	63 / 100	2520 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;
}

int 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;
}

// 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 = new cnode_t;
        }
        if(!right && ranges({mid, range.second}, dest)){
            right = new cnode_t;
        }
    }
};

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

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

    rnode_t(){
        col = new cnode_t();
    }

    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 = new rnode_t;
        }
        if(!right && ranges({mid, range.second}, dest)){
            right = new rnode_t;
        }
    }
};

rnode_t* tree;
p32 __row_range;
p32 __col_range;

void update_base(cnode_t *node, int64_t val, p32 range, p32 dest){
    if(!node){
        return;
    }
    int 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 = gcd2((node->left)  ? node->left->val  : 0,
                     (node->right) ? node->right->val : 0);
}

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

    if(!type){
        return;
    }

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

        return;
    }

    node->expand(range, dest);
    left->expand(range, dest);
    right->expand(range, dest);

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

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

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

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

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

        return;
    }

    node->expand(range, range);

    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->col, node->right->col, __col_range, col_dest);
}

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

    int type = ranges(range, dest);

    if(!type){
        return 0;
    }

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

    node->expand(range, dest);

    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;
    }

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

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

    node->expand(range, 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 = new rnode_t;
    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});
}

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: 0 / 17
• Subtask 5: 0 / 20