WA0求调,思路与正解无异
查看原帖
WA0求调,思路与正解无异
515891
paper_楼主2023/11/17 20:28
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
#define int long long
int n, w, h, cnt, cn;
double b[N * 2];
struct P{
	double x, y;
	int c;
}s[N * 2];
bool cmp(P p, P q) {
	if (p.y != q.y) return p.y < q.y;
	return p.c < q.c;
}
struct TREE {
	int l, r, add, ma;
}tr[N * 8];
void pushdown(int k) {
	auto &a = tr[k], &b = tr[k * 2], &c = tr[k * 2 + 1];
	b.add += a.add, b.ma += a.add;
	c.add += a.add, c.ma += a.add;
	a.add = 0;
}
void pushup(int k) {
	tr[k].ma = max(tr[k * 2].ma, tr[k * 2 + 1].ma);
}
void build(int k, int l, int r) {
	tr[k] = {l, r, 0, 0};
	if (l == r) return;
	int mid = l + r >> 1;
	build(k * 2, l, mid);build(k * 2 + 1, mid + 1, r);
}
void add(int k, int l, int r, int v) {
	if (tr[k].l >= l && tr[k].r <= r) {
		tr[k].ma += v;
		tr[k].add += v;
		return ;
	}
	int mid = tr[k].l + tr[k].r >> 1;
	pushdown(k);
	if (l <= mid) add(k * 2, l, r, v);
	if (r > mid) add(k * 2 + 1, l, r, v);
	pushup(k);
}
void work() {
	unordered_map<double, int> mp;
	cnt = cn = 0;
	cin >> n >> w >> h;
	for (int i = 1; i <= n; i ++ ) {
		cn ++;
		cin >> s[cn].x >> s[cn].y >> s[cn].c;
		b[++cnt] = s[cn].x;
		b[++cnt] = s[cn].x + w - 0.5;
		cn ++;
		s[cn].x = s[cn - 1].x, s[cn].y = s[cn - 1].y + h - 0.5, s[cn].c = -s[cn - 1].c;
	}
	sort(b + 1, b + 1 + cnt);
	b[0] = -1;
	int C = 0;
	for (int i = 1; i <= cnt; i ++ )
		if (b[i] != b[i - 1]) mp[b[i]] = ++C;
	sort(s + 1, s + n + 1, cmp);
	build(1, 1, C - 1);
	int ans = 0;
	for (int i = 1; i <= cn; i ++ ) {
		add(1, mp[s[i].x], mp[s[i].x + w - 0.5] - 1, s[i].c);
		ans = max(ans, tr[1].ma);
	}
	cout << ans << '\n';
}
signed main() {
	int T;
	cin >> T;
	while (T -- ) work();
	return 0;
}
2023/11/17 20:28
加载中...