글 읽기 - 시간초과!

sotter1020 5년 전 0

구간 트리를 공부하고 있어서

지금 하고 있는데요..

책에서는 init함수가 O(N)이라고 하고,

search함수는 logN이니까 여기서는 O(M(logN))고,

그래서 총 O(N + M(logN))이면 충분히 돌아갈거 같은데

시간초과가 나네요 ㅠㅠ 어디서 문제인 걸까요?

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
long long nums[100001];
struct segment {
	long long min = 10e9+1, max = 0;
};
struct RMQ {
	int n;
	vector<segment> tree;
	RMQ(long long nums[], int size) {
		n = size;
		tree.resize(4 * n);
		init(nums, 1, N, 1);
	}
	segment init(long long nums[], int left, int right, int node) {
		if (left == right) { 
			tree[node].min = tree[node].max = nums[left]; 
			return tree[node];
		}
		int mid = (left + right) / 2;
		segment leftS = init(nums, left, mid, 2 * node);
		segment rightS = init(nums, mid + 1, right, 2 * node + 1);
		tree[node].min = min(leftS.min, rightS.min);
		tree[node].max = max(leftS.max, rightS.max);
		return tree[node];
	}
	segment search(int a, int b, int nodeLeft, int nodeRight, int node) {
		if (a > nodeRight || b < nodeLeft) return segment();
		if (a <= nodeLeft && b >= nodeRight)
			return tree[node];
		int mid = (nodeLeft + nodeRight) / 2;
		segment left = search(a, b, nodeLeft, mid, node * 2);
		segment right = search(a, b, mid + 1, nodeRight, node * 2 + 1);
		segment ret;
		ret.min = min(left.min, right.min);
		ret.max = max(left.max, right.max);
		return ret;
	}
};
int main() {
	ios::sync_with_stdio(false);
	cout.tie(NULL), cin.tie(NULL);
	cin >> N >> M;
	for (int i = 1; i <= N; ++i)
		cin >> nums[i];
	RMQ tree(nums, N);
	while (M--) {
		int a, b;
		cin >> a >> b;
		segment ret = tree.search(a, b, 1, N, 1);
		cout << ret.min << ' ' << ret.max << endl;
	}
	return 0;
}

indioindio 5년 전 1

입출력을 빠르게 하기 위해 ios::sync_with_stdio(false); cout.tie(NULL), cin.tie(NULL); 등을 사용하신 것은 좋았습니다만,

c++ reference에 endl은 Inserts a new-line character and flushes the stream. 즉 출력 버퍼를 비우는 작업을 하기 때문에 느립니다.

그냥 '\n'만 출력하면 아무 문제 없이 통과합니다.

맞추지도 않은 문제인데, 확인 차 제출했다가 맞아버린 것 양해부탁드립니다.

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

문제

문제

출처

ICPC

시간초과!

sotter1020 5년 전 0

indioindio 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말