oj.uz

Submission #230935

# Submission time Handle Problem Language Result Execution time Memory
230935 2020-05-12T02:14:41 Z jiahng Baloni (COCI15_baloni) C++14
40 / 100
 2000 ms 131076 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;
	
	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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47360 KB Output is correct
2 Correct 31 ms 47488 KB Output is correct
3 Correct 33 ms 47744 KB Output is correct
4 Correct 34 ms 47736 KB Output is correct
5 Execution timed out 2095 ms 124796 KB Time limit exceeded
6 Runtime error 1307 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Execution timed out 2096 ms 119000 KB Time limit exceeded
8 Execution timed out 2097 ms 118136 KB Time limit exceeded
9 Execution timed out 2094 ms 121920 KB Time limit exceeded
10 Execution timed out 2095 ms 125180 KB Time limit exceeded