AcWing 1238. 日志统计 | STL, 小模拟, Hash Table, Queue, Vector
原题链接
中等
作者:
KeChang
,
2024-03-05 19:06:48
,
所有人可见
,
阅读 30
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#define x first
#define y second
using namespace std;
int n, d, k, ts, id;
map <int, vector <int>> mp;
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> d >> k;
while(n--) {
cin >> ts >> id;
mp[id].push_back(ts);
}
for(auto& tt : mp) {
sort(tt.y.begin(), tt.y.end());
queue <int> que;
int ans = 0;
for(auto& v : tt.y) {
while(!que.empty() && que.front() + d <= v) que.pop();
que.push(v);
ans = max(ans, (int)que.size());
}
if(ans >= k) cout << tt.x << '\n';
}
return 0;
}