AcWing 1238. 日志统计
原题链接
中等
作者:
EXQS
,
2021-04-13 20:46:22
,
所有人可见
,
阅读 249
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
int N, D, K, ans;
struct node {
int id, time;
};
bool cmp(node a, node b) {
return a.time < b.time;
}
int main() {
std::ios::sync_with_stdio(0);
cin >> N >> D >> K;
vector<node> logs(N);
for (int i = 0; i < N; ++i) {
cin >> logs[i].time >> logs[i].id;
}
sort(logs.begin(), logs.end(), cmp);
set<int> ans;
map<int, int> cnt;
int j = 0;
for (int i = 0; i < N; ++i) {
while (j < N && logs[j].time - logs[i].time < D) {
cnt[logs[j].id]++;
if (cnt[logs[j].id] >= K)ans.insert(logs[j].id);
j++;
}
cnt[logs[i].id]--;
}
for (set<int>::iterator i = ans.begin(); i != ans.end(); i++)cout << *i << endl;
return 0;
}