Submission #710140

#	Time	Username	Problem	Language	Result	Execution time	Memory
710140		arcane	Money (IZhO17_money)	C++17	100 / 100	1188 ms	63016 KiB

money

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
const int MAX_A = 1e6 + 5;
int cnt[MAX_A];
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int ans = 0, n, x, prevx = -1; cin >> n;
	int arr[n]; for (int i = 0; i < n; i++) cin >> arr[i];
	set <int> s;
	bool flag = false;
	for (int i = 0; i < n; i++){
		x = arr[i];
		s.insert(arr[i]);
		cnt[arr[i]]++;
		if (!i){
			ans += 1;
			flag = true;
		}
		else if (flag){
			if (prevx > x){
				ans += 1;
				flag = true;
			} 
			else if (prevx < x){
				auto it = s.find(prevx);
				it++;
				if (it != s.end() and x <= *it){
					flag = false;
				}
				else ans += 1, flag = true;
			}
		}
		else{
			if (prevx > x){
				ans += 1;
				flag = true;
			}
			else if (prevx < x){
				auto it = s.find(prevx);
				it++;
				if (it != s.end() and x <= *it and cnt[prevx] == 1){
					//cerr << prevx << ' ' << *it << ' ' << x << '\n';
					flag = false;
				}
				else ans += 1, flag = true;
			}
		}
		//cerr << ans << '\n';
		//cerr << ans << ' ' << *prev << ' ' << *cur << '\n';
		prevx = x;
	}
	cout << ans;
}

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