CSES - HIIT Open 2024 - Results
Submission details
Task:Key cutting
Sender:Sold days
Submission time:2024-11-16 12:51:55 +0200
Language:C++ (C++20)
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.02 sdetails
#10ACCEPTED0.03 sdetails
#11ACCEPTED0.03 sdetails
#12ACCEPTED0.03 sdetails
#13ACCEPTED0.04 sdetails
#14ACCEPTED0.05 sdetails

Code

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

const int INF = (int)1e9;

struct SegTree {
    vector<int> mins;

    SegTree(vector<int> a) : mins(4 * a.size()) {
        build(0, 0, a.size(), a);
    }

    void build(int i, int l, int r, const vector<int>& arr) {
        if (l + 1 == r) {
            mins[i] = arr[l];
            return;
        }

        int m = (l + r) / 2;
        build(i * 2 + 1, l, m, arr);
        build(i * 2 + 2, m, r, arr);
        mins[i] = min(mins[i * 2 + 1], mins[i * 2 + 2]);
    }

    int get(int i, int l, int r, int ql, int qr) {
        if (l >= qr || ql >= r) {
            return INF;
        }
        if (ql <= l && r <= qr) {
            return mins[i];
        }

        int m = (l + r) / 2;
        return min(get(i * 2 + 1, l, m, ql, qr),
            get(i * 2 + 2, m, r, ql, qr));
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 0;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    SegTree st(a);

    map<int, int> prev;
    int ans = n;
    for (int i = 0; i < n; ++i) {
        if (prev.count(a[i])) {
            if (st.get(0, 0, n, prev[a[i]], i) == a[i]) {
                ans--;
            }
        } else {
            if (a[i] == 0) {
                ans--;
            }
        }
        prev[a[i]] = i;
    }

    cout << ans << endl;

    return 0;
}

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