Submission #36381

#	Time	Username	Problem	Language	Result	Execution time	Memory
36381		cheater2k	Money (IZhO17_money)	C++14	100 / 100	319 ms	9988 KiB

money

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

const int N = 1000005;

int n, a[N];
int T[N];
int ans;

void upd(int x) { for (; x < N; x += x & -x) T[x]++; }
int get(int x) { int res = 0; for (; x > 0; x -= x & -x) res += T[x]; return res; }

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];

	for (int i = 1; i <= n; ) {
		int j = i; ++i;
		++ans;
		while(i <= n) {
			if (get(a[i] - 1) - get(a[j]) > 0 || a[i] < a[i - 1]) break;	
			else ++i;
		}
		for (int k = j; k < i; ++k) upd(a[k]);
	}

	cout << ans << endl;
}

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