| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 710148 |
2023-03-15T05:10:49 Z |
hpesoj |
Money (IZhO17_money) |
C++17 |
|
0 ms |
212 KB |
#include <bits/stdc++.h>
#define int long long
#define pi pair <int, int>
#define ppi pair <pi, int>
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << '\n'
using namespace std;
const int inf = 1000000000;
int n, a[1000005];
set <int> s;
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
bool b = 1;
for(int i = 1; i <= n; i++){
cin >> a[i];
if(i != 1 and a[i] < a[i-1]) b = 0;
}
s.insert(a[1]);
int ans = 1, l = 2;
while(a[l] >= a[l-1]){
s.insert(a[l]);
l++;
}
//for(int i = 1; i < l; i++) cout << a[i] << ' ';
int i = l;
while(i <= n){
//try to make a[i] the same set as a[i-1]
if(i == l){
i++;
continue;
}
//check if subsegment is non-decreasing
//and that there isn't an element between the minimum and maximum of the subsegment
auto it = s.lower_bound(a[l]);
if(a[i] < a[i-1] or (it != s.end() and *it < a[i])){
ans++;
for(int j = l; j < i; j++) s.insert(a[j]);
l = i;
}
i++;
}
if(!b) ans++;
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
