Why does this solution pass ECPC2024 Problem D ??

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

problem statement

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000;
int  n, q, B;                          
int  val[MAXN + 2];                     
int  lazy[(MAXN+450)/450 + 2];         

void addLamp(int L,int R){             
    int bl = L / B , br = R / B;

    if (bl == br){                    
        for (int i=L;i<=R;++i) val[i] = max(val[i], R);
        return;
    }

    int endL = (bl+1)*B - 1;
    for (int i=L;i<=endL;++i) val[i] = max(val[i], R);

    for (int b=bl+1;b<br;++b)
        lazy[b] = max(lazy[b], R);

    int startR = br*B;
    for (int i=startR;i<=R;++i) val[i] = max(val[i], R);
}

int minLamps(int L,int R){              
    int cur=L, ans=0;
    while (cur <= R){
        int b   = cur / B;
        int best = max(val[cur], lazy[b]);   
        if (best < cur) return -1;          
        ++ans;
        cur = best + 1;                      
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    B = int(sqrt(n)) + 1;
    fill(val,  val+n+2, -1);
    fill(lazy, lazy+ (n+B-1)/B + 2, -1);
    while (q--){
        int t,L,R; cin >> t >> L >> R;
        --L; --R;                           
        if (t==1) addLamp(L,R);
        else      cout << minLamps(L,R) << '\n';
    }
}

I'm solving a problem where I can insert lamps on a street segment [L, R], and later need to answer queries like: “What’s the minimum number of lamps needed to fully cover [L, R]?”

In my solution (which passed all tests), each query walks from L to R using a greedy jump to the farthest lamp covering the current position. In the worst case — like when every lamp covers only one position — this query can walk every single position in [L, R], so O(N) per query.

Since there can be up to Q = N = 2·10⁵ such queries, isn’t the total worst-case complexity O(N²)?

Yet the solution is accepted . Why does it pass if O(N²) time is theoretically possible? Does the test data avoid this case? Or is there something I’m missing in the analysis?