Task: | Key cutting |
Sender: | asdf4321 |
Submission time: | 2024-11-16 13:42:11 +0200 |
Language: | C++ (C++17) |
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.04 s | details |
#10 | ACCEPTED | 0.05 s | details |
#11 | ACCEPTED | 0.05 s | details |
#12 | ACCEPTED | 0.05 s | details |
#13 | ACCEPTED | 0.06 s | details |
#14 | ACCEPTED | 0.06 s | details |
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 |