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
#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;
}
# 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