Key cutting

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

using Z = long long int;

Z n;
vector<Z> X;
vector<pair<Z, Z>> A[20];

pair<Z, Z> q(Z a, Z b) {
    if(a > b) throw 5;
    Z len = b - a + 1;
    Z bit = 63 - __builtin_clzll(len);
    if(!(2 * (Z{1} << bit) >= len)) throw 5;
    if(!((Z{1} << bit) <= len)) throw 5;
    if(a + len - (Z{1} << bit) >= n) throw 5;
    return min(A[bit][a], A[bit][a + len - (Z{1} << bit)]);
};

Z count(Z a, Z b, Z d) {
    if(a > b) {
        return 0;
    }
    Z ret = 0;
    auto [val, pos] = q(a, b);
    if(pos < a) throw 5;
    if(pos > b) throw 5;
    if(val < d) throw 5;
    if(val > d) {
        ++ret;
    }
    ret += count(a, pos - 1, val);
    ret += count(pos + 1, b, val);
    return ret;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    X.resize(n);
    for(Z i = 0; i < n; ++i) {
        cin >> X[i];
    }

    A[0].resize(n);
    for(Z i = 0; i < n; ++i) {
        A[0][i] = {X[i], i};
    }
    for(Z b = 1; b < 20; ++b) {
        A[b].resize(n);
        for(Z i = 0; i < n; ++i) {
            A[b][i] = A[b - 1][i];
            Z j = i + (Z{1} << (b - 1));
            if(j < n) {
                A[b][i] = min(A[b][i], A[b - 1][j]);
            }
        }
    }

    cout << count(0, n - 1, 0) << "\n";

    return 0;
}

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