글 읽기 - 2%에서 시간초과가 납니다

lufovic77 3년 전 0

세그먼트 트리로 구현했구

입출력도 반복문의 경우 cstdio로 변경했습니다.

배열의 인덱스는 1부터 시작합니다.

구현 상 문제로 어디선가 무한루프가 돌고 있는 것일까요 ??

알려주시면 감사하겠습니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <limits.h>
#define FOR(i, n) for(int i=0;i<n;i++)
using namespace std;
class segT{
	private:
		int tree[300000];
	public:
		segT(vector<int> arr, int n){
			init(arr, 1, 1, n);
		}
		int init(vector<int> arr, int node, int left, int right){
			if(left == right){
				return tree[node] = arr[left];
			}
			int mid = (left+right)/2;
			return tree[node] = min(
					init(arr, node*2, left, mid), init(arr, node*2+1, mid+1, right));
		}
		int query(int l, int r, int node, int leftN, int rightN){
			if(rightN<l || leftN>r)
				return INT_MAX;
			if(l<=leftN && rightN<=r)
				return tree[node];
			int mid = (leftN+rightN)/2;
			return min(query(l, r, node*2, leftN, mid),
					query(l, r, node*2+1, mid+1, rightN));
		}
};
int main(){
	int n, m, tmp, a, b, ans;
	cin>>n>>m;
	vector <int> arr;
	arr.push_back(0);
	FOR(i, n){
		scanf("%d", &tmp);
		arr.push_back(tmp);
	}
	segT obj = segT(arr, n); 
	FOR(i, m){
		scanf("%d%d", &a, &b);
		//Do something
		ans = obj.query(a, b, 1, 1, n);
		printf("%d\n", ans);
	}
}

wbjeon2k 3년 전 1

init 함수에서 arr 을 통째로 parameter 로 넘기고 있는데

거기서 시간을 많이 잡아 먹어서 시간 초과가 나는것 같네요.

arr을 전역 변수로 빼서 parameter 로 넘기지 않으니까 시간 내에 빠르게 잘 됩니다

lufovic77 3년 전 0

감사합니다.

매번 함수로 넘길때 복사를 하느라 그랬나 보네요.

하나 또 배워갑니다 ㅎㅎ

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

문제

문제

출처

ICPC

2%에서 시간초과가 납니다

lufovic77 3년 전 0

wbjeon2k 3년 전 1

lufovic77 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말