Submission #331608

#	Time	Username	Problem	Language	Result	Execution time	Memory
331608		limabeans	Money (IZhO17_money)	C++17	100 / 100	1346 ms	58220 KiB

money

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;




int n;
int a[maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }

    set<int> st;
    st.insert(1e9);
    st.insert(a[0]);
    int ub = 1e9;

    int res = 1;
    
    for (int i=1; i<n; i++) {
	if (a[i-1]>a[i] || a[i]>ub) {
	    res++;
	    ub = *st.upper_bound(a[i]);
	}
	st.insert(a[i]);
    }

    cout<<res<<endl;  
    return 0;
}

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