AcWing 1238. 日志统计
原题链接
中等
作者:
RememberMe
,
2025-03-22 12:50:10
· 福建
,
所有人可见
,
阅读 1
#include <stdio.h>
#include <stdlib.h>
#define N 100010
typedef struct {
int x;
int y;
}PII;
int comparesum(const void * a, const void * b) {
PII * sumA = (PII *)a;
PII* sumB = (PII *)b;
if (sumA -> x != sumB -> x) return sumA -> x - sumB -> x;
return sumA -> y - sumB -> y;
}
PII longs[N];
int cnt[N];
int st[N];
int main() {
int n, d, k;
int i,j;
int id;
scanf("%d %d %d", &n, &d, &k);
for (i = 0; i < n; i++) scanf("%d %d", &longs[i].x, &longs[i].y);
qsort(longs, n, sizeof(PII) , comparesum);
for (i = 0 , j = 0 ; i < n ; i ++)
{
id = longs[i].y;
cnt[id] ++;
while (longs[i].x - longs[j].x >= d)
{
cnt[longs[j].y] --;
j ++;
}
if (cnt[id] >= k) st[id] = 1;
}
for (i = 0 ; i <= 100010 ; i ++)
if (st[i])
printf("%d \n",i);
return 0;
}