글 읽기 - 시간 초과

lee0289 5년 전 0

아래 코드 시간초과 나는데요.
어느 부분에서 시간을 많이 잡아 먹는걸까요?
비슷한 문제 10868에서 최솟값만 구할 때는 시간초과가 없었는데,
최소, 최대 페어로 구하는 현재 문제에서 다르게 처리해야 하는 부분이 있나요?

#include <iostream>
#include <cstdio>

using namespace std;

double a[100001];
int tree[300001];
int tree_max[300001];

void init(int node, int start, int end) {
	if(start == end) {
		tree[node] = a[start];
	} else {
		init(node*2, start, (start+end)/2);
		init(node*2+1, (start+end)/2+1, end);
		tree[node] = min(tree[node*2], tree[node*2+1]);
	}
}

void init_max(int node, int start, int end) {
	if(start == end) {
		tree_max[node] = a[start];
	} else {
		init_max(node*2, start, (start+end)/2);
		init_max(node*2+1, (start+end)/2+1, end);
		tree_max[node] = max(tree_max[node*2], tree_max[node*2+1]);
	}
}

int query(int node, int start, int end, int i, int j) {
	if(i > end || j < start ) return -1;
	if(i <= start && end <=j) return tree[node];
	
	int m1 = query(2*node, start, (start+end)/2, i, j);
	int m2 = query(2*node+1, (start+end)/2+1, end, i, j);
	
	if(m1 == -1) return m2;
	else if(m2 == -1) return m1;
	else return min(m1, m2);
}

int query_max(int node, int start, int end, int i, int j) {
	if(i > end || j < start ) return -1;
	if(i <= start && end <=j) return tree_max[node];
	
	int m1 = query_max(2*node, start, (start+end)/2, i, j);
	int m2 = query_max(2*node+1, (start+end)/2+1, end, i, j);
	
	if(m1 == -1) return m2;
	else if(m2 == -1) return m1;
	else return max(m1, m2);
}

int main() {
	ios::sync_with_stdio(false);
	int n, m;
	
	cin >> n;
	cin >> m;
	
	int start_range;
	int end_range;
	
	for(int i=0; i<n; i++) cin >> a[i];
	
	init(1, 0, n-1);
	init_max(1, 0, n-1);
	
	for(int i=0; i<m; i++) {
		cin >> start_range;
		cin >> end_range;
		int ans = query(1, 0, n-1, start_range-1, end_range-1);
		int ans_max = query_max(1, 0, n-1, start_range-1, end_range-1);
		cout << ans << ' ' << ans_max << '\n';
	}
	return 0;
}

djm03178 5년 전 0

이 코드와 같이 cin과 cout이 번갈아 호출되는 경우에는 sync_with_stdio(false)보다도 훨씬 중요한 문장이 cin.tie(NULL); 입니다. cin은 cout과 기본적으로 묶여있어 cin을 할 때마다 cout을 flush시키기 때문에, 이를 해제해주면 눈에 띄는 속도 향상을 볼 수 있습니다.

lee0289 5년 전 0

앗,, 되네요. 감사합니다.

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

문제

문제

출처

ICPC

시간 초과

lee0289 5년 전 0

djm03178 5년 전 0

lee0289 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말