Submission #555606

#	Time	Username	Problem	Language	Result	Execution time	Memory
555606		ngpin04	Money (IZhO17_money)	C++14	100 / 100	1488 ms	73728 KiB

money

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int N = 1e6 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

int las[N];
int l[N];
int r[N];
int a[N];
int n;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n;
	vector <int> val;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		val.push_back(a[i]);
	}
	sort(ALL(val));
	val.resize(unique(ALL(val)) - val.begin());
	for (int i = 1; i <= n; i++)
		a[i] = lower_bound(ALL(val), a[i]) - val.begin() + 1;

	a[0] = 0;
	a[n + 1] = n + 1;
	r[0] = n + 1;
	l[n + 1] = 0;

	int ans = 0;
	set <int> s;	
	s.insert(0);
	for (int i = 1; i <= n; i++) {
		int j = r[i - 1];
		if (a[i - 1] <= a[i] && a[i] <= a[j]) {

			r[i] = j;
			l[j] = i;

			l[i] = i - 1;
			r[i - 1] = i;

			if (a[i] < a[j]) 
				las[a[i]] = i;
		} else {
			ans++;
			int pre = las[*prev(s.upper_bound(a[i]))];
			int nxt = r[pre];

			r[i] = nxt;
			l[nxt] = i;

			l[i] = pre;
			r[pre] = i;

			las[a[i]] = i;
		}

		s.insert(a[i]);
	}

	cout << ans + 1;
	return 0;
}

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