"Hot post" Statistics

Original link ： Log statistics

struct log
{
    
    int t, id;
    bool operator<(const log &L) const
    {
    
        return t < L.t;
    }
} logs[N];

Simple approach

Enumerate all of length $D$ Time period , Statistics in this time period , Number of likes received per post , Thus it is concluded that “ Hot post ”.

sort(logs, logs + n); // Sort all likes by time 

for (int t = 0; t <= 100001 - D; t ++) // Enumerate each time period 
{
    
    memset(cnt, 0, sizeof(cnt));
    
    for (int i = 0; i < n; i ++) // Traverse each record 
        if (t <= logs[i].t && logs[i].t < t + D) // The likes are recorded in this time period 
        {
    
            int id = logs[i].id;
            cnt[id] ++;
            if (cnt[id] >= K) st[id] = true;
        }
}

TLE

Double pointer method

be aware ： The first $i$ Time period and $i+1$ There are many records in the same time period .

So double pointers are used to traverse all records , Maintenance pointer $j,i$ Make it long $D$ Both ends of the time period .

Be careful ： Because it enumerates in order ,$i$ Each movement of the pointer will increase the number of likes of a post , therefore $i$ The movement of the pointer produces “ Hot post ” Direct guidance of , That is, the latest “ Hot post ” It must be $i$ The post pointed to , So just judge each time $i$ Whether the post referred to by the pointer is a hot post .

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
struct log
{
    
    int t, id;
    bool operator< (const log &L) const
    {
    
        return t < L.t;
    }
} logs[N];
int cnt[N];
bool st[N];  // st[id] Recording posts id Is it a hot post 

int main()
{
    
    int n, D, K;
    cin >> n >> D >> K;
    for (int i = 0; i < n; i ++) cin >> logs[i].t >> logs[i].id;

    sort(logs, logs + n); // Sort the likes by time 

    for (int i = 0, j = 0; i < n; i ++) // Double pointer enumerates each record ,j、i Points to both ends of the time period 
    {
    
        int id = logs[i].id; //i Point to a new record 
        cnt[id] ++;

        while (logs[j].t + D <= logs[i].t) cnt[logs[j].id] --, j ++; // adjustment j, send j~i In the same time period 
        if (cnt[id] >= K) st[id] = true; // In this time period ,id It's a hot post 
    }

    for (int id = 0; id <= 100000; id ++)
        if (st[id]) cout << id << endl;

    return 0;
}