Submission #230935

#	Time	Username	Problem	Language	Result	Execution time	Memory
230935		jiahng	Baloni (COCI15_baloni)	C++14	40 / 100	2097 ms	131076 KiB

baloni

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define maxn 1000001

int N;
set <int> height[maxn];
int A[maxn];

int main(){
	fast;
	
	cin>>N;
	
	multiset <int> S;
	
	FOR(i,1,N){
		cin>>A[i];
		S.insert(A[i]);
		height[A[i]].insert(i);
	}
	
	int total = N;
	int ans = 0;
	while (total > 0){
		//throw at mx
	
		int mx = *(--S.end());

		int cur = 1;
		while (1){
			if (mx < 0 || height[mx].empty()) break;
			
			auto it = height[mx].lower_bound(cur);
			if (it == height[mx].end()) break;
			
			cur = *it;
			height[mx].erase(it);
			if (S.find(mx) != S.end()) S.erase(S.find(mx));
			
			mx--;
			total--;
		}
		ans++;
	}
	cout<<ans;
}

• Subtask 1: 40 / 100