oj.uz

Submission #230936

# Submission time Handle Problem Language Result Execution time Memory
230936 2020-05-12T02:19:17 Z jiahng Baloni (COCI15_baloni) C++14
100 / 100
 1143 ms 96248 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47360 KB Output is correct
2 Correct 32 ms 47488 KB Output is correct
3 Correct 33 ms 47616 KB Output is correct
4 Correct 33 ms 47616 KB Output is correct
5 Correct 944 ms 87800 KB Output is correct
6 Correct 1143 ms 96248 KB Output is correct
7 Correct 875 ms 84728 KB Output is correct
8 Correct 867 ms 84216 KB Output is correct
9 Correct 917 ms 86384 KB Output is correct
10 Correct 975 ms 87800 KB Output is correct