AcWing 1238. 日志统计
原题链接
中等
作者:
自说i
,
2024-03-24 12:09:06
,
所有人可见
,
阅读 2
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
#define x first
#define y second
int n,k,d,num[N],res[N],cnt;
bool st[N];
int q[N],hh,tt;
vector<PII> a;
int main()
{
cin>>n>>d>>k;
for(int i=0;i<n;i++)
{
int ts,id;
cin>>ts>>id;
a.push_back({ts,id});
}
sort(a.begin(),a.end());
hh=0,tt=-1;
for(int i=0;i<n;i++)
{
int ts=a[i].x,id=a[i].y;
while(hh<=tt&&ts-a[q[hh]].x>=d)
{
num[a[q[hh]].y]--;
hh++;
}
q[++tt]=i;
num[id]++;
if(num[id]>=k&&!st[id])
{
res[cnt++]=id;
st[id]=true;
}
}
sort(res,res+cnt);
for(int i=0;i<cnt;i++)
{
cout<<res[i]<<endl;
}
}