글 읽기 - 시간초과관련....

aza1200 4년 전 0

일단 저같은경우는

5
132 392 311 351 231
392 351 132 311 231

와 같이 입력이 들어올시

배열에다가 3 1 4 2 5 를 저장해두어서 1칸부터 N번쨰칸까지 돌면서

i 칸검사시 i+1 칸부터 N 번쨰 칸까지 검사를 해서 i 칸의 값보다 작은 값들의 개수의 합을 구하는 방식으로 했는데요

각 구간에대한 최댓값을 기준으로 segment 트리를 작성한 이후에 재귀함수를 이용해서 해당구간의 최댓값이 비교하고자 하는 값보다 작을 시 답을 증가시키는 방향을 썻는데 시간초과가 나네요 ㅠㅠ 어디가 문제인걸까요..ㅠㅠ

#include<algorithm>
#include<iostream>

using namespace std;

long long N, reference[1000003], Number, machine[1000003], ex;
long long segment[2000003], answer;


//idx가 관장하는 범위의 최댓값과 number를 비교하여 number 가 더클시 그 범위에 해당하는 수들 의 개수 다 더하장
long long get(int idx, int curL, int curR, int dstL, int dstR, int number) {

	//범위에 안들어갈시
	//
	if (curR<dstL || curL>dstR) return 0;


	if (dstL <= curL && curR <= dstR) {
		if (segment[idx] < number) {
			return curR - curL + 1;
		}
		else {
			if (curL == curR) return 0;
		}
	}

	int mid = (curL + curR) / 2;
	return get(idx * 2, curL, mid, dstL, dstR, number) + get(idx * 2 + 1, mid + 1, curR, dstL, dstR, number);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (ex = 1; ex < N; ex *= 2);
	for (int i = 1; i <= N; i++) {
		cin >> Number;
		reference[Number] = i;
		//i번째기계는 Number번이다.
		//반대로 Number 번을 가진 기계는 i번쨰에 위치해있다
	}
	for (int i = 1; i <= N; i++) {
		cin >> Number;
		machine[reference[Number]] = i;
	}

	for (int i = 1; i <= N; i++) segment[i + ex - 1] = machine[i];
	for (int i = ex - 1; i >= 1; i--) segment[i] = max(segment[i * 2], segment[i * 2 + 1]);
	/*
	for (int i = 1; i <= N; i++) cout << machine[i] << " ";
	cout << '\n';
	for (int i = 1; i <= 2 * ex - 1; i++) cout << segment[i] << " ";
	cout << "\n\n";
	*/
	for (int i = 1; i < N; i++) {
		//segment[i+ex-1] 부터 segment[i+n-1] 까지 중에서 segment[i+ex-1] 보다 작은수의 개수를 구하자!
		answer += get(1, ex, 2 * ex - 1, i + ex, N + ex - 1, machine[i]);
		//cout<<i<<" "<< get(1, ex, 2 * ex - 1, i + ex, N + ex - 1, machine[i])<<'\n';
	}
	cout << answer << '\n';
}

djm03178 4년 전 2

get 함수에 들어갔을 때 18번째 줄의 조건을 만족하면 반드시 리턴이 이루어져야 하는데, 19, 23번째 줄의 조건이 모두 만족되지 않을 시 다시 양방향으로 탐색을 들어가기 때문에 O(log(N)) 보장이 되지 ㅇ낳습니다.

aza1200 4년 전 0

아하 .... 감사합니다 동문선배님 ...ㅠ

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

문제

문제

출처

ICPC

시간초과관련....

aza1200 4년 전 0

djm03178 4년 전 2

aza1200 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말