oj.uz

Submission #230933

# Submission time Handle Problem Language Result Execution time Memory
230933 2020-05-12T02:06:15 Z jiahng Baloni (COCI15_baloni) C++14
60 / 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;
int num[maxn];
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]);
		num[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 = 0;
		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);
			S.erase(S.find(mx));
			mx--;
			total--;
		}
		ans++;
	}
	cout<<ans;
}

Subtask #1
60.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 47736 KB Output is correct
4 Correct 32 ms 47872 KB Output is correct
5 Execution timed out 2092 ms 128412 KB Time limit exceeded
6 Runtime error 1268 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 1949 ms 121852 KB Output is correct
8 Correct 1995 ms 120952 KB Output is correct
9 Execution timed out 2084 ms 125304 KB Time limit exceeded
10 Execution timed out 2092 ms 128120 KB Time limit exceeded