oj.uz

Submission #230996

# Submission time Handle Problem Language Result Execution time Memory
230996 2020-05-12T10:04:38 Z cstuart Baloni (COCI15_baloni) C++17
100 / 100
 1055 ms 89080 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47360 KB Output is correct
2 Correct 35 ms 47360 KB Output is correct
3 Correct 35 ms 47488 KB Output is correct
4 Correct 35 ms 47488 KB Output is correct
5 Correct 899 ms 84728 KB Output is correct
6 Correct 1055 ms 89080 KB Output is correct
7 Correct 878 ms 81788 KB Output is correct
8 Correct 807 ms 81272 KB Output is correct
9 Correct 916 ms 83192 KB Output is correct
10 Correct 962 ms 84608 KB Output is correct