AcWing 1238. 日志统计
原题链接
中等
作者:
hutacm602
,
2021-03-01 20:58:59
,
所有人可见
,
阅读 339
# include<unordered_map>
# include<functional>
# include<algorithm>
# include<iostream>
# include<cstring>
# include<utility>
# include<string>
# include<cstdio>
# include<cmath>
# include<queue>
# include<stack>
# include<map>
# include<set>
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define per(i,be,en) for(int i=be;i>=en;i--)
# define out(i) ou(i),puts("")
# define x first
# define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int inf = 0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
///*
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void ou(ll x)
{
char ch[25];int len=0;
if(x<0){putchar('-');x=~x+1;}
do {ch[len++]=x%10+'0';x/=10;}while(x>0);
for(int i=len-1;i>=0;i--) putchar(ch[i]);
return;
}
//*/
const int maxn = 1e5+5;
const int N = 500;
PII a[maxn];
bool st[maxn];
int cnt[maxn];
int main()
{
//ios::sync_with_stdio(0);
//cin.tie(0),cout.tie(0);
int n = read(),d = read(),k = read();
rep(i,1,n)
{
a[i].x=read(),a[i].y = read();
}
sort(a+1,a+1+n);
int l = 1,r = 1;
while(r<=n)
{
cnt[a[r].y]++;
while(a[r].x - a[l].x >= d)
{
cnt[a[l].y]--;
l++;
}
if(cnt[a[r].y] >= k) st[a[r].y] = 1;
r++;
}
rep(i,1,1e5)
{
if(st[i] == 1)
{
out(i);
}
}
return 0;
}