AcWing 1238. 日志统计(一眼想到二分直接过)
原题链接
中等
作者:
章若楠
,
2022-03-31 22:56:01
,
所有人可见
,
阅读 213
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include<unordered_map>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
vector<PII> lx;
int main()
{
ios::sync_with_stdio(false);
unordered_map<int,vector<int>>mh;
vector<int> res;
int n,d,h;
cin>>n>>d>>h;
while (n -- )
{
int t,id;
cin>>t>>id;
lx.push_back({t,id});
}
sort(lx.begin(),lx.end());
for (auto g:lx)
{
mh[g.y].push_back(g.x);
}
for (auto [k,v]:mh)
{
bool f = false;
for (int i=0;i<v.size();i++)
{
int r = upper_bound(v.begin(),v.end(),v[i]+d)-v.begin();
r--;
if (v[r]==v[i]+d) r--;
// if (k==78) cout<<i<<' '<<r<<endl;
if ((r-i+1)>=h)
{
f = true;
break;
}
}
if (f)
{
res.push_back(k);
}
}
sort(res.begin(),res.end());
for (int j:res)
cout << j<<endl;
return 0;
}