90分 WA#8 求调
查看原帖
90分 WA#8 求调
815504
chenwenmo楼主2024/7/17 11:47
#include<bits/stdc++.h>
#define y1 other
using namespace std;
typedef long long ll;
const int N = 10010;
int T;
int n, W, H;
ll val[N << 1], m;

struct line{
	ll x, y1, y2, k;
}l[N << 1];

bool cmp(line a, line b) {return a.x < b.x;}

struct tree{
	int l, r;
	ll maxn, add;
}t[N << 3];

void build(int x, int l, int r){
	t[x].l = l;
	t[x].r = r;
	t[x].maxn = t[x].add = 0;
	if(l == r) return;
	int mid = l + r >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
}

void push_up(int x){
	t[x].maxn = max(t[x << 1].maxn, t[x << 1 | 1].maxn);
}

void push_down(int x){
	if(t[x].add){
		int l = x << 1, r = x << 1 | 1;
		t[l].add += t[x].add;
		t[r].add += t[x].add;
		t[l].maxn += t[x].add;
		t[r].maxn += t[x].add;
		t[x].add = 0;
	}
}

void update(int x, int l, int r, int k){
	if(t[x].l >= l && t[x].r <= r){
		t[x].add += k;
		t[x].maxn += k;
		return;
	}
	push_down(x);
	int mid = t[x].l + t[x].r >> 1;
	if(l <= mid) update(x << 1, l, r, k);
	if(r > mid) update(x << 1 | 1, l, r, k);
	push_up(x);
}

int find(int x){
	return lower_bound(val + 1, val + 1 + m, x) - val;
}

int main(){
	scanf("%d", &T);
	while(T--){
		m = 0;
		memset(val, 0, sizeof(val));
		int x, y, k;
		scanf("%d%d%d", &n, &W, &H);
		for(int i = 1, j = 0; i <= n; i++){
			scanf("%d%d%d", &x, &y, &k);
			l[++j] = (line){x + 1, y + 1, y + 1 + H, k};
			l[++j] = (line){x + 1 + W, y + 1, y + 1 + H, -k};
			val[++m] = y + 1;
			val[++m] = y + 1 + H;
		}
		sort(val + 1, val + 1 + m);
		sort(l + 1, l + 1 + 2 * n, cmp);
		build(1, 1, m - 1);
		ll ans = -1;
		for(int i = 1; i < 2 * n; i++){
			update(1, find(l[i].y1), find(l[i].y2) - 1, l[i].k);
			ans = max(ans, t[1].maxn);
		}
		printf("%lld\n", ans);
	}
	return 0;
}
2024/7/17 11:47
加载中...