Sunset

input/code.cpp: In function 'int main()':
input/code.cpp:44:20: warning: unused variable 'l' [-Wunused-variable]
     for(int i = 1, l = 0; i <= n; i++){
                    ^

#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
using ll = long long;
using lf = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int n, q, h[100005];
int L[100005];
vector<int> seg[262150];

void build(int now, int s, int e){
    if(s == e){
        seg[now].push_back(L[s]);
        return;
    }
    int m = (s+e)>>1;
    build(now << 1, s, m);
    build(now << 1 | 1, m+1, e);
    merge(all(seg[now<<1]), all(seg[now<<1|1]), back_inserter(seg[now]));
    return;
}

int cnt(int now, int s, int e, int l, int r){
    if(e < l || s > r) return 0;
    if(l <= s && e <= r){
        return lb(all(seg[now]),l) - seg[now].begin();
    }
    int m = (s+e)>>1;
    return cnt(now<<1,s,m,l,r) + cnt(now<<1|1,m+1,e,l,r);
}

int main(){
    vector<int> D;
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n >> q;
    for(int i = 1, l = 0; i <= n; i++){
        cin >> h[i];
        while(D.size() && h[D.back()] < h[i]) D.pop_back();
        L[i] = (D.size() ? D.back() : 0);
        D.push_back(i);
    }
    build(1,1,n);

    for(int a, b; q--;){
        cin >> a >> b;
        cout << cnt(1,1,n,a,b) << '\n';
    }
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: ACCEPTED

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: ACCEPTED

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: ACCEPTED

Test 34

Group: 3

Verdict: ACCEPTED

Test 35

Group: 3

Verdict: ACCEPTED

Test 36

Group: 3

Verdict: ACCEPTED

Test 37

Group: 3

Verdict: ACCEPTED

Test 38

Group: 3

Verdict: ACCEPTED

Test 39

Group: 3

Verdict: ACCEPTED

Test 40

Group: 3

Verdict: ACCEPTED

Test 41

Group: 3

Verdict: ACCEPTED

Test 42

Group: 3

Verdict: ACCEPTED

Test 43

Group: 3

Verdict: ACCEPTED

Test 44

Group: 3

Verdict: ACCEPTED

Test 45

Group: 3

Verdict: ACCEPTED

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: ACCEPTED

Test 48

Group: 3

Verdict: ACCEPTED

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: ACCEPTED

Test 51

Group: 3

Verdict: ACCEPTED

Test 52

Group: 3

Verdict: ACCEPTED

Test 53

Group: 3

Verdict: ACCEPTED

Test 54

Group: 3

Verdict: ACCEPTED