Task: | Key cutting |
Sender: | Sold days |
Submission time: | 2024-11-16 12:51:55 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
#7 | ACCEPTED | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.02 s | details |
#10 | ACCEPTED | 0.03 s | details |
#11 | ACCEPTED | 0.03 s | details |
#12 | ACCEPTED | 0.03 s | details |
#13 | ACCEPTED | 0.04 s | details |
#14 | ACCEPTED | 0.05 s | details |
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 |