AcWing 1238. 日志统计
原题链接
中等
作者:
Bear_King
,
2021-01-25 11:35:23
,
所有人可见
,
阅读 310
日志统计
sort+双指针
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 100010
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int n,d,k;
PII logs[N];
int cnt[N];
bool st[N];
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);
for(int i = 0 , j = 0;i < n;i ++)
{
int id = logs[i].y;
cnt[id] ++;
while(logs[i].x - logs[j].x >= d)
{
cnt[logs[j].y] --;
j ++;
}
if(cnt[id] >= k) st[id] = true;
}
for(int i = 0;i < 100000;i ++)
if(st[i])
printf("%d\n",i);
return 0;
}