- 选择客栈
- 2016-11-18 21:49:57 @
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cctype>
using namespace std;
int n, k, p;
vector<int> h[51];
int cost[200001];
int next0[200002];
inline int in() {
int RV = 0;
char p = getchar();
while(!isdigit(p)) {
p = getchar();
}
while(isdigit(p)) {
RV *= 10;
RV += (p - '0');
p = getchar();
}
return RV;
}
int main(int argc, const char *argv[]) {
scanf("%d %d %d", &n, &k, &p);
int color;
for (int i = 1; i <= n; ++i) {
color = in();
cost[i] = in();
h[color].push_back(i);
}
for (int i = n; i >= 1; --i) {
if (cost[i] > p)
next0[i] = next0[i + 1];
else
next0[i] = i;
}
int temp[200001];
int ans = 0;
for (int i = 0; i < k; ++i) {
int cnt = h[i].size();
for (int j = 0; j < cnt; ++j)
temp[j] = h[i][j];
for (int j = 0; j < cnt; ++j) {
int now = temp[j];
if (next0[now] == 0) break;
int p = lower_bound(temp + j + 1, temp + cnt, next0[now]) - temp;
ans += (cnt - p);
}
}
printf("%d\n", ans);
return 0;
}