Submission #88579

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
88579	2018-12-06T18:02:09 Z	aminra	Baloni (COCI15_baloni)	C++14	100 / 100	213 ms	47740 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	23 ms	23940 KB	Output is correct
3	Correct	24 ms	23980 KB	Output is correct
4	Correct	24 ms	24060 KB	Output is correct
5	Correct	199 ms	32260 KB	Output is correct
6	Correct	213 ms	35736 KB	Output is correct
7	Correct	171 ms	39192 KB	Output is correct
8	Correct	171 ms	40424 KB	Output is correct
9	Correct	185 ms	45280 KB	Output is correct
10	Correct	188 ms	47740 KB	Output is correct