1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
#define Pair pair<LL,LL>
#define Combine Pair, greater<Pair>, pairing_heap_tag
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 1000009
#define INF 1e18
#define DBINF 1e100
#define Pi acos(-1.0)
#define eps 1e-9
#define mod 99999997
LL n,m;
LL w,h;
struct node{
LL xl,xr,y,g;
}line[MS*2];
LL hx[MS*2];
LL p[MS<<3];
LL la[MS<<3];
LL tli,thx;
bool cmp(node a,node b){
if(a.y == b.y) return a.g > b.g;
return a.y < b.y;
}
void push_down(int rt){
if(la[rt]){
p[ls] += la[rt];
p[rs] += la[rt];
la[ls] += la[rt];
la[rs] += la[rt];
la[rt] = 0;
}
}
void push_up(int rt,int l,int r){
p[rt] = max(p[ls],p[rs]);
}
void build(int l,int r,int rt){
la[rt] = p[rt] = 0;
if(l == r) return;
int m = l+r>>1;
build(l,m,ls);
build(m+1,r,rs);
}
void update(int L,int R,int l,int r,int rt,LL val){
if(L <= l && r <= R){
la[rt] += val;
p[rt] += val;
return;
}
int m = l+r>>1;
push_down(rt);
if(m >= L) update(L,R,l,m,ls,val);
if(m < R) update(L,R,m+1,r,rs,val);
push_up(rt,l,r);
}
int main() {
ios::sync_with_stdio(false);
LL ce;
cin >> ce;
while(ce--){
thx = 0;
tli = 0;
cin >> n >> w >> h;
w-- ,h--;
for(int i=1;i<=n;i++){
LL x,y,g;
cin >> x >> y >> g;
hx[++tli] = x;
line[tli] = {x,x+w,y,g};
hx[++tli] = x+w;
line[tli] = {x,x+w,y+h,-g};
}
sort(hx+1,hx+tli+1);
sort(line+1,line+tli+1,cmp);
thx = 1;
for(int i=2;i<=tli;i++){
if(hx[i] != hx[i-1]) hx[++thx] = hx[i];
}
build(1,thx,1);
LL ans = 0;
for(int i=1;i<=tli;i++){
int l = lower_bound(hx+1,hx+thx+1,line[i].xl) - hx;
int r = lower_bound(hx+1,hx+thx+1,line[i].xr) - hx;
update(l,r,1,thx,1,line[i].g);
ans = max(ans,p[1]);
}
cout << ans << endl;
}
return 0;
}
|
