글 읽기 - 혹시 안되는 케이스가 어떻게 될까요??

barcelonamessi 6년 전 0

map 자료구조를 이용했구요

map<int, long long int> m;

자료형은 번호 k에 대한 레벨을 계속 맵에 저장했습니다.

다음 번 숫자에 대해서 왼쪽으로 가장 가까운 지점의 레벨, 오른쪽으로 가장 가까운 지점의 레벨을 찾고

만약 현재 숫자가 트리의 왼쪽 끝이면 왼쪽 끝의 레벨에 +1을 했고

현재 숫자가 트리의 오른쪽 끝이면 오른쪽 끝의 레벨에 +1을 했습니다.

그리고 중간이면 바로 앞의 레벨, 바로 뒤의 레벨을 참조해서 더 큰것보다 +1을 해서 map에 저장했습니다.

혹시 안되는 케이스좀 알 수 있을까요?

#include <stdio.h>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;


int arr[300002];

int main(void) {

	int N;
	int i;
	map<int, long long int> m;
	int lowest_index;
	int uppest_index;
	long long int result = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		int cur_num;
		scanf("%d", &cur_num);
		if (i == 0) {
			m[cur_num] = 0;
			lowest_index = cur_num;
			uppest_index = cur_num;

			
			
		}
		else {
			map<int, long long int>::iterator low, up;
			pair<map<int, long long int>::iterator, map<int, long long int>::iterator> ret;
			ret = m.equal_range(cur_num);
			
			ret.first = prev(ret.first);
		
			if (ret.second == m.end()) {
				m[cur_num] = m[uppest_index] + 1;
				uppest_index = cur_num;
				result += m[cur_num];
			}
			else if(ret.first==m.end()){
				m[cur_num] = m[lowest_index] + 1;
				lowest_index = cur_num;
				result += m[cur_num];
			}
			else {
				if (ret.first->second >= ret.second->second) {
					m[cur_num] = ret.first->second + 1;
				}
				else {
					m[cur_num] = ret.second->second + 1;
				}
				result += m[cur_num];
				
			}
			


		}
		printf("%lld\n", result);
	}
	
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

혹시 안되는 케이스가 어떻게 될까요??

barcelonamessi 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말