/*
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|
| / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / |
| / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / |
|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ |
| \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ |
| \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ | / | \ |
| \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (signed i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (signed i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (signed i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;
template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const int maxN = 100005;
int n, a[maxN], Log2[maxN];
ii spt[20][maxN];
ii query(int l, int r) {
const int &j = Log2[r - l + 1];
return min(spt[j][l], spt[j][r - (1 << j) + 1]);
}
int rec(int l, int r) {
if (l > r)
return 0;
const int val = query(l, r).fi;
int res = (val > 0);
while (l <= r) {
if (a[l] == val) {
++l;
continue;
}
const auto [v, p] = query(l, r);
if (v == val) {
res += rec(l, p - 1);
l = p + 1;
} else {
res += rec(l, r);
break;
}
}
return res;
}
int main() {
#ifdef LOCAL
freopen("input.INP", "r", stdin);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
cin >> n;
fort(i, 1, n) {
cin >> a[i];
spt[0][i] = make_pair(a[i], i);
}
fort(i, 2, n)
Log2[i] = Log2[i >> 1] + 1;
for (int j = 1; (1 << j) <= n; ++j)
fort(i, 1, n - (1 << j) + 1)
spt[j][i] = min(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
cout << rec(1, n) << '\n';
return 0;
}
Compilation message
Main.cpp: In function 'int rec(int, int)':
Main.cpp:58:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | const auto [v, p] = query(l, r);
| ^
Main.cpp: In function 'int main()':
Main.cpp:85:67: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
85 | spt[j][i] = min(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
11 ms |
6612 KB |
Output is correct |
| 5 |
Correct |
13 ms |
10068 KB |
Output is correct |
| 6 |
Correct |
19 ms |
17620 KB |
Output is correct |
| 7 |
Correct |
19 ms |
18976 KB |
Output is correct |
