#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, H[1000005], used[1000005];
set <int> s[1000005];
void solve(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> H[i];
s[H[i]].insert(i);
}
int ptr = 1, cnt = 0;
while(ptr <= n){
cnt++;
int cur = ptr, val = H[cur];
used[cur] = 1;
while(cur <= n){
if(val == 1)break;
auto it = s[val - 1].lower_bound(cur);
if(it == s[val - 1].end())break;
val--;
int tmp = *it;
s[val].erase(it);
used[tmp] = 1;
cur = tmp;
}
while(used[ptr])ptr++;
}
cout << cnt;
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
baloni.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
43 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
49756 KB |
Output is correct |
| 2 |
Correct |
11 ms |
49752 KB |
Output is correct |
| 3 |
Correct |
12 ms |
50012 KB |
Output is correct |
| 4 |
Correct |
11 ms |
50012 KB |
Output is correct |
| 5 |
Correct |
635 ms |
103000 KB |
Output is correct |
| 6 |
Correct |
730 ms |
107604 KB |
Output is correct |
| 7 |
Correct |
518 ms |
99180 KB |
Output is correct |
| 8 |
Correct |
554 ms |
98832 KB |
Output is correct |
| 9 |
Correct |
608 ms |
101180 KB |
Output is correct |
| 10 |
Correct |
608 ms |
102720 KB |
Output is correct |
