Proficient.
Put your skills to the test.

Problem summary

Activity i covers every integer millisecond in [L[i],R[i]]. For each index range [X[j],Y[j]], return the number of milliseconds covered by at least one permitted activity.

Constraints

1 ≤ N,D ≤ 500,000; 1 ≤ L[i] ≤ R[i] ≤ 1,000,000; 0 ≤ X[j] ≤ Y[j] < N.

Worked example

An independently prepared example for this explanation.

5
1 5
2 7
9 11
5 10
2 4
15
0 0
0 1
0 2
0 3
0 4
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

5
7
10
11
11
6
9
10
10
3
7
10
6
9
3

Solution analysis

1. Sweep the right query endpoint r from 0 through N−1. For every millisecond, retain only the largest activity index at most r that covers it. A millisecond belongs to the union for [l,r] exactly when this latest index is at least l.
2. Represent maximal or nonmaximal constant-index pieces by a map of boundaries. The boundary at p stores the latest index on [p,nextBoundary). Initially [1,1000001) has index −1. To insert activity r, split at L[r] and R[r]+1, remove all pieces inside, and replace them by one piece labeled r. Splitting preserves all length counts.
3. A Fenwick tree stores the total length carrying each latest index. Remove the lengths of overwritten pieces from their old labels and add R[r]−L[r]+1 at r. The answer to [l,r] is the total labeled length minus the prefix for indices smaller than l. Bucket queries by their right endpoint so the sweep answers each immediately.
4. After the first three sample activities, labels 0,1,2 cover respectively [1,1], [2,7], [9,11]. Query [1,2] discards the one millisecond last covered by activity 0 and returns 6+3=9. Inserting [5,10] overwrites several pieces but preserves [2,4] and [11,11].

Why it works

After processing r, the boundary map stores precisely the latest covering activity at every point: range assignment changes exactly the new activity’s points to r and leaves the rest unchanged. The Fenwick tree counts these labels because splitting changes no length, each removed piece subtracts its length once, and the replacement adds its full length. A point is covered by some activity in [l,r] if and only if its latest covering index is at least l. The suffix sum therefore equals the required union length.

Watch out. Intervals include both endpoints, so split at R+1. Update Fenwick counts when overwriting pieces; splitting itself does not change counts. Preserve answer order.

Grader function only; no main. The displayed example is the official local-grader format.

#include<vector>
#include<map>
#include<iterator>
class Fenwick{
    std::vector<int>tree;
    public:
    explicit Fenwick(int n):tree(n+1,0){
    }
    void add(int index,int delta){
        for(++index;index<static_cast<int>(tree.size());index+=index&-index){
            tree[index]+=delta;
        }
    }
    int prefix(int count)const{
        int result=0;
        for(;count>0;count-=count&-count){
            result+=tree[count];
        }
        return result;
    }
};
std::vector<int>solve(std::vector<int>L,std::vector<int>R,std::vector<int>X,std::vector<int>Y){
    int n=static_cast<int>(L.size());
    int q=static_cast<int>(X.size());
    std::vector<int>head(n,-1),next(q),answer(q);
    for(int j=0;j<q;++j){
        next[j]=head[Y[j]];
        head[Y[j]]=j;
    }
    // A boundary maps to the most recent covering interval until the next boundary.
    std::map<int,int>segments;
    segments[1]=-1;
    segments[1000001]=-1;
    auto split=[&](int position){
        auto it=segments.lower_bound(position);
        if(it!=segments.end()&&it->first==position){
            return it;
        }
        return segments.emplace_hint(it,position,std::prev(it)->second);
    };
    Fenwick counts(n);
    for(int i=0;i<n;++i){
        auto end=split(R[i]+1);
        auto begin=split(L[i]);
        auto it=begin;
        while(it!=end){
            auto after=std::next(it);
            if(it->second!=-1){
                counts.add(it->second,-(after->first-it->first));
            }
            it=after;
        }
        segments.erase(begin,end);
        segments.emplace(L[i],i);
        counts.add(i,R[i]-L[i]+1);
        for(int j=head[i];j!=-1;j=next[j]){
            answer[j]=counts.prefix(n)-counts.prefix(X[j]);
        }
    }
    return answer;
}