日志统计
作者:
Change01
,
2024-03-21 23:24:58
,
所有人可见
,
阅读 4
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define x first
#define y second
const int N = 100010;
typedef pair<int, int> PII;
PII logs[N];
int n, d, k;
int cnt[N]; //用来记录一个id号获得的赞数,表示形式为cnt[id] ++ ;
bool st[N]; //用来标记id号,因为id <= 1e5,所以可以利用遍历来输出
int main()
{
cin >> n >> d >> k;
for (int i = 0; i < n; i ++ ) scanf("%d%d", &logs[i].x, &logs[i].y);
//排序时默认以first为准排序
sort(logs, logs + n);
//双指针算法, i走在前面,j走在后面
for (int i = 0, j = 0; i < n; i ++ )
{
int id = logs[i].y; //t表示为i时刻的id号
cnt[id] ++ ; //在j时刻,id号的日记获得了一个赞
//维护一个长度为 d 的区间
while (logs[i].x - logs[j].x >= d) //两个指针跨越的时间超过了d,早期的赞过期了
{
cnt[logs[j].y] --; //减去上个区间的赞
j ++; //j指针向后移动
}
if (cnt[id] >= k) st[id] = true; //记录热帖的id号,
}
for (int i = 0; i < 100000; i ++ ) if (st[i]) printf("%d\n", i);
return 0;
}