제출 #230936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230936		jiahng	Baloni (COCI15_baloni)	C++14	100 / 100	1143 ms	96248 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;
	
	set <int> S;
	
	FOR(i,1,N){
		cin>>A[i];
		S.insert(A[i]);
		height[A[i]].insert(i);
	}
	
	int total = N;
	int ans = 0;
	auto mxit = --S.end();
	
	while (total > 0){
		//throw at mx
	
		while (height[*mxit].empty()){
			if (mxit == S.begin()) break;
			mxit--;
		}
		
		int mx = *mxit;

		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);
			
			mx--;
			total--;
		}
		ans++;
	}
	cout<<ans;
}

• Subtask 1: 100 / 100