Submission #533590

#	Time	Username	Problem	Language	Result	Execution time	Memory
533590		devariaota	Money (IZhO17_money)	C++17	100 / 100	1184 ms	51316 KiB

money

#include <bits/stdc++.h>
using namespace std;
int arr[1000005];
const int inf = 1e9 + 7;
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    set < int > st;
    st.insert(inf);
    int ans = 0;
    for(int i = 0; i < n; ){
        ans++;
        int j = i + 1;
        int x = *st.upper_bound(arr[i]);
        st.insert(arr[i]);
        while (j < n && arr[j - 1] <= arr[j] && arr[j] <= x){
            st.insert(arr[j]);
            j++;
        }
        i = j;
    }
    cout << ans;
}

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