Expert.
Put your skills to the test.

Problem summary

Choose two integer start times for advertisements of duration M, with the first ending no later than the second starts. Customer i is present throughout [Ai,Bi]. Maximize the sum of the numbers hearing each advertisement completely; a customer hearing both counts twice.

Constraints

1 ≤ N ≤ 300000; 1 ≤ M ≤ 10^8; 1 ≤ Ai < Bi ≤ 10^8.

Worked example

Official example, transcribed with whitespace restored from the PDF.

4 5
1 12
4 11
6 15
2 7

4

Solution analysis

1. A customer contributes to the audience function f(t) exactly on the integer interval [Ai,Bi−M]. Discard empty intervals and create +1 at its left end and −1 immediately after its right end. Aggregate equal coordinates.
2. For a second start x, the best first advertisement contributes max f(t) over t≤x−M. Sweep x while a second pointer advances through all events at coordinates at most x−M, maintaining the greatest audience seen by that pointer. The current audience f(x) is maintained by the usual event sweep.
3. The objective can change only when f(x) changes, or when the prefix maximum can change: these coordinates belong to E or E+M, where E is the event set. Test this union. In the sample, starts 2 and 7 each have two listeners, giving four.

Why it works

Each retained interval describes precisely the allowed starts for its customer, so the sweep computes f exactly. For fixed second start x, all permitted first starts are precisely t≤x−M, and their best audience is the maintained prefix maximum. Between consecutive candidate coordinates neither term changes. Therefore testing every candidate finds a global optimum.

Watch out. Use inclusive customer intervals, remove at Bi−M+1, and count a person separately for both advertisements.

An independently written complete program with standard headers.

// Key idea: Each retained interval describes precisely the allowed starts for its customer, so the
// sweep computes f exactly. For fixed second start x, all permitted first starts are precisely t≤x−M,
// and their best audience is the maintained prefix maximum.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin>>n>>m;
    vector<pair<long long,int>>raw;
    for(int i=0;i<n;++i){
        long long a,b;
        cin>>a>>b;
        if(a<=b-m){
            raw.push_back({a,1});
            raw.push_back({b-m+1,-1});
        }
    }
    sort(raw.begin(),raw.end());
    vector<pair<long long,int>>events;
    for(auto e:raw){
        if(!events.empty()&&events.back().first==e.first){
            events.back().second+=e.second;
        }
        else{
            events.push_back(e);
        }
    }
    vector<long long>candidates;
    for(auto e:events){
        candidates.push_back(e.first);
        candidates.push_back(e.first+m);
    }
    sort(candidates.begin(),candidates.end());
    size_t p=0,q=0;
    int current=0,old=0,best=0,answer=0;
    for(long long x:candidates){
        while(p<events.size()&&events[p].first<=x){
            current+=events[p++].second;
        }
        while(q<events.size()&&events[q].first<=x-m){
            old+=events[q++].second;
            best=max(best,old);
        }
        answer=max(answer,current+best);
    }
    cout<<answer<<'\n';
}