글 읽기 - 어디가 틀린건지...ㅜㅜ

ekdlemdjq456 3년 전 0

다른 풀이들과 비슷하게 세그먼트 트리를 이용해서 풀었는데 뭐가 잘못된 건지 잘 모르겠습니다....ㅜㅜ

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

// segment tree : 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 방법.

#define MAX_N 100000

using namespace std;

int T, n;
int segment_tree[MAX_N*4];
vector<pair<int, int>> islands;
vector<int> y_islands;


bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.first == b.first)
		return a.second > b.second;
	return a.first < b.first;
}

void init_tree(int node, int start, int end) {
	if (start > end)
		return;

	if (start == end) {
		segment_tree[node] = 0;
		return;
	}
	segment_tree[node] = 0;
	int mid = (start + end) / 2;
	init_tree(node * 2, start, mid);
	init_tree(node * 2 + 1, mid + 1, end);
}

int query(int now, int left, int right, int start, int end) {
	if (left > end || right < start)
		return 0;
	if (left <= start && right >= end)
		return segment_tree[now];
	int mid = (start + end) / 2;
	return (query(now * 2, left, right, start, mid) + query(now * 2 + 1, left, right, mid + 1, end));
}

void update(int now, int target, int start, int end) {
	if (target > end || target < start)
		return;
	if (start == end) {
		segment_tree[now]++;
		return;
	}
	int mid = (start + end) / 2;
	update(now * 2, target, start, mid);
	update(now * 2 + 1, target, mid + 1, end);
	segment_tree[now] = segment_tree[now * 2] + segment_tree[now * 2 + 1];
}

bool comp_y(int a, int b) {
	return a > b;
}

void input() {
	cin >> n;
	int x, y;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		islands.push_back(make_pair(x, y));
		y_islands.push_back(y);
	}
	sort(islands.begin(), islands.end(), cmp);
	sort(y_islands.begin(), y_islands.end(), comp_y);
}

int winds() {
	int possible = 0;
	vector<pair<int, int>>::iterator iter;
	vector<pair<int, int>>::iterator y_iter;

	int x, y, index;

	for (iter = islands.begin(); iter != islands.end(); iter++) {
		y = iter->second;
		index = upper_bound(y_islands.begin(), y_islands.end(), y) - y_islands.begin() -1;
		possible += query(1, 0, index, 0, n-1);
		update(1, index, 0, n-1);
	}
	return possible;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	int result;
	for (int i = 0; i < T; i++) {
		input();
		init_tree(1, 0, n - 1);
		result = winds();
		cout << result << "\n";
		islands.clear();
		y_islands.clear();
	}
	return 0;
}

byeongkeunahn 3년 전 2

이미 해결하신 것 같기는 하지만 다른 분들을 위해 남깁니다!

upper_bound는 오름차순으로 정렬된 배열을 가정하는데, 구현에서 y_islands 배열은 y가 내림차순으로 정렬되어 있습니다. 따라서 가장 큰 y값은 n-1로, 그보다 작은 나머지 y값은 전부 -1로 매핑이 됩니다.
- 해결법은 upper_bound 호출 맨 뒤에 std::greater<>()를 추가하여 이 배열이 내림차순 정렬임을 알려주는 것입니다.
- 다르게 해결하려면 y_islands가 y에 대한 오름차순으로 정렬되도록 코드의 비교함수들을 수정해도 됩니다.
최대 출력은 75000 * (75000 - 1) / 2로 int 범위를 벗어납니다.
- 해결법은 long long 사용입니다.

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

문제

문제

출처

ICPC

어디가 틀린건지...ㅜㅜ

ekdlemdjq456 3년 전 0

byeongkeunahn 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말