글 읽기 - 시간초과가 나는 이유

melon940925 3년 전 0

머지소트 트리를 만들어서 구현하였습니다.

다른 분들 풀이를 봐도 저랑 다른게 없어보이는데 시간초과가 나네요..

다른점이라면, 노드마다 리스트와 함께 리스트의 최댓값을 저장해두었습니다.

어떤 이유로 시간초과가 나는건지 궁금합니다.

#include <iostream>
#include <algorithm>
#include <vector>
#define F(i,n) for(int i=1; i<=n; i++)
using namespace std;
typedef long long ll;

ll input[100100];

class tree {
public:
	vector<ll> list;
	ll Max;
};
tree* t;

ll Upper_bound(ll left, ll right, ll value,vector<ll> input) {
	if (left >= right) {
		return input.size() - left;
	}
	ll mid = left + right >> 1;
	if (input[mid] <= value) {
		return Upper_bound(mid + 1, right, value, input);
	}
	else {
		return Upper_bound(left, mid, value, input);
	}
}

class Segment {
public:
	Segment(int N) {
		t = new tree[N * 4];
	}
	tree init(ll left, ll right, ll node) {
		if (left == right) {
			t[node].list.push_back(input[left]);
			t[node].Max = input[left];
			return t[node];
		}
		ll mid = (left + right) / 2;
		tree a, b;
		a = init(left, mid, node * 2);
		b = init(mid + 1, right, node * 2 + 1);
		vector<ll>& temp_a = a.list;
		vector<ll>& temp_b = b.list;
		int i=0, j = 0;
		while (i!=temp_a.size() && j!=temp_b.size()) {
			ll A = temp_a[i], B = temp_b[j];
			if (A <= B) {
				t[node].list.push_back(A);
				i++;
			}
			else {
				t[node].list.push_back(B);
				j++;
			}
		}
		if (i!=temp_a.size()) {
			while (i!=temp_a.size()) {
				t[node].list.push_back(temp_a[i++]);
			}
		}
		if (j!=temp_b.size()) {
			while (j!=temp_b.size()) {
				t[node].list.push_back(temp_b[j++]);
			}
		}
		t[node].Max = max(a.Max, b.Max);
		return t[node];
	}

	ll sum(ll left, ll right, ll start, ll end, ll node, ll k) {
		if (right<start || left>end)
			return 0;
		if (right <= end && left >= start) {
			if (t[node].Max <= k) {
				return 0;
			}
			else {
				return Upper_bound(0, t[node].list.size() - 1, k, t[node].list);
			}
		}
		ll mid = left + right >> 1;
		return sum(left, mid, start, end, node * 2, k) + sum(mid + 1, right, start, end, node * 2 + 1, k);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	F(i, N) cin >> input[i];
	Segment S(N);
	S.init(1, N, 1);
	int M;
	cin >> M;
	F(i, M) {
		ll a, b, c;
		cin >> a >> b >> c;
		printf("%lld\n", S.sum(1, N, a, b, 1, c));
	}
	return 0;
}

djm03178 3년 전 2

Upper_bound 함수의 마지막 인자가 벡터를 값으로 받고 있기 때문에 호출할 때마다 벡터의 전체 내용이 복사되어 새로운 벡터를 만들게 됩니다. 참조자로 바꾸세요.

melon940925 3년 전 0

감사합니다 덕분에 해결되었습니다!

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

문제

문제

출처

ICPC

시간초과가 나는 이유

melon940925 3년 전 0

djm03178 3년 전 2

melon940925 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말