Submission #495430

#	Time	Username	Problem	Language	Result	Execution time	Memory
495430		blue	Game (IOI13_game)	C++17	0 / 100	1 ms	204 KiB

game

#include "game.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

using ll = long long;

const int INF = 1'000'000'000;

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

const int bs = 5;



struct col_tree
{
    ll g = 0;

    // col_tree* left = NULL;
    // col_tree* right = NULL;

    col_tree* children[bs];

    col_tree()
    {
        for(int b = 0; b < bs; b++) children[b] = NULL;
    }
};

// col_tree* col_stash = new col_tree[400'000];
// int col_tree_ct = -1;

col_tree* new_col_tree()
{
    // col_tree_ct++;
    // return &col_stash[col_tree_ct];
    return new col_tree;
}

void update(col_tree* T, int I, ll V, int l, int r)
{
    // cerr << "updating column tree\n";
    // cerr << I << ' ' << V << ' ' << l << ' ' << r << '\n';
    if(l == r)
    {
        T->g = V;
    }
    else if(r-l+1 <= bs)
    {
        if(T->children[I-l] == NULL) T->children[I-l] = new_col_tree();
        update(T->children[I-l], I, V, I, I);

        T->g = 0;
        for(int s = 0; s < bs; s++)
            T->g = gcd2(T->g, (T->children[s] == NULL ? 0 : T->children[s]->g));
    }
    else
    {
        // cerr << "case 3\n";
        int d = (r+1-l)/bs;

        for(int s = 0; s < bs; s++)
        {
            if(s == bs-1)
            {
                if(T->children[s] == NULL) T->children[s] = new_col_tree();
                update(T->children[s], I, V, l + d*s, r);
                break;
            }
            else if(I < l + d*(s+1))
            {
                if(T->children[s] == NULL) T->children[s] = new_col_tree();
                update(T->children[s], I, V, l + d*s, l + d*(s+1)-1);
                break;
            }
        }

        T->g = 0;
        for(int s = 0; s < bs; s++)
            T->g = gcd2(T->g, (T->children[s] == NULL ? 0 : T->children[s]->g));
    }
    /*else
    {

        if(I <= (l+r)/2)
        {
            if(T->left == NULL) T->left = new_col_tree();
            update(T->left, I, V, l, (l+r)/2);
        }
        else
        {
            if(T->right == NULL) T->right = new_col_tree();
            update(T->right, I, V, (l+r)/2+1, r);
        }

        ll lg = (T->left == NULL) ? 0 : T->left->g;
        ll rg = (T->right == NULL) ? 0 : T->right->g;

        T->g = gcd2(lg, rg);
    }*/
}

void update(col_tree* T, int I, ll V)
{
    update(T, I, V, 0, INF-1);
}

ll range_gcd(col_tree* T, int L, int R, int l, int r)
{
    // cerr << "range gcd called\n";
    if(T == NULL) return 0;
    else if(R < l || r < L) return 0;
    else if(L <= l && r <= R) return T->g;
    else
    {
        int d = (r+1-l)/bs;
        ll ans = 0;
        for(int s = 0; s < bs; s++)
        {
            if(s == bs-1)
            {
                ans = gcd2(ans, range_gcd(T->children[s], L, R, l+d*s, r));
            }
            else
            {
                ans = gcd2(ans, range_gcd(T->children[s], L, R, l+d*s, l+d*(s+1)-1));
            }
        }

        return ans;
    } //return gcd2(range_gcd(T->left, L, R, l, (l+r)/2), range_gcd(T->right, L, R, (l+r)/2+1, r));
}

ll range_gcd(col_tree* T, int L, int R)
{
    return range_gcd(T, L, R, 0, INF-1);
}







struct row_tree
{
    col_tree v;

    row_tree* left = NULL;
    row_tree* right = NULL;
};

// row_tree* row_stash = new row_tree[2'300'000]; //IF NECESSARY CUT THIS!!!!
// int row_tree_ct = -1;

row_tree* new_row_tree()
{
    // row_tree_ct++;
    // return &row_stash[row_tree_ct];
    return new row_tree;
}
                           //ro
void update(row_tree* T, int I, int J, ll V, int l, int r)
{
    if(l == r)
    {
        update(&T->v, J, V);
    }
    else
    {
        if(I <= (l+r)/2)
        {
            if(T->left == NULL) T->left = new_row_tree();
            update(T->left, I, J, V, l, (l+r)/2);
        }
        else
        {
            if(T->right == NULL) T->right = new_row_tree();
            update(T->right, I, J, V, (l+r)/2+1, r);
        }

        ll lg = (T->left == NULL) ? 0 : range_gcd(&T->left->v, J, J);
        ll rg = (T->right == NULL) ? 0 : range_gcd(&T->right->v, J, J);

        update(&T->v, J, gcd2(lg, rg));
    }
}

void update(row_tree* T, int I, int J, ll V)
{
    update(T, I, J, V, 0, INF-1);
}


ll grid_gcd(row_tree* T, int R1, int R2, int C1, int C2, int l, int r)
{
    if(T == NULL) return 0;
    else if(R2 < l || r < R1) return 0;
    else if(R1 <= l && r <= R2) return range_gcd(&T->v, C1, C2);
    else return gcd2(grid_gcd(T->left, R1, R2, C1, C2, l, (l+r)/2), grid_gcd(T->right, R1, R2, C1, C2, (l+r)/2+1, r));
}

ll grid_gcd(row_tree* T, int R1, int R2, int C1, int C2)
{
    return grid_gcd(T, R1, R2, C1, C2, 0, INF-1);
}



row_tree ST;

void init(int R, int C)
{
    ;
}

void update(int P, int Q, long long K)
{
    update(&ST, P, Q, K);
}

ll calculate(int P, int Q, int U, int V)
{
    return grid_gcd(&ST, P, U, Q, V);
}

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