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
| #include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a,b,c) for(int a=(b),a##end=(c);a<=a##end;++a)
#define FR(a,b,c) for(int a=(b),a##end=(c);a>=a##end;--a)
#define lowbit(x) ((x)&-(x))
#define eb emplace_back
#define sz(x) (int)((x).size())
#define int long long
#define vt vector
#define fr first
#define se second
bool IOS=(cin.tie(0)->sync_with_stdio(0),0);
#ifdef LOCAL
bool IOS1=(freopen(LOCAL".in", "r", stdin),1);
bool IOS2=(freopen(LOCAL".out", "w", stdout),1);
#endif
#define mmt(x, y) memset(x, y, sizeof x)
#define PII pair<int, int>
#define max(a, b)({auto f7r=(a);auto j3h=(b);f7r<j3h?j3h:f7r;})
#define cmax(a, b)({auto j3h=(b);(j3h>a)&&(a=j3h);})
#define min(a, b)({auto f7r=(a);auto j3h=(b);f7r>j3h?j3h:f7r;})
#define cmin(a, b)({auto j3h=(b);(j3h<a)&&(a=j3h);})
constexpr int N = 1e6 + 10;
int n, m, dx[N], dy[N], X[N], Y[N], C[N], lenx, leny, w[N];
void add(int x, int v){while(x <= lenx)w[x] += v, x += lowbit(x);}
int query(int x){int ans = 0;while(x)ans += w[x], x -= lowbit(x);return ans;}
vt<PII>e[N];
set<int>g[N];
void ___(){
cin >> n >> m;
FL(i, 1, n)cin >> X[i] >> Y[i] >> C[i], dx[i] = X[i], dy[i] = Y[i];
sort(dx + 1, dx + 1 + n), lenx = unique(dx + 1, dx + 1 + n) - dx - 1;
sort(dy + 1, dy + 1 + n), leny = unique(dy + 1, dy + 1 + n) - dy - 1;
FL(i, 1, n)
X[i] = lower_bound(dx + 1, dx + 1 + lenx, X[i]) - dx,
Y[i] = lower_bound(dy + 1, dy + 1 + leny, Y[i]) - dy;
FL(i, 1, m)g[i].emplace(0), g[i].emplace(lenx + 1);
FL(i, 1, n)e[Y[i]].eb(X[i], C[i]);
int ans = 0;
FL(i, 1, leny){
sort(e[i].begin(), e[i].end(), [](PII&a, PII&b){return a.fr < b.fr;});
for(auto&z : e[i])if(!g[z.se].count(z.fr)){
auto w = g[z.se].insert(z.fr).fr;
cmax(ans, query(*next(w) - 1) - query(*prev(w)));
}
for(auto&z : e[i])add(z.fr, 1);
}
FL(i, 1, m){
int lst = 0;
for(int z : g[i])if(z)cmax(ans, query(z - 1) - query(lst)), lst = z;
}
cout << ans << endl;
FL(i, 1, m)g[i].clear();
FL(i, 1, leny)e[i].clear();
FL(i, 1, lenx)w[i] = 0;
}
int32_t main(){
int t;
cin >> t;
while(t--)___();
return 0;
}
|
