Key cutting

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    const int inf = 1e9 + 7;
    vector<int> a(n);
    for(int &i : a) cin >> i;
    for(int &i : a) i = inf - i;
 
    int N = 1;
    while(N < n) N *= 2;
 
    vector<vector<int> > p(2*N);
    vector<int> mx(2*N);
    for(int i=0; i<n; i++){
        mx[N+i] = a[i];
        p[N+i].push_back(i);
    }
 
    for(int i=N-1; i>0; i--){
        int l = i*2;
        int r = i*2+1;
        if(mx[l] == mx[r]){
            mx[i] = mx[r];
            p[i] = p[l];
            for(int j : p[r]) p[i].push_back(j);
        } else if(mx[l] < mx[r]){
            mx[i] = mx[r];
            p[i] = p[r];
        } else {
            mx[i] = mx[l];
            p[i] = p[l];
        }
    }
 
    auto gmax = [&](int l, int r){
        l += N; r += N;
        int m = 0;
        while(l <= r){
            if(l&1) m = max(m, mx[l++]);
            if(~r&1) m = max(m, mx[r--]);
            l /= 2;
            r /= 2;
        }
        return m;
    };
 
    auto gpos = [&](int l, int r, int m){
        vector<int> pos;
        l += N; r += N;
        while(l <= r){
            if(l&1){
                if(mx[l] == m) for(int j : p[l]) pos.push_back(j);
                l++;
            }
            if(~r&1){
                if(mx[r] == m) for(int j : p[r]) pos.push_back(j);
                r--;
            }
            l /= 2;
            r /= 2;
        }
        return pos;
    };
    
    int ans = 0;
    auto dnq = [&](auto &&dnq, int l, int r) -> void {
        ans++;
        int m = gmax(l, r);
        if(m == inf){
            ans--;
        }
        auto pos = gpos(l, r, m);
        sort(pos.begin(), pos.end());
        int pr = l;
        for(int j : pos){
            if(j-pr > 0){
                dnq(dnq, pr, j-1);
            }
            pr = j+1;
        }
        if(r-pr >= 0){
            dnq(dnq, pr, r);
        }
    };
 
    dnq(dnq, 0, n-1);
 
    cout << ans << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED