Submission #581045

#	Time	Username	Problem	Language	Result	Execution time	Memory
581045		ggoh	Game (IOI13_game)	C++14	63 / 100	1954 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int R, C, N, ch, P, Q, U, V;
long long K;
struct A
{
    int s, e, left, right, ynum;
};
struct B
{
    int s, e, left, right;
    long long val;
};
vector<A> xTree;
vector<B> yTree;
long long gcd2(long long xx, long long yy)
{
    if (yy == 0)
        return xx;
    return gcd2(yy, xx % yy);
}
 
void yup(int num, int yco, long long v)
{
    int s1 = yTree[num].s, e1 = yTree[num].e;
    if (s1 == e1)
    {
        yTree[num].val = v;
        return;
    }
    if ((s1 + e1) / 2 >= yco)
    {
        if (yTree[num].left == -1)
        {
            yTree[num].left = yTree.size();
            yTree.push_back({s1, (s1 + e1) / 2, -1, -1, 0});
        }
        yup(yTree[num].left, yco, v);
    }
    else
    {
        if (yTree[num].right == -1)
        {
            yTree[num].right = yTree.size();
            yTree.push_back({(s1 + e1) / 2 + 1, e1, -1, -1, 0});
        }
        yup(yTree[num].right, yco, v);
    }
    long long l = 0, r = 0;
    if (yTree[num].left >= 0)
        l = yTree[yTree[num].left].val;
    if (yTree[num].right >= 0)
        r = yTree[yTree[num].right].val;
    yTree[num].val = gcd2(l, r);
}
void hardyup(int num, int lnum, int rnum, int yco)
{
    int s1 = yTree[num].s, e1 = yTree[num].e;
    int nextl, nextr;
    long long l = 0, r = 0;
    if (lnum >= 0)
    {
        l = yTree[lnum].val;
    }
    if (rnum >= 0)
    {
        r = yTree[rnum].val;
    }
    yTree[num].val = gcd2(l, r);
    if (s1 == e1)
        return;
    if (yco <= (s1 + e1) / 2)
    {
        if (lnum == -1)
            nextl = -1;
        else
            nextl = yTree[lnum].left;
        if (rnum == -1)
            nextr = -1;
        else
            nextr = yTree[rnum].left;
        if (yTree[num].left == -1)
        {
            yTree[num].left = yTree.size();
            yTree.push_back({s1, (s1 + e1) / 2, -1, -1, 0});
        }
        hardyup(yTree[num].left, nextl, nextr, yco);
    }
    else
    {
        if (lnum == -1)
            nextl = -1;
        else
            nextl = yTree[lnum].right;
        if (rnum == -1)
            nextr = -1;
        else
            nextr = yTree[rnum].right;
        if (yTree[num].right == -1)
        {
            yTree[num].right = yTree.size();
            yTree.push_back({(s1 + e1) / 2 + 1, e1, -1, -1, 0});
        }
        hardyup(yTree[num].right, nextl, nextr, yco);
    }
}
void xup(int num, int xco, int yco, long long v)
{
    int s1 = xTree[num].s, e1 = xTree[num].e;
    if (s1 == e1)
    {
        yup(xTree[num].ynum, yco, v);
        return;
    }
    if ((s1 + e1) / 2 >= xco)
    {
        if (xTree[num].left == -1)
        {
            xTree[num].left = xTree.size();
            xTree.push_back({s1, (s1 + e1) / 2, -1, -1, int(yTree.size())});
            yTree.push_back({0, C - 1, -1, -1, 0});
        }
        xup(xTree[num].left, xco, yco, v);
    }
    else
    {
        if (xTree[num].right == -1)
        {
            xTree[num].right = xTree.size();
            xTree.push_back({(s1 + e1) / 2 + 1, e1, -1, -1, int(yTree.size())});
            yTree.push_back({0, C - 1, -1, -1, 0});
        }
        xup(xTree[num].right, xco, yco, v);
    }
    int lynum = -1, rynum = -1;
    if (xTree[num].left >= 0)
        lynum = xTree[xTree[num].left].ynum;
    if (xTree[num].right >= 0)
        rynum = xTree[xTree[num].right].ynum;
    hardyup(xTree[num].ynum, lynum, rynum, yco);
}
long long yans(int num, int py, int qy)
{
    if (yTree[num].s > qy || yTree[num].e < py)
        return 0ll;
    if (py <= yTree[num].s && yTree[num].e <= qy)
        return yTree[num].val;
    long long l = 0, r = 0;
    if (yTree[num].left >= 0)
        l = yans(yTree[num].left, py, qy);
    if (yTree[num].right >= 0)
        r = yans(yTree[num].right, py, qy);
    return gcd2(l, r);
}
long long xans(int num, int px, int qx, int py, int qy)
{
    if (xTree[num].s > qx || xTree[num].e < px)
        return 0ll;
    if (px <= xTree[num].s && xTree[num].e <= qx)
    {
        return yans(xTree[num].ynum, py, qy);
    }
    long long l = 0, r = 0;
    if (xTree[num].left >= 0)
        l = xans(xTree[num].left, px, qx, py, qy);
    if (xTree[num].right >= 0)
        r = xans(xTree[num].right, px, qx, py, qy);
    return gcd2(l, r);
}
void init(int RR, int CC)
{
  R=RR;
  C=CC;
    xTree.push_back({0, R - 1, -1, -1, 0});
    yTree.push_back({0, C - 1, -1, -1, 0});
}
void update(int P,int Q,long long K)
{
  xup(0, P, Q, K);
}
long long calculate(int P,int Q,int U,int V)
{
  return xans(0, P, U, Q, V);
}

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