当前位置:网站首页>Log statistics (double pointer)
Log statistics (double pointer)
2022-07-06 16:25:00 【AC__ dream】
This problem is a double pointer problem , Let's sort the likes by time , We set up i and j Respectively indicates that the current time period is less than k Hot post boundary , Each time the right boundary corresponds to id Zanga 1, If satisfied, praise equals k, Set as true, When the time period is greater than k When the current left boundary is represented id Praise and subtract 1, Enumerate , Until the end , What needs attention is the boundary problem , See the code for details :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e5+10;
bool vis[N];
int n,d,k,cnt[N];
struct node{
int ts,id;
}p[N];
bool cmp(node a,node b)
{
return a.ts<b.ts;
}
int main()
{
cin>>n>>d>>k;
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i].ts,&p[i].id),p[i].id++;
sort(p+1,p+n+1,cmp);
cnt[p[0].id]++;
for(int i=0,j=1;j<=n;i++)
{
while(p[j].ts-p[i].ts<d&&j<=n)
{
cnt[p[j].id]++;
if(cnt[p[j].id]==k) vis[p[j].id]=true;
j++;
}
cnt[p[i].id]--;
}
for(int i=1;i<=100001;i++)
if(vis[i]) printf("%d\n",i-1);
return 0;
}
边栏推荐
- 1005. Maximized array sum after K negations
- Codeforces Round #803 (Div. 2)A~C
- Remove the border when input is focused
- input 只能输入数字,限定输入
- Candy delivery (Mathematics)
- (lightoj - 1354) IP checking (Analog)
- (POJ - 3579) median (two points)
- QT实现圆角窗口
- (lightoj - 1370) Bi shoe and phi shoe (Euler function tabulation)
- Understand what is a programming language in a popular way
猜你喜欢
QT有关QCobobox控件的样式设置(圆角、下拉框,向上展开、可编辑、内部布局等)
Codeforces Round #797 (Div. 3)无F
Raspberry pie 4B installation opencv3.4.0
读取和保存zarr文件
Browser print margin, default / borderless, full 1 page A4
OneForAll安装使用
Openwrt source code generation image
Local visualization tools are connected to redis of Alibaba cloud CentOS server
去掉input聚焦时的边框
Li Kou: the 81st biweekly match
随机推荐
Understand what is a programming language in a popular way
C language is the watershed between low-level and high-level
QWidget代码设置样式表探讨
Suffix expression (greed + thinking)
QT implementation fillet window
Auto. Getting started with JS
807. Maintain the urban skyline
去掉input聚焦时的边框
Codeforces Round #798 (Div. 2)A~D
“鬼鬼祟祟的”新小行星将在本周安全掠过地球:如何观看
Acwing: the 56th weekly match
(POJ - 2739) sum of constructive prime numbers (ruler or two points)
875. 爱吃香蕉的珂珂 - 力扣(LeetCode)
Browser print margin, default / borderless, full 1 page A4
Install Jupiter notebook under Anaconda
pytorch提取骨架(可微)
Classic application of stack -- bracket matching problem
1005. Maximized array sum after K negations
2078. Two houses with different colors and the farthest distance
875. Leetcode, a banana lover