CSES - HIIT Open 2024 - Results
Submission details
Task:Key cutting
Sender:asdf4321
Submission time:2024-11-16 13:42:11 +0200
Language:C++ (C++17)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.04 sdetails
#10ACCEPTED0.05 sdetails
#11ACCEPTED0.05 sdetails
#12ACCEPTED0.05 sdetails
#13ACCEPTED0.06 sdetails
#14ACCEPTED0.06 sdetails

Code

#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 details

Test 1

Verdict: ACCEPTED

input
3
1 2 1

correct output
2

user output
2

Test 2

Verdict: ACCEPTED

input
1
0

correct output
0

user output
0

Test 3

Verdict: ACCEPTED

input
1
9

correct output
1

user output
1

Test 4

Verdict: ACCEPTED

input
100
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
0

user output
0

Test 5

Verdict: ACCEPTED

input
100
0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 ...

correct output
25

user output
25

Test 6

Verdict: ACCEPTED

input
100
2 1 2 1 2 0 0 0 1 1 2 2 1 2 2 ...

correct output
41

user output
41

Test 7

Verdict: ACCEPTED

input
100
36 5 10 37 94 59 20 31 64 2 58...

correct output
99

user output
99

Test 8

Verdict: ACCEPTED

input
100
228768416 32415139 952687252 6...

correct output
100

user output
100

Test 9

Verdict: ACCEPTED

input
100000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
0

user output
0

Test 10

Verdict: ACCEPTED

input
100000
1 1 1 0 0 1 0 0 0 0 1 0 1 0 0 ...

correct output
24965

user output
24965

Test 11

Verdict: ACCEPTED

input
100000
2 1 2 2 2 2 2 1 1 0 1 1 0 1 1 ...

correct output
38968

user output
38968

Test 12

Verdict: ACCEPTED

input
100000
4 4 5 4 4 5 0 2 2 1 4 4 1 0 5 ...

correct output
59156

user output
59156

Test 13

Verdict: ACCEPTED

input
100000
18 5 6 16 8 10 1 7 4 15 5 9 19...

correct output
82598

user output
82598

Test 14

Verdict: ACCEPTED

input
100000
33 37 37 86 42 38 18 10 77 57 ...

correct output
94897

user output
94897