各路大神球条
查看原帖
各路大神球条
943083
WaterM楼主2024/12/11 23:34

WA10pts,只过了第一个点(悲)

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Linf 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int> 
#define all(v) v.begin(), v.end()
using namespace std;

//#define filename "xxx" 
#define FileOperations() freopen(filename".in", "r", stdin), freopen(filename".out", "w", stdout)


namespace Traveller {
	const int N = 1e4+2, V = 1e6+2;
	
	int n, w, h;
	struct point {
		int x, y, val;
		point() { }
		point(int x, int y, int val) : x(x), y(y), val(val) { }
	} a[N];
	
	vector<int> v;
	int l[N], r[N];
	
	
	struct node {
		node *l, *r;
		int val;
		int tag;
		void up() { val = max(l->val, r->val); }
		void upd(int v) { val += v, tag += v; }
		void down() { if(tag) l->upd(tag), r->upd(tag), tag = 0; }
	} pool[N << 1], *tmp = pool;
	
	node *newnode() {
		tmp->l = tmp->r = NULL;
		tmp->val = 0;
		tmp->tag = 0;
		return tmp++;
	}
	
	class SegmentTree {	//区间加,全局最大
		public:
			node *root;
			int l, r;
			SegmentTree(int l = 0, int r = 0) : l(l), r(r), root(NULL) { }
		
		public:
			void build(node *&p, int l, int r) {
				p = newnode();
				if(l == r) return;
				int mid = l+r >> 1;
				build(p->l, l, mid);
				build(p->r, mid+1, r);
				p->up();
			}
			void update(node *p, int l, int r, int ql, int qr, int v) {
				if(l == ql && r == qr) {
					p->upd(v);
					return;
				}
				p->down();
				int mid = l+r >> 1;
				if(mid >= qr) update(p->l, l, mid, ql, qr, v);
				else if(mid < ql) update(p->r, mid+1, r, ql, qr, v);
				else {
					update(p->l, l, mid, ql, mid, v);
					update(p->r, mid+1, r, mid+1, qr, v);
				}
				p->up();
			}
			int query() { return root->val; }
			
			void build(int l, int r) {
				tmp = pool;
				*this = SegmentTree(l, r);
				build(root, l, r);
			}
			void update(int ql, int qr, int v) { update(root, l, r, ql, qr, v); }
	} tr;
	
	
	void main() {
		vector<int>().swap(v);
		
		cin >> n >> w >> h;
		for(int i = 1, x, y, val; i <= n; ++i) {
			scanf("%d%d%d", &x, &y, &val);
			a[i] = point(x, y, val);
			v.push_back(y);
		}
		
		sort(all(v));
		v.erase(unique(all(v)), v.end());
		for(int i = 1; i <= n; ++i) {
			l[i] = lower_bound(all(v), a[i].y - h + 1) - v.begin() + 1;
			r[i] = upper_bound(all(v), a[i].y) - v.begin();
		}
		
		sort(a+1, a+n+1, [](point a, point b) { return a.x < b.x; });
		int ans = 0;
		tr.build(1, n);
		for(int i = 1, p = 1; i <= n; ++i) {
			tr.update(l[i], r[i], a[i].val);
			while(p < i && a[p].x <= a[i].x - w) tr.update(l[p], r[p], -a[p].val), ++p;
			ans = max(ans, tr.query());
		}
		cout << ans << '\n';
	}
}

signed main() {
	#ifdef filename
		FileOperations();
	#endif
	
	int _;
	cin >> _;
	while(_--) Traveller::main();
	return 0;
}

2024/12/11 23:34
加载中...