제출 #518552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
518552		blue	Game (IOI13_game)	C++17	100 / 100	2947 ms	82012 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;
}



struct col_tree
{
    int l;
    int r;

    ll g = 0;

    col_tree* left = NULL;
    col_tree* right = NULL;
};

col_tree* insert(col_tree* P, int I, ll V, int nl, int nr)
{
    // cerr << "ins called\n";
    col_tree* node1 = P;
    col_tree* node2 = new col_tree{I, I, V, NULL, NULL};

    if(node1->l >= node2->l) swap(node1, node2);

    // int nl = P->l, nr = P->r;
    while(1)
    {
        // cerr << node1->l << ' ' << node1->r << ' ' << node2->l << ' ' << node2->r << "  " << nl << ' ' << nr << '\n';
        if((nl+nr)>>1 >= node2->r)
            nr = (nl+nr)>>1;
        else if((nl+nr)/2+1 <= node1->l)
            nl = (nl+nr)/2+1;
        else
            break;
    }

    col_tree* par = new col_tree{nl, nr, gcd2(node1->g, node2->g), node1, node2};

    // cerr << "ins exit\n";

    return par;
}

void update(col_tree* T, int I, ll V)
{
    // cerr << "col tree update enter : " << T->l << ' ' << T->r << ' ' << I << ' ' << V << '\n';
    if(T->r < I || I < T->l)
    {
        // cerr << "case 1\n";
        return;
    }
    if(T->l == T->r)
    {
        // cerr << "case 2\n";
        T->g = V;
    }
    else
    {
        // cerr << "case 3\n";
        if(I <= (T->l+T->r)/2)
        {
            if(T->left == NULL) T->left = new col_tree{I, I, V, NULL, NULL};
            else if(T->left->l <= I && I <= T->left->r) update(T->left, I, V);
            else T->left = insert(T->left, I, V, T->l, T->r);
            // update(T->left, I, V);
        }
        else
        {
            if(T->right == NULL) T->right = new col_tree{I, I, V, NULL, NULL};
            if(T->right->l <= I && I <= T->right->r) update(T->right, I, V);
            else T->right = insert(T->right, I, V, T->l, T->r);
        }

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

        T->g = gcd2(lg, rg);
    }
    // cerr << "col tree exit\n";
}

ll range_gcd(col_tree* T, int L, int R)
{
    if(T == NULL) return 0;
    else if(R < T->l || T->r < L) return 0;
    else if(L <= T->l && T->r <= R) return T->g;
    else return gcd2(range_gcd(T->left, L, R), range_gcd(T->right, L, R));
}











struct row_tree
{
    col_tree v{0, INF-1, 0, NULL, NULL};

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

row_tree* new_row_tree()
{
    return new row_tree;
}
                           //ro
void update(row_tree* T, int I, int J, ll V, int l, int r)
{
    // cerr << "entering row_tree " << l << ' ' << r << "\n";
    if(l == r)
    {
        update(&T->v, J, V);
    }
    else
    {
        // cerr << "case 2\n";
        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));
    }

    // cerr << "exiting row_tree " << l << ' ' << r << "\n";
}

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);
    // cerr << "update done\n";
}

ll calculate(int P, int Q, int U, int V)
{
    ll res =  grid_gcd(&ST, P, U, Q, V);
    // cerr << "computed\n";
    return res;
}

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