Submission #1168077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168077		altern23	Money (IZhO17_money)	C++20	100 / 100	763 ms	55196 KiB

money

#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";
    }   
}

/*

*/ 

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55