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