Submission #432412

#	Time	Username	Problem	Language	Result	Execution time	Memory
432412		p_square	Game (IOI13_game)	C++14	37 / 100	13095 ms	14636 KiB

game

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

using namespace std;

#define ll long long

ll r, c;
vector <ll> lqry;

struct node
{
    ll val, North, South, West, East;
    node *NE, *NW, *SE, *SW;
    node(ll a, ll b, ll c, ll d)
    {
        North = a, South = b, West = c, East = d;
        val = 0;
    }
    node() {}
};

node *last = new node(-1, -1, -1, -1);

void lastify(node *th)
{
    th->NE = last;
    th->NW = last;
    th->SE = last;
    th->SW = last;
}

node *rt = new node();

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

ll mgcd(ll a, ll b, ll c, ll d)
{
    a = gcd2(a, b);
    a = gcd2(a, c);
    a = gcd2(a, d);
    return a;
}

void update_seg(node* cur, ll row, ll col, ll val)
{
    //cout<<cur->North<<" "<<cur->South<<" "<<cur->West<<" "<<cur->East<<endl;
    if(cur -> North > row || cur -> South < row)
        return;

    if(cur -> West > col || cur -> East < col)
        return;

    if(cur -> North == cur -> South && cur -> East == cur -> West)
    {
        cur->val = val;
        return;
    }

    ll mrow = (cur -> North + cur -> South)/2;
    ll mcol = (cur -> East + cur -> West)/2;

    if(row <= mrow && col <= mcol)
    {
        if(cur -> NW == last)
        {
            cur -> NW = new node(cur->North, mrow, cur -> West, mcol);
            lastify(cur->NW);
        }
        update_seg(cur->NW, row, col, val);
    }

    if(row <= mrow && col > mcol)
    {
        if(cur -> NE == last)
        {
            cur -> NE = new node(cur->North, mrow, mcol+1, cur->East);
            lastify(cur->NE);
        }
        update_seg(cur->NE, row, col, val);
    }

    if(row > mrow && col <= mcol)
    {
        if(cur -> SW == last)
        {
            cur -> SW = new node(mrow+1, cur->South, cur -> West, mcol);
            lastify(cur->SW);
        }
        update_seg(cur->SW, row, col, val);
    }

    if(row > mrow && col > mcol)
    {
        if(cur -> SE == last)
        {
            cur -> SE = new node(mrow+1, cur->South, mcol+1, cur->East);
            lastify(cur->SE);
        }
        update_seg(cur->SE, row, col, val);
    }

    cur->val = mgcd((cur->NE)->val, (cur->NW)->val, (cur->SE)->val, (cur->SW)->val);
    //cout<<cur->North<<" "<<cur->South<<" "<<cur->West<<" "<<cur->East<<" "<<cur->val<<endl;
}

void query_seg(node *cur, ll top, ll bottom, ll left, ll right)
{
    if(cur->North > bottom || cur -> South < top)
        return;

    if(cur -> East < left || cur -> West > right)
        return;

    if(cur->East <= right && cur->West >= left && cur->North >= top && cur->South <= bottom)
    {
        lqry.push_back(cur->val);
        return;
    }

    query_seg(cur->NE, top, bottom, left, right);
    query_seg(cur->NW, top, bottom, left, right);
    query_seg(cur->SE, top, bottom, left, right);
    query_seg(cur->SW, top, bottom, left, right);
}

void init(int R, int C) {
    /* ... */
    r = R;
    c = C;
    rt -> North = 0;
    rt -> South = r-1;
    rt -> West = 0;
    rt -> East = c-1;
    lastify(rt);
}

void update(int P, int Q, long long K) {
    update_seg(rt, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    lqry.clear();
    lqry.push_back(0);
    query_seg(rt, P, U, Q, V);
    sort(lqry.begin(), lqry.end());

    ll ind = 0;
    for(int i = 0; i<int(lqry.size()); i++)
    {
        if(lqry[i] != 0)
        {
            ind = i;
            for(int j = i; j<int(lqry.size()); j++)
            {
                lqry[i] = gcd2(lqry[i], lqry[j]);
            }
            break;
        }
    }
    return lqry[ind];
}

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