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;
}