Submission #683962

#	Time	Username	Problem	Language	Result	Execution time	Memory
683962		HamletPetrosyan	Money (IZhO17_money)	C++17	100 / 100	1064 ms	73776 KiB

money

/// -- -- ---- --- -- --
/// 19.01.2023 Thu 22:49
/// -- -- ---- --- -- --

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

#define pll pair<long long, long long>
#define all(a) (a).begin(), (a).end()
#define len(a) ((int)(a).size())
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second

const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const int N = 1e6 + 5;

ll n, a[N], ans = 0;
map<ll, bool> mp;
map<ll, bool>::iterator it;

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

	ll from = 0, kk = INF;
	for(int i = 1; i < n; i++){
		if(a[i] > kk || a[i - 1] > a[i]){
			for(int j = from; j < i; j++){
				mp[a[j]] = true;
			}
			ans++;
			from = i;
			it = mp.upper_bound(a[i]);
			if(it == mp.end()) kk = INF;
			else kk = it -> fr;
		}
	}
	ans++;
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int _ = 1;
	// cout << fixed;
	// cout.precision(9);

	// cin >> _ ;
	while(_--) solve();
	return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// just a reminder. ubuntu password is i o i
/// ---- - --------  ------ -------- -- - - -

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