# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
419389 | cpp219 | Money (IZhO17_money) | C++14 | 1 ms | 320 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1500 + 9;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
set<ll> s;
ll n,a[N],L = inf,R,ans = 1;
bool chk(ll l,ll r){
assert(l <= r);
return (l > *s.rbegin()) || (r < *s.begin()) || (*s.lower_bound(l) == *s.lower_bound(r));
}
ll Travel(ll now){
ll kq = now;
ll l = a[now],r = a[now];
for (ll i = now + 1;i <= n;i++){
l = min(l,a[i]); r = max(r,a[i]);
if (!chk(l,r) || a[i] < a[i - 1]) break; kq = i;
}
return kq;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "tst"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
}
cin>>n; s.insert(0); s.insert(inf);
for (ll i = 1;i <= n;i++) cin>>a[i];
for (ll i = 1;i <= n;){
ll nxt = Travel(i); //cout<<nxt<<"x\n"; //return 0;
for (ll j = i;j <= nxt;j++) s.insert(a[j]);
ans += (i <= n);
i = nxt + 1;
}
cout<<ans - 1;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |