Expert.
Put your skills to the test.

Problem summary

Horizontal boards are fixed on a wall. A falling beetle hits the highest board below it, walks to either end, then falls just outside that end. It repeats until reaching the floor. For each starting vertical gap between integer x and x+1, minimize the number of boards touched. Boards at equal height neither overlap nor touch.

Constraints

1 ≤ N ≤ 100,000; 1 ≤ x,y,d ≤ 100,000; 1 ≤ T ≤ 60,000; 1 ≤ X ≤ 100,000.

Worked example

Independently chosen example; the official PDF’s tightly spaced illustration/sample is not reused.

3
2 1 3
1 3 2
5 2 1
4
1 2 4 5

1 1 1 1

Solution analysis

1. Represent each open unit gap (x,x+1) by its integer index x. A board starting at x with length d catches all gaps x through x+d−1. Leaving its left end falls through gap x−1; leaving its right end falls through gap x+d. The half-centimeter beetle and integer coordinates make these outside gaps unambiguous.
2. Sweep boards by increasing height. Maintain for each gap the optimal remaining board count if falling from just above the processed boards. Initially every gap reaches the floor at cost zero. A new board has cost 1+min(cost[x−1],cost[x+d]); assign that value to all gaps x through x+d−1. A lazy segment tree supports these range assignments and point queries. Equal-height boards do not touch, so none of their exit gaps lies under another board in the same height group.
3. In the independent example, the lowest board covers gaps 2,3,4 and has cost one. The board at (5,2) covers gap 5 and can exit right directly to the floor, also costing one. The top board covers gaps 1,2 and can exit left to the floor, so all four queried gaps have answer one.

Why it works

Induct on the increasing-height sweep. Before processing a board, the point values describe optimal descent through all lower boards. Once the beetle lands on the new board it must choose one of exactly two exits, yielding the stated minimum plus one. That board is now the first contact for precisely its covered gaps, so overwriting their values is correct; other gaps are unaffected. Nonintersecting equal-height boards preserve this induction. After all boards, point queries are the requested full descents.

Watch out. Covered gaps end at x+d−1, but the right exit is x+d. Count the board being landed on. Use range assignment, not range minimum.

An independently written complete program with standard headers.

// Key idea: Induct on the increasing-height sweep. Before processing a board, the point values
// describe optimal descent through all lower boards.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class SegmentTree{
    int size;
    vector<int>lazy;
    void push(int node){
        if(lazy[node]!=-1){
            lazy[node*2]=lazy[node*2+1]=lazy[node];
            lazy[node]=-1;
        }
    }
    void assign(int node,int l,int r,int ql,int qr,int value){
        if(ql<=l&&r<=qr){
            lazy[node]=value;
            return;
        }
        push(node);
        int middle=(l+r)/2;
        if(ql<=middle){
            assign(node*2,l,middle,ql,qr,value);
        }
        if(qr>middle){
            assign(node*2+1,middle+1,r,ql,qr,value);
        }
    }
    int get(int node,int l,int r,int position){
        if(lazy[node]!=-1||l==r){
            return lazy[node];
        }
        int middle=(l+r)/2;
        return position<=middle?get(node*2,l,middle,position)
                                    :get(node*2+1,middle+1,r,position);
    }
    public:
    explicit SegmentTree(int n):size(n),lazy(4*n,0){
    }
    void assign(int l,int r,int value){
        assign(1,0,size-1,l,r,value);
    }
    int get(int position){
        return get(1,0,size-1,position);
    }
};
struct Board{
    int x,y,length;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<Board>boards(n);
    for(auto&board:boards){
        cin>>board.x>>board.y>>board.length;
    }
    sort(boards.begin(),boards.end(),[](const Board&a,const Board&b){
        return a.y<b.y;
    });
    SegmentTree tree(200002);
    for(const auto&board:boards){
        int cost=1+min(tree.get(board.x-1),tree.get(board.x+board.length));
        tree.assign(board.x,board.x+board.length-1,cost);
    }
    int queries;
    cin>>queries;
    for(int i=0;i<queries;++i){
        int x;
        cin>>x;
        cout<<(i?" ":"")<<tree.get(x);
    }
    cout<<'\n';
}