글 읽기 - 여기서 더 최적화할 방법을 모르겠습니다.

lucian0910 4년 전 0

아래 글에서 map을 사용하라는 말씀에 따라 map stl로 구현을 해봤는데 그렇게 해도 시간초과가 납니다... 어떻게 해야 시간을 더 줄일 수 있을까요?

#include <iostream>
#include <map>
using namespace std;

int main() {
	int n;
	cin >> n;
	int num;
	int root;
	int cnt = 0;
	map<int, int> m;

	for (int i = 0; i < n; i++) {
		cin >> num;
		
		if (i == 0) {
			m.insert(pair<int, int>(num, 0));
			root = num;
		}
		else {
			pair<map<int, int>::iterator, bool> pr;
	
			pr = m.insert(pair<int, int>(num, 0));
			map<int, int>::iterator iter = pr.first;
			
			if (num > root) {
				if (++iter != m.end()) {
					m[num] = (iter->second) + 1;
				}
				else {
					--iter;
					m[num] = ((--iter)->second) + 1;
				}
			}
			else {
				if (iter != m.begin()) {
					m[num] = ((--iter)->second) + 1;
				}
				else {
					m[num] = ((++iter)->second) + 1;
				}
			}
			cnt += m[num];
		}
		
		cout << cnt << endl;
	}
	return 0;
}

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

문제

문제

출처

ICPC

여기서 더 최적화할 방법을 모르겠습니다.

lucian0910 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말