Submission #44691

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44691	2018-04-04T20:28:33 Z	heon	Baloni (COCI15_baloni)	C++14	90 / 100	2000 ms	107448 KB

baloni

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1000005;

int n;
set <int> st[maxn];
int x[maxn];

auto nadi(int id, int height){
	auto it = st[height].lower_bound(id);
	if(it == st[height].end()) return -1;
	return *it;
}

int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> x[i];
		st[x[i]].insert(i);
	}
	int sol = 0;
	for(int i = 0; i < n; i++){
		if(!st[x[i]].count(i)) continue;
		sol++;
		int pos = i;
		while(pos >= 0){
			st[x[pos]].erase(pos);
			pos = nadi(pos,x[pos]-1);
		}
	}
	cout << sol;
}

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	47352 KB	Output is correct
2	Correct	38 ms	47472 KB	Output is correct
3	Correct	38 ms	47660 KB	Output is correct
4	Correct	43 ms	47872 KB	Output is correct
5	Correct	1637 ms	91472 KB	Output is correct
6	Correct	1865 ms	100020 KB	Output is correct
7	Correct	1505 ms	100020 KB	Output is correct
8	Correct	1450 ms	100020 KB	Output is correct
9	Correct	1662 ms	102644 KB	Output is correct
10	Execution timed out	2009 ms	107448 KB	Time limit exceeded