Submission #703769

#	Time	Username	Problem	Language	Result	Execution time	Memory
703769		TheSahib	Game (IOI13_game)	C++17	100 / 100	4727 ms	157488 KiB

game

#include <bits/stdc++.h>
#include "game.h"

#define ll long long
#define pii pair<int, int>

using namespace std;

const int MAX = (1 << 30) - 1;
const int BRANCH_LOG = 3;
const int BRANCH = (1 << BRANCH_LOG);
const int TREE_SIZE = 22000 * (30 / BRANCH_LOG);


struct SegTree1D{
    int nxt = 0;
    vector<ll> tree; 
    vector<int> L, R;
    
    SegTree1D(){
        tree.emplace_back(0);
        L.emplace_back(0);
        R.emplace_back(0);
    }

    int addNode(){
        tree.emplace_back(0);
        L.emplace_back(0);
        R.emplace_back(0);
        return ++nxt;
    }

    void update(int node, int l, int r, int pos, ll val){
        if(l == r){
            tree[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid){
            if(!L[node]) L[node] = addNode();
            update(L[node], l, mid, pos, val);
        }
        else{
            if(!R[node]) R[node] = addNode();
            update(R[node], mid + 1, r, pos, val);
        }
        tree[node] = 0;
        if(L[node]) tree[node] = gcd(tree[node], tree[L[node]]);
        if(R[node]) tree[node] = gcd(tree[node], tree[R[node]]);
    }
    ll ask(int node, int l, int r, int ql, int qr){
        if(qr < l || r < ql){
            return 0;
        }
        if(ql <= l && r <= qr){
            return tree[node];
        }
        int mid = (l + r) / 2;
        ll ans = 0;
        if(L[node]) ans = gcd(ans, ask(L[node], l, mid, ql, qr));
        if(R[node]) ans = gcd(ans, ask(R[node], mid + 1, r, ql, qr));
        return ans;
    }
};

struct SegTree2D{
    int nxt = 0;
    SegTree1D tree[TREE_SIZE];
    int child[TREE_SIZE][BRANCH];
    
    SegTree2D(){
        memset(child, 0, sizeof(child));
    }

    void update(int node, int l, int r, int posY, int posX, ll val){
        if(l == r){
            tree[node].update(0, 0, MAX, posX, val);
            return;
        }
        ll ans = 0;
        int inc = (r - l + 1) >> BRANCH_LOG;

        int uChild = (posY - l) / inc;
        if(!child[node][uChild]) child[node][uChild] = ++nxt;
        update(child[node][uChild], l + uChild * inc, l + (uChild + 1) * inc- 1, posY, posX, val);

        for (int i = 0; i < BRANCH; i++)
        {
            if(child[node][i]) ans = gcd(ans, tree[child[node][i]].ask(0, 0, MAX, posX, posX));
        }
        
        tree[node].update(0, 0, MAX, posX, ans);
    }
    ll ask(int node, int l, int r, int qlY, int qrY, int qlX, int qrX){
        if(qrY < l || r < qlY){
            return 0;
        }
        if(qlY <= l && r <= qrY){
            return tree[node].ask(0, 0, MAX, qlX, qrX);
        }
        ll ans = 0;
        int inc = (r - l + 1) >> BRANCH_LOG;
        int a = l;
        for (int i = 0; i < BRANCH; i++)
        {
            if(child[node][i] && a + inc - 1 >= qlY && a <= qrY){
                ans = gcd(ans, ask(child[node][i], a, a + inc - 1, qlY, qrY, qlX, qrX));
            }
            a += inc;
        }
        return ans;
    }
};

SegTree2D tree;

void init(int R, int C){
    
}

void update(int P, int Q, ll K){
    tree.update(0, 0, MAX, P, Q, K);
}

ll calculate(int P, int Q, int U, int V){
    return tree.ask(0, 0, MAX, P, U, Q, V);
}

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