Submission #88579

#	Time	Username	Problem	Language	Result	Execution time	Memory
88579		aminra	Baloni (COCI15_baloni)	C++14	100 / 100	213 ms	47740 KiB

baloni

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e6 + 3;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
vector<int> pos[MAXN];
int n;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	int mx = 0;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		pos[a].push_back(i);
		mx = max(mx, a);
	}
	int ted = 0;
	set<int> S;
	for (int i = mx; i >= 1; i--)
	{
		for (auto u : pos[i])
		{
			if(S.empty() || *S.begin() > u)
				ted++;
			else
				S.erase(*S.begin());
		}
		S.clear();
		for (auto u : pos[i])
			S.insert(u);
	}
	cout << ted;
}

• Subtask 1: 100 / 100