Submission #230996

#	Time	Username	Problem	Language	Result	Execution time	Memory
230996		cstuart	Baloni (COCI15_baloni)	C++17	100 / 100	1055 ms	89080 KiB

baloni

#define USE_MATH_DEFINES 1
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MOD 998244353ll
#define INF 1000000000000000000ll
#define EPS 1e-9
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock

typedef long long         ll;
typedef long double       ld;
typedef pair <ll,ll>      pl;
typedef tuple <ll,ll,ll>  tl;

ll N, acnt, maxh, chgt, cpos;
set <ll> H[1000005];

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;
	
	for (ll i = 1; i <= N; i++) {
		ll x;
		cin >> x;
		H[x].insert(i);
	}
	
	acnt = 0;
	maxh = 1000000;
	
	while (maxh > 0) {
		if (H[maxh].empty()) {
			maxh--;
			continue;
		}
		acnt++;
		chgt = maxh;
		cpos = 0;
		while (true) {
			auto it = H[chgt].upper_bound(cpos);
			if (it == H[chgt].end()) break;
			cpos = *it;
			H[chgt].erase(it);
			chgt--;
		}
	}
	
	cout << acnt;
	
    return 0;
}

• Subtask 1: 100 / 100