Submission #581715

#	Time	Username	Problem	Language	Result	Execution time	Memory
581715		ggoh	Game (IOI13_game)	C++14	10 / 100	1278 ms	17960 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int R, C, N, ch, P, Q, U, V;
int px, qx, py, qy;
int xco, yco;
long long v;
long long K;
struct Y
{
    Y *left, *right;
    int only;
    long long val;
    Y(int d, long long va) : left(NULL), right(NULL), only(d), val(va) {}
};
struct X
{
    X *left, *right;
    Y *ynode;
    X() : left(NULL), right(NULL), ynode(NULL) {}
} * inix;

long long gcd2(long long xx, long long yy)
{
    if (yy == 0)
        return xx;
    return gcd2(yy, xx % yy);
}

void yup(Y *y, int s, int e)
{
    int m = (s + e) >> 1;
    if (y->only >= 0)
    {
        if (y->only == yco)
        {
            y->val = v;
            if (!y->left && !y->right)
                return;
        }
        else
        {
            if (y->only <= m && !y->left)
            {
                y->left = new Y(y->only, y->val);
            }
            else if (y->only > m && !y->right)
            {
                y->right = new Y(y->only, y->val);
            }
            y->only = -1;
        }
    }
    if (m >= yco)
    {
        if (!y->left)
        {
            y->left = new Y(yco, v);
        }
        yup(y->left, s, m);
    }
    else
    {
        if (!y->right)
        {
            y->right = new Y(yco, v);
        }
        yup(y->right, m + 1, e);
    }
    long long l = 0, r = 0;
    if (y->left)
        l = y->left->val;
    if (y->right)
        r = y->right->val;
    y->val = gcd2(l, r);
}
void hardyup(Y *y, int s, int e, Y *ly, Y *ry)
{
    int m = (s + e) >> 1;
    long long l = 0, r = 0;
    int cnt = 0, valind = -1;
    if (ly)
    {
        l = ly->val;
        if (ly->only >= 0)
        {
            cnt++;
            valind = ly->only;
            if (ly->only <= m && !ly->left)
            {
                ly->left = new Y(ly->only, ly->val);
            }
            else if (ly->only > m && !ly->right)
            {
                ly->right = new Y(ly->only, ly->val);
            }
        }
        else
            cnt += 2;
    }
    if (ry)
    {
        r = ry->val;
        if (ry->only >= 0)
        {
            cnt++;
            valind = ry->only;
            if (ry->only <= m && !ry->left)
            {
                ry->left = new Y(ry->only, ry->val);
            }
            else if (ry->only > m && !ry->right)
            {
                ry->right = new Y(ry->only, ry->val);
            }
        }
        else
            cnt += 2;
    }
    if (cnt == 1)
    {
        y->only = valind;
        y->val = gcd2(l, r);
        return;
    }
    else
    {
        if (y->only >= 0)
        {
            if (y->only <= m && !y->left)
            {
                y->left = new Y(y->only, y->val);
            }
            else if (y->only > m && !y->right)
            {
                y->right = new Y(y->only, y->val);
            }
        }
        y->only = -1;
        y->val = gcd2(l, r);
    }

    if (s == e)
        return;
    if (yco <= m)
    {
        if (!y->left)
        {
            y->left = new Y(yco, v);
        }
        hardyup(y->left, s, m, ly ? ly->left : NULL, ry ? ry->left : NULL);
    }
    else
    {
        if (!y->right)
        {
            y->right = new Y(yco, v);
        }
        hardyup(y->right, m + 1, e, ly ? ly->right : NULL, ry ? ry->right : NULL);
    }
}
void xup(X *x, int s, int e)
{
    int m = (s + e) >> 1;
    if (!x->ynode)
        x->ynode = new Y(yco, v);
    if (s == e)
    {
        yup(x->ynode, 0, C - 1);
        return;
    }
    if (m >= xco)
    {
        if (!x->left)
        {
            x->left = new X();
        }
        xup(x->left, s, m);
    }
    else
    {
        if (!x->right)
        {
            x->right = new X();
        }
        xup(x->right, m + 1, e);
    }
    hardyup(x->ynode, 0, C - 1, x->left ? x->left->ynode : NULL, x->right ? x->right->ynode : NULL);
}
long long yans(Y *y, int s, int e)
{
    int m = (s + e) >> 1;
    if ((!y) || s > qy || e < py)
        return 0ll;

    if (py <= s && e <= qy)
    {
        return y->val;
    }
    if (y->only >= 0)
    {
        if (py <= y->only && y->only <= qy)
        {
            return y->val;
        }
        else
            return 0ll;
    }
    long long l = 0, r = 0;
    if (y->left)
    {
        l = yans(y->left, s, m);
    }
    if (y->right)
    {
        r = yans(y->right, m + 1, e);
    }
    return gcd2(l, r);
}
long long xans(X *x, int s, int e)
{
    int m = (s + e) >> 1;
    if ((!x->ynode) || s > qx || e < px)
        return 0ll;
    if (px <= s && e <= qx)
    {
        return yans(x->ynode, 0, C - 1);
    }
    long long l = 0, r = 0;
    if (x->left)
        l = xans(x->left, s, m);
    if (x->right)
        r = xans(x->right, m + 1, e);
    return gcd2(l, r);
}
void init(int RR, int CC)
{
    R = RR;
    C = CC;
    inix = new X();
}
void update(int P, int Q, long long K)
{
    xco = P;
    yco = Q;
    v = K;
    xup(inix, 0, R - 1);
}
long long calculate(int P, int Q, int U, int V)
{
    px = P;
    qx = U;
    py = Q;
    qy = V;
    return xans(inix, 0, R - 1);
}

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