Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
4.2 kB
11
Indexable
//user
#define MAX_N 100005
int arr[MAX_N];
struct Node
{
    int val;
    int idx;
};
Node node[4 * MAX_N];
int n;
 
int max(int a, int b)
{
    return (a >= b) ? a : b;
}
 
void init(int N)
{
    n = N;
    for (int i = 1; i <=N; i++)
    {
        arr[i] = 0;
    }
    for (int i = 0; i < 4 *N+1; i++)
    {
        node[i].idx = 0;
        node[i].val = 0;
    }
    return;
}
 
void update(int idx, int low, int high, int pos)
{
    if (pos < low || pos>high)
    {
        return;
    }
    if (low >= pos && high <= pos)
    {
        node[idx].val = arr[pos];
        node[idx].idx = pos;
        return;
    }
    int mid = (low + high) / 2;
    update(2 * idx + 1, low, mid, pos);
    update(2 * idx + 2, mid + 1, high, pos);
 
    if (node[2 * idx + 1].val > node[2 * idx + 2].val)
    {
        node[idx].val = node[2 * idx + 1].val;
        node[idx].idx = node[2 * idx + 1].idx;
    }
    else
    {
        node[idx].val = node[2 * idx + 2].val;
        node[idx].idx = node[2 * idx + 2].idx;
    }
}
 
Node queryArea(int idx, int low, int high, int l, int r)
{
    if (low > high)
    {
        return { -1,-1 };
    }
    if (low > r || high < l)
    {
        return { -1,-1 };
    }
 
    if (low >= l && high <= r)
    {
        return node[idx];
    }
 
    int mid = (low + high) / 2;
    Node left = queryArea(2 * idx + 1, low, mid, l, r);
    Node right = queryArea(2 * idx + 2, mid + 1, high, l, r);
 
    if (left.val > right.val)
    {
        return left;
    }
    return right;
 
}

int area()
{
    Node maxAns = node[0];
    int maxArea = maxAns.val;
    int maxIdx = maxAns.idx;
 
    int tmp = maxIdx;
 
    while (tmp < n)
    {
        Node ansRight = queryArea(0, 1, n, tmp + 1, n);
        if (ansRight.val == 0)
        {
            break;
        }
        maxArea += (ansRight.idx - tmp) * ansRight.val;
        tmp = ansRight.idx;
    }
    tmp = maxIdx;
 
    while (tmp > 1)
    {
        Node ansLeft = queryArea(0, 1, n, 1, tmp-1);
        if (ansLeft.val == 0)
        {
            break;
        }
        maxArea += (tmp-ansLeft.idx) * ansLeft.val;
        tmp = ansLeft.idx;
    }
    return maxArea;
}
 
int stock(int mLoc, int mBox)
{
    arr[mLoc] += mBox;
    update(0, 1, n, mLoc);
    return area();
}
 
int ship(int mLoc, int mBox)
{
    arr[mLoc] -= mBox;
    update(0, 1, n, mLoc);
    return area();
}
 
int getHeight(int mLoc)
{
    return arr[mLoc];
}
//main
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

#define CMD_INIT			(100)
#define CMD_STOCK			(200)
#define CMD_SHIP			(300)
#define CMD_GET_HEIGHT		(400)

extern void init(int N);
extern int stock(int mLoc, int mBox);
extern int ship(int mLoc, int mBox);
extern int getHeight(int mLoc);

static bool run()
{
	int Q;
	int N, mLoc, mBox;
	
	int ret = -1, ans;

	scanf("%d", &Q);

	bool okay = false;

	for (int q = 0; q < Q; ++q)
	{
		int cmd;
		scanf("%d", &cmd);
		switch(cmd)
		{
		case CMD_INIT:
			scanf("%d", &N);
			init(N);
			okay = true;
			break;
		case CMD_STOCK:
			scanf("%d %d", &mLoc, &mBox);
			ret = stock(mLoc, mBox);
			scanf("%d", &ans);
			if (ret != ans)
				okay = false;
			break;
		case CMD_SHIP:
			scanf("%d %d", &mLoc, &mBox);
			ret = ship(mLoc, mBox);
			scanf("%d", &ans);
			if (ret != ans)
				okay = false;
			break;
		case CMD_GET_HEIGHT:
			scanf("%d", &mLoc);
			ret = getHeight(mLoc);
			scanf("%d", &ans);
			if (ret != ans)
				okay = false;
			break;
		default:
			okay = false;
			break;
		}
	}

	return okay;
}

int main()
{
	setbuf(stdout, NULL);
	freopen("sample_input.txt", "r", stdin);

	int TC, MARK;

	scanf("%d %d", &TC, &MARK);
	for (int tc = 1; tc <= TC; ++tc)
	{
		int score = run() ? MARK : 0;
		printf("#%d %d\n", tc, score);
	}

	return 0;
}
//input
25 100
15
100 8
200 3 4 4
300 3 4 0
400 3 0
200 5 2 2
200 7 3 7
200 1 1 11
200 3 3 17
200 8 1 18
200 4 5 20
200 7 3 27
400 7 6
300 4 3 21
300 7 3 18
400 4 2
23
100 6
200 1 1 1
200 6 1 6
300 6 1 1
200 1 1 2
200 2 1 3
200 1 1 4
300 1 3 1
200 6 1 5
400 5 0
200 5 1 5
300 6 1 4
200 2 1 5
300 5 1 2
400 4 0
200 2 1 3
200 2 1 4
200 1 1 5
400 2 4
300 1 1 4
300 2 2 2
400 5 0
200 2 1 3