Submission #581132

#	Time	Username	Problem	Language	Result	Execution time	Memory
581132		ggoh	Game (IOI13_game)	C++14	0 / 100	1 ms	468 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, onlyvalindex;
    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 onevalyup(int num, int yco)
{
    int s1 = yTree[num].s, e1 = yTree[num].e;
	if(s1==e1)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, yco, yTree[num].val});}
    }
    else
    {
        if(yTree[num].right==-1){yTree[num].right = yTree.size();
        yTree.push_back({(s1 + e1) / 2 + 1, e1, -1, -1, yco, yTree[num].val});}
    }
}
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;
        yTree[num].onlyvalindex = yco;
        return;
    }*/
    if (yTree[num].onlyvalindex == -1)
    {
        yTree[num].val = v;
        yTree[num].onlyvalindex = yco;
        return;
    }
    else if (yTree[num].onlyvalindex >= 0)
    {
        if (yTree[num].onlyvalindex == yco)
        {
            yTree[num].val = v;
            return;
        }
        else
        {
            onevalyup(num, yTree[num].onlyvalindex);
            yTree[num].onlyvalindex = -2;
        }
    }
    if ((s1 + e1) / 2 >= yco)
    {
        if (yTree[num].left == -1)
        {
            yTree[num].left = yTree.size();
            yTree.push_back({s1, (s1 + e1) / 2, -1, -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, -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;
    int cnt = 0, valind;
    if (lnum >= 0)
    {
        l = yTree[lnum].val;
        if (yTree[lnum].onlyvalindex >= 0)
        {
            cnt++;
            valind = yTree[lnum].onlyvalindex;
            onevalyup(lnum, yTree[lnum].onlyvalindex);
        }
        else if (yTree[lnum].onlyvalindex == -2)
            cnt += 2;
    }
    if (rnum >= 0)
    {
        r = yTree[rnum].val;
        if (yTree[rnum].onlyvalindex >= 0)
        {
            cnt++;
            valind = yTree[rnum].onlyvalindex;
            onevalyup(rnum, yTree[rnum].onlyvalindex);
        }
        else if (yTree[rnum].onlyvalindex == -2)
            cnt += 2;
    }
    if (cnt == 1)
        yTree[num].onlyvalindex = valind;
    else if (cnt > 1)
        yTree[num].onlyvalindex = -2;
    else
        yTree[num].onlyvalindex = -1;
    yTree[num].val = gcd2(l, r);
    if (s1 == e1 || yTree[num].onlyvalindex >= 0)
        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, -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, -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, -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, -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 (yTree[num].onlyvalindex >= 0)
    {
        if (py <= yTree[num].onlyvalindex && yTree[num].onlyvalindex <= qy)
        {
 
            return yTree[num].val;
        }
        else
            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,-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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20