oj.uz

답안 #44691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
44691 2018-04-04T20:28:33 Z heon Baloni (COCI15_baloni) C++14
90 / 100
 2000 ms 107448 KB 
#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

# 결과 실행 시간 메모리 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