[sliding window] group B of the 9th Landbridge cup provincial tournament: log statistics

 

  Ideas ： The maximum length of the interval is D,id and t After pairing , Sort by time , Maintain the interval with double pointers , The maximum length of this interval shall not exceed D.

cnt[id] Current interval record id Number of occurrences .

st[id] Record id Is it a hot post .

Only the right and left endpoints of the interval need to be maintained .

Reference resources ACWING Pear painted Xiaotang The antithesis of ：

AcWing 1238. Log statistics - AcWing

 

import java.util.*;
        import java.io.*;
        import java.math.*;
public class Main{
    static final int N=100010;
    static int n,d,k;
    static int[] cnt=new int[N];
    static boolean[] st=new boolean[N];
    static PII[] logs= new PII[N];
    public static void main(String[]args) throws IOException{
        
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[]s=br.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        d=Integer.parseInt(s[1]);
        k=Integer.parseInt(s[2]);
        for(int i=0;i<n;i++){
            String[]str=br.readLine().split(" ");
            int t=Integer.parseInt(str[0]);
            int id=Integer.parseInt(str[1]);
            logs[i]=new PII(t,id);
        }
        Arrays.sort(logs,0,n);
        for(int i=0,j=0;i<n;i++){
            cnt[logs[i].id]++;
            while(logs[i].t-logs[j].t>=d){
                cnt[logs[j].id]--;
                j++;
            }
            if(cnt[logs[i].id]>=k)st[logs[i].id]=true;
        }
        for(int i=0;i<N;i++){
            if(st[i]==true)System.out.println(i);
        }
    }
}


class PII implements Comparable<PII>{
        int t,id;
        public PII(int t,int id){
            this.t=t;
            this.id=id;
        }
        public int compareTo(PII o){
            return Integer.compare(t,o.t);
        }
    }