Submission #467131

#	Time	Username	Problem	Language	Result	Execution time	Memory
467131		ritul_kr_singh	Money (IZhO17_money)	C++17	100 / 100	1146 ms	55296 KiB

money

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int MAX_N = 1e6+1;

int N, A[MAX_N], ans;
set<int> s = {MAX_N};

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> N;

	for(int i=0; i<N; ++i) cin >> A[i];

	for(int i=0, j; i<N; i=j){
		j = i + 1;
		int x = *s.upper_bound(A[i]);
		s.insert(A[i]);

		while(j < N && A[j-1] <= A[j] && A[j] <= x)
			s.insert(A[j++]);

		++ans;
	}

	cout << ans;
}

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