Submission #867406

#	Time	Username	Problem	Language	Result	Execution time	Memory
867406		Halym2007	Money (IZhO17_money)	C++17	100 / 100	759 ms	51536 KiB

money

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 5;
#define pb push_back
#define sz size()
#define ff first
#define ss second
int a[N];
int main () {
//	freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	vector <int> seg;
	set <int> s;
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (seg.empty()) {
			seg.pb (a[i]);
			ans++;
		}
		else {
			if (seg.back() > a[i]) {
				for (int i : seg) {
					s.insert (i);
				}
				seg.clear();
				seg.pb (a[i]);
				ans++;
			}
			else if (seg.back() == a[i]) {
				seg.pb (a[i]);
			}
			else {
				// seg[0] bilen a[i] aralyk setda san bamy men shony cek etsem bolyar
				auto tr = s.upper_bound (seg[0]);
				if (tr == s.end()) {
					seg.pb (a[i]);
				}	
				else {
					if (*tr < a[i]) {
						for (int i : seg) {
						s.insert (i);
						}
						seg.clear();
						ans++;
						seg.pb (a[i]);
					}
					else seg.pb (a[i]);
				}
			}
		}
	}
	cout << ans;
}

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