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
| #define DREP(i, s, e) for(int i = s; i >= e ;i--)
#define REP(i, s, e) for(int i = s; i <= e ;i++)
#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 10, maxk = 2000000;
template <typename T> inline T read()
{
T ans(0), p(1);
char c = getchar();
while (!isdigit(c))
{
if (c == '-') p = -1;
c = getchar();
}
while (isdigit(c))
{
ans = ans * 10 + c - 48;
c = getchar();
}
return ans * p;
}
int n, k;
struct flower
{
int s, c, m, id;
flower(){}
flower(int _s, int _c, int _m, int _id) : s(_s), c(_c), m(_m), id(_id){}
}f[maxn];
bool cmp(flower A, flower B) {return A.s < B.s;}
vector <int> s[maxn];
void update(int c, int m)
{
while (c <= k)
{
s[c].insert(lower_bound(s[c].begin(), s[c].end(), m), m);
c += c & -c;
}
}
int ans[maxn];
int query(int c, int m)
{
int res = 0;
while (c > 0)
{
res += lower_bound(s[c].begin(), s[c].end(), m+1) - s[c].begin();
c -= c & -c;
}
return res-1;
}
int cnt[maxn];
int main()
{
#ifdef CraZYali
freopen("B.in", "r", stdin);
freopen("B.out", "w", stdout);
freopen("B.err", "w", stderr);
#endif
cin >> n >> k;
REP(i, 1, n)
{
int s(read<int>()), c(read<int>()), m(read<int>());
f[i] = flower(s, c, m, i);
}
sort(f + 1, f + 1 + n, cmp);
int last = 1;
REP(i, 1, n)
{
if (i > 1 && f[i].s ^ f[i-1].s)
{
REP(j, last, i-1)
cnt[ans[f[j].id] = query(f[j].c, f[j].m)]++;
last = i;
}
update(f[i].c, f[i].m);
}
REP(i, last, n) cnt[ans[f[i].id] = query(f[i].c, f[i].m)]++;
REP(i, 0, n-1) printf("%d\n", cnt[i]);
return 0;
}
|
