글 읽기 - 세그먼트+분할정복 시간초과 질문입니다...

hschoi1104 5년 전 0

페어로 {값,인덱스}를 저장한 세그먼트 + 분할정복으로 풀었습니다
밑의 게시글의

4 1 3 3 1 예제 답:6

그리고 인터넷에 돌아다니는 테케들 중에서 숫자가 적은것들은 답이 잘 나오는데요
제출시 33프로에서 시간초과가 나네요...

아마 n의 수가 엄청날때 통과를 못하는거같은데 update의 시간복잡도를 줄이거나 아니면 제가 다른 부분에서 실수한게있을까요...?

고수님들 한수부탁드립니다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
ll INF = 10000000000;
typedef pair<ll, ll>P;
vector<P> node;
ll h = 1;
ll ans = 0;

void update(ll i, ll val) {
#
}
P query(ll L, ll R, ll nodeNum, ll nodeL, ll nodeR) {
	if (L <= nodeL&&nodeR <= R) return node[nodeNum];
	else if (nodeR < L || R < nodeL) return{ INF,INF };
	ll mid = (nodeL + nodeR) / 2;
	if (query(L, R, nodeNum * 2, nodeL, mid).first <= query(L, R, nodeNum * 2 + 1, mid + 1, nodeR).first)
		return query(L, R, nodeNum * 2, nodeL, mid);
	else
		return query(L, R, nodeNum * 2 + 1, mid + 1, nodeR);
}
P go(ll l, ll r) {
	#
}
int main(void) {
	while (1) {
		int n;
		scanf("%d", &n);
		if (n == 0) break;
		while (h < n) h <<= 1;
		node.resize(h * 2);
		for (int i = h; i < 2*h; i++) {
			node[i] = { INF,INF };
		}
		for (int i = 1; i <= n; i++) {
			ll x;
			scanf("%lld", &x);
			update(i, x);
		}
		printf("%lld\n", go(1, n).first);
		ans = 0;
        //node.claer();
	}
	return 0;
}

hschoi1104 5년 전 1

자문자답 : 쿼리함수 19~22 에서 시간초과가 나는거였습니다

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

문제

문제

출처

ICPC

세그먼트+분할정복 시간초과 질문입니다...

hschoi1104 5년 전 0

hschoi1104 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말