Submission #36151

#	Time	Username	Problem	Language	Result	Execution time	Memory
36151		YoLo	Money (IZhO17_money)	C++14	100 / 100	246 ms	9988 KiB

money

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define pi acos(-1)
#define pque priority_queue
#define N 1000000
#define lmax LONG_LONG_MAX
typedef pair < int, int > ii;
typedef vector < int > vi;
typedef vector < vi > vii;
int mod = 1000000007;
int n, a[1000009], bit[1000009], ans, l = 1, r;
void updbit(int u)
{
	while(u <= 1000000)
	{
		bit[u] ++;
		u = (u + (u & ( - u)));
	}
}
int getbit(int u)
{
	int res = 0;
	while(u > 0)
	{
		res += bit[u];
		u = (u - (u & ( - u)));
	}
	return res;
}
signed main()
{
	ios_base::sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
	while(l <= n)
	{
		r = l + 1;
		while(r <= n)
		{
			if(getbit(a[r] - 1) - getbit(a[l]) > 0 || a[r - 1] > a[r])
			{
				ans ++;
				break;
			}
			r ++;
		}
		for(int i = l; i < r; i ++)
			updbit(a[i]);
		l = r;
	}
	cout << ans + 1;
}

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