AcWing 1238. 日志统计
原题链接
中等
作者:
acwing_陌路
,
2021-03-25 19:58:45
,
所有人可见
,
阅读 414
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
#define x first
#define y second
typedef pair<int,int> PII;
int n,d,k;
PII logs[N];
bool st[N];
int cnt[N];//用来记录一个id获得的赞数
int main()
{
scanf("%d%d%d",&n,&d,&k);
for(int i = 0;i < n;i++) scanf("%d%d",&logs[i].x,&logs[i].y);
sort(logs,logs + n);//默认按时间x排序
for(int i = 0,j = 0;i < n;i++)//i在前,j在后
{
int t = logs[i].y;
cnt[t]++;
while(logs[i].x - logs[j].x >= d)//如果时间段超过d
{
cnt[logs[j].y]--;
j++;
}
if(cnt[t] >= k) st[t] = true;
}
for(int i = 0;i < 100000;i++)
if(st[i])
printf("%d\n",i);
return 0;
}