WA on #9 求调
查看原帖
WA on #9 求调
467357
firstlight楼主2024/8/3 14:29
// Problem: P1502 窗口的星星
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1502
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20010;
typedef long long ll;
#define int ll

int n, w, h;
vector<ll> ys; // 离散化用

struct Segment{
	ll x, y1, y2;
	ll val;
	
	bool operator< (const Segment &u)const 
	{
		if(x == u.x) return val < u.val;
		return x < u.x;
	}
} seg[N]; // 矩形的边

struct Node{
	int l, r;
	ll maxval;
	ll add;
} tr[N * 4]; // 线段树

void build(int u, int l, int r) // 建树
{
	tr[u] = {l, r, 0, 0};
	if(l == r) return;
	
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
}

void pushup(int u) {tr[u].maxval = max(tr[u << 1].maxval, tr[u << 1 | 1].maxval);} // 子节点计算父节点

void pushdown(int u) // 下传标记
{
	auto &root = tr[u], &le = tr[u << 1], &ri = tr[u << 1 | 1];
	
	if(root.add)
	{
		le.add += root.add;
		le.maxval += root.add;
		ri.add += root.add;
		ri.maxval += root.add;
		root.add = 0;
	}
}

void update(int u, int l, int r, int k) // 区间修改
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].maxval += k;
		tr[u].add += k;
		return;
	}
	
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) update(u << 1, l, r, k);
	if(r > mid) update(u << 1 | 1, l, r, k);
	pushup(u);
}

int find(ll x) {return lower_bound(ys.begin(), ys.end(), x) - ys.begin();}

signed main()
{
	int T;
	scanf("%lld", &T);
	
	while(T -- )
	{
		memset(seg, 0, sizeof seg);
		memset(tr, 0, sizeof tr);
		ys.clear();
		scanf("%lld%lld%lld", &n, &w, &h);
		for(int i = 1, j = 0; i <= n; i ++ )
		{
			ll x, y, l;
			scanf("%lld%lld%lld", &x, &y, &l);
			ys.push_back(y), ys.push_back(y + h - 1);
			seg[j ++ ] = {x, y, y + h - 1, l};
			seg[j ++ ] = {x + w - 1, y, y + h - 1, -l};
		}
		
		sort(ys.begin(), ys.end());
		ys.erase(unique(ys.begin(), ys.end()), ys.end()); // 离散化
		
		build(1, 0, ys.size());
		
		sort(seg, seg + n * 2);
		
		ll res = 0;
		for(int i = 0; i < n * 2; i ++ )
		{
			update(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].val);
			res = max(res, tr[1].maxval);
		}
		
		printf("%lld\n", res);
	}
	
	return 0;
}
2024/8/3 14:29
加载中...