Submission #1168077

#TimeUsernameProblemLanguageResultExecution timeMemory
1168077altern23Money (IZhO17_money)C++20
100 / 100
763 ms55196 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 1e5;
const ll INF = 4e18;
const ll MOD = 998244353;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n; cin >> n;
        vector<ll> a(n + 5);
        for(int i = 1; i <= n; i++) cin >> a[i];
        
        set<ll> st;
        ll ans = 0;
        for(int i = 1; i <= n; i++){
            auto x = st.upper_bound(a[i]);
            st.insert(a[i]);
            ll j = i + 1;
            for(;j <= n && a[j] >= a[j - 1]; j++){
                if(x != st.end() && a[j] > (*x)) break;
                st.insert(a[j]);
            }
            ans++, i = j - 1;
        }
        cout << ans << "\n";
    }   
}

/*

*/ 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...