Key cutting

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

#define int long long
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

pii comp(const pii& u, const pii& v) {
    if (u.first != v.first) {
        return u.first < v.first ? u : v;
    } else {
        return u.second < v.second ? u : v;
    }
}

template<class T>
struct RMQ {
    vector<vector<T>> jmp;
    RMQ(const vector<T>& V): jmp(1, V) {
        for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
            jmp.emplace_back(sz(V) - pw * 2 + 1);
            rep(j,0,sz(jmp[k])) {
                jmp[k][j] = comp(jmp[k - 1][j], jmp[k - 1][j + pw]);
                // jmp[k][j] = (jmp[k - 1][j].first < jmp[k - 1][j + pw].first) ? jmp[k - 1][j] : jmp[k - 1][j + pw];
                // jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
            }
        }
    }
    T query(int a, int b) {
        assert(a < b);
        int dep = 31 - __builtin_clz(b - a);
        return comp(jmp[dep][a], jmp[dep][b - (1 << dep)]);
        // return jmp[dep][a].first < jmp[dep][b - (1 << dep)].first ? jmp[dep][a] : jmp[dep][b - (1 << dep)];
        // return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
    }
};

int n;
vector<pair<int, int>> a;
RMQ rmq(a);
int ans;

void rec(int l, int r) {
    // cerr << l << ' ' << r << '\n';
    pii mn = rmq.query(l, r + 1);
    if (mn.first > 0) ans++;
    
    vi ind;
    ind.push_back(l - 1);
    ind.push_back(mn.second);

    while (ind.back() + 1 <= r) {
        pii cur = rmq.query(ind.back() + 1, r + 1);
        if (cur.first != mn.first) break;
        ind.push_back(cur.second);
    }

    ind.push_back(r + 1);

    // for (int x : ind) cerr << x << ' ';
    // cerr << '\n';
    
    for (int i = 1; i < sz(ind); i++) {
        if (ind[i - 1] + 1 < ind[i]) {
            rec(ind[i - 1] + 1, ind[i] - 1);
        }
    }
}

signed main() {
#ifdef LOCAL
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
#endif

    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }

    ans = 0;
    rmq = RMQ<pii>(a);
    rec(0, n - 1);
    cout << ans;
}

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