单调队列88pts求助!!!

P8661 [蓝桥杯 2018 省 B] 日志统计

Eric_jx @ 2023-04-12 21:38:44


#include<bits/stdc++.h>
using namespace std;
struct stu{
    int ti,id;
}a[1000001];
bool cmp(stu x,stu y){
    if(x.ti!=y.ti){
        return x.ti<y.ti;
    }
    return x.id<y.id;
}
int q[1000001];
int head=1,tail=0;
int c[1000001];
int ans[1000001];
int main(){
    int n,d,k,maxn=0;
    cin>>n>>d>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].ti>>a[i].id;
        maxn=max(maxn,a[i].id);
    }
    sort(a+1,a+1+n,cmp);
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i].ti>=d){
            while(head<=tail&&a[q[head]].ti<a[i].ti-d+1){
                head++;
            }
        }
        q[++tail]=i;
        for(int j=head;j<=tail;j++){
            c[a[q[j]].id]++;
            if(c[a[q[j]].id]>=k){
                ans[++cnt]=a[q[j]].id;
            }
        }
        for(int j=head;j<=tail;j++){
            c[a[q[j]].id]--;
        }
    } 
    sort(ans+1,ans+cnt+1); 
    for(int i=1;i<=cnt;i++){
        cout<<ans[i]<<"\n";
        while(ans[i]==ans[i+1]&&i<cnt){
            i++;
        }
    }
    return 0;
}

|