글 읽기 - 시간초과 질문

sminhyuck 4년 전 0

각 x값에 y값들을 연결리스트 형식으로 저장하여 계산하도록 했습니다

시간을 어떻게 더 줄여할지 조언좀 부탁드립니다

#include <iostream>
#include <vector>
#include <algorithm>
#define FULL 400001
#define START 200000
using namespace std;
vector<int> STAR[FULL];
bool ASC(const int &a, const int &b) { return a < b; }
int MAX, MIN, CUR;	// 가장 큰 X좌표, 가장 작은 X좌표= 종료, 시작 점, 빈공간 무시 위한 커서
int INDEX[START+1];	// 인덱스에는 값이 있는 곳들의 위치가 나와있음

void init() {
	MAX = 0; MIN = FULL, CUR = 0;
	int N;		// 별의 개수
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		x += START;
		STAR[x].push_back(y);
		if (MAX < x) MAX = x;
		if (MIN > x) MIN = x;
	}

	for (int i = MIN; i <= MAX; i++) {
		if (!STAR[i].empty()) { 
			sort(STAR[i].begin(), STAR[i].end(), ASC);
			INDEX[CUR++] = i;
		}
	}
}// 입력처리

void COUNTING() {
	unsigned long long ANSWER = 0;

	for (int cur1 = 0; cur1 < CUR - 2; cur1++) {
		for (int i = 0; i < STAR[INDEX[cur1]].size(); i++) {
			int y1 = STAR[INDEX[cur1]].at(i);

			for (int cur2 = cur1 + 1; cur2 < CUR - 1; cur2++) {
				for (int j = 0; j < STAR[INDEX[cur2]].size(); j++) {
					int y2 = STAR[INDEX[cur2]].at(j);

					if (y1 <= y2) break;

					for (int cur3 = cur2 + 1; cur3 < CUR; cur3++) {
						for (int k = 0; k < STAR[INDEX[cur3]].size(); k++) {
							int y3 = STAR[INDEX[cur3]].at(k);
							if (y3 > y2) {
								ANSWER += STAR[INDEX[cur3]].size()-k;
								break;
							}
						}
					} // 마지막 탐색

					
				}
			}			// 가운데 탐색 

		}	
	}					// 시작점 탐색
	cout <<  ANSWER % 1000000007;
}

int main() {
	init();
	COUNTING();
}

atomzeno 4년 전 1

저 풀이는 잘 모르겠는데

그냥 세그먼트 트리나 인덱스 트리 형식으로 갱신해 나가면서 어느 범위에 속한 것들 개수를 세주면 O(nlogn)정도만에 될 거 같긴 하네요

sminhyuck 4년 전 0

인덱스 트리를 이용해서 다시 코드를 짜봤는데 67%, 9초쯤 시간초과가 발생하네요

조언 부탁드립니다!

#include <iostream>
#include <algorithm>
#define MAX 200001
using namespace std;
struct pos { int x, y; };
pos STAR[MAX];
int TREE[2 * MAX];	// 인덱스 트리. 별들의 X좌표를 인덱스로함. 시작은 1부터
long long MOD = 1e9 + 7;
int N;

// y를 기준으로 오름차순, 같을 땐 x를 기준으로 오름차순
bool COMP(const pos &a, const pos &b) {	
	if (a.y < b.y) return true;
	else if (a.y == b.y) return a.x < b.x;
	else return false;
}

void UPDATE(int x, int num) {
	while (x < 2 * MAX) {
		TREE[x] += num;	// x 인덱스의 트리에는 x를 포함하는 별들의 수가 담김
		x += (x & -x);	// x에 x의 가장 마지막 비트를 더함
	}
}

// 1부터 i 까지 별들의 수 
 long long SUM(int x) {
	long long result = 0;
	while (x > 0) {
		result += TREE[x];
		x -= (x & -x);	// x의 마지막 비트를 빼줌
	}
	return result;
}

// 입력 받는 동작
void init() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> STAR[i].x >> STAR[i].y;
		STAR[i].x += MAX;
		UPDATE(STAR[i].x, 1);	// x의 시작은 1부터, 별들을 트리에 입력. 트리에는 해당 인덱스 범위까지 별들의 개수가 들어있음
	}

	sort(STAR, STAR + N, COMP);
}

 long long ANSWER() {
	long long result = 0;
	int Y = -2 * MAX;
	for (int i = 0; i < N; i++) {
		if (Y != STAR[i].y) {
			Y = STAR[i].y;
			
			// 같은 Y축에 있는 별들은 V가 될 수 없으므로 제거, 현재 가리키는 별도 별들의 개수에서 제거
			for (int j = i; Y == STAR[j].y; j++) UPDATE(STAR[j].x, -1);
		}

		long long LEFT, RIGHT;	// 가장 낮은 Y축의 별을 중심으로 왼쪽, 오른쪽 별의 개수를 곱하면 해당 점에서 V를 이루는 별자리의 수가 됨
		LEFT = SUM(STAR[i].x - 1) % MOD;
		RIGHT = (SUM(2 * MAX - 1) - SUM(STAR[i].x)) % MOD;
		result += (LEFT * RIGHT) % MOD;
		result %= MOD;
	}
	return result;
}

int main() {
	init();
	cout << ANSWER() << endl;
}

atomzeno 4년 전 1

for (int j = i; Y == STAR[j].y; j++) UPDATE(STAR[j].x, -1);

이줄에서 무언가 시간초과가 날 이상한 점이 보이지 않으신가요

풀이의 문제가 아니라 작은 실수네용

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

문제

문제

출처

ICPC

시간초과 질문

sminhyuck 4년 전 0

atomzeno 4년 전 1

sminhyuck 4년 전 0

atomzeno 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말