蒟蒻只AC第一个点,后面9个全WA求助
查看原帖
蒟蒻只AC第一个点,后面9个全WA求助
416483
Niouville楼主2021/3/14 15:00
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node1
{
	long long  x, y, l;
	long long  left, right;
}star[10005];
long long height_sorted[10005] = { 0 }, height_set[10005] = { 0 }, ans = 0;
struct node2
{
	int left;
	int right;
	long long val = 0;
	long long lazy_tag = 0;
}tree[4 * 10005];
bool cmp_x(node1 a, node1 b)
{
	return a.x < b.x;
}
void build(int num, int start, int end)
{
	tree[num].left = start, tree[num].right = end;
	if (start == end)
	{
		tree[num].val = 0;
		return;
	}
	int mid = (tree[num].left + tree[num].right) / 2;
	build(num * 2, start, mid);
	build(num * 2 + 1, mid + 1, end);
}
void spread(int num)
{
	if (tree[num].lazy_tag)
	{
		tree[num * 2].val += tree[num].lazy_tag;
		tree[num * 2 + 1].val += tree[num].lazy_tag;
		tree[num * 2].lazy_tag += tree[num].lazy_tag;
		tree[num * 2 + 1].lazy_tag += tree[num].lazy_tag;
		tree[num].lazy_tag = 0;
	}
}
void change(int num, int start, int end, long long int value)
{
	if (start <= tree[num].left && end >= tree[num].right)
	{
		tree[num].val += value;
		tree[num].lazy_tag += value;
		return;
	}
	spread(num);
	int mid = (tree[num].left + tree[num].right) / 2;
	if (start <= mid)change(num * 2, start, end, value);
	if (end > mid)change(num * 2 + 1, start, end, value);
	tree[num].val = max(tree[num * 2].val, tree[num * 2 + 1].val);
}
int main(void)
{
	int T;
	scanf("%d", &T);
	for (int k = 1; k <= T; k++)
	{
		//initial:
		int n, w, h;int top = 0;
		scanf("%d%d%d", &n, &w, &h);
		for (int i = 1; i <= n; i++)
		{
			scanf("%lld%lld%lld", &star[i].x, &star[i].y, &star[i].l);
			height_sorted[i] = star[i].y;
		}
		sort(star + 1, star + 1 + n, cmp_x);
		sort(height_sorted + 1, height_sorted + n + 1);
		for (int i = 1; i <= n; i++)
		{
			if (i == 1 || height_sorted[i] ^ height_sorted[i - 1])
				height_set[++top] = height_sorted[i];
		}
		for (int i = 1; i <= n; i++)
		{
			star[i].left = lower_bound(height_set + 1, height_set + 1 + top, star[i].y) - height_set;
			star[i].right = lower_bound(height_set + 1, height_set + 1 + top, star[i].y + h) - height_set - 1;
		}
		build(1, 1, top);
		//work:
		int tail = 1;
		for (int i = 1; i <= n; i++)
		{
			long long int j = star[i].x;
			while (star[i].x == j)
			{
				change(1, star[i].left, star[i].right, star[i].l);
				i++;
			}
			i--;
			while (tail < i && star[tail].x + w <= j)
			{
				change(1, star[tail].left, star[tail].right, -star[tail].l);
				tail++;
			}
			ans = max(ans, tree[1].val);
		}
		printf("%lld\n", ans);
	}
	return 0;
}
2021/3/14 15:00
加载中...