글 읽기 - 금광 문제 무엇이 잘못된 것일까요?

kskim90 6년 전 0

아래와 같이 X좌표 Y좌표 다시 매겨서

Y좌표 1~1, ... , 1 ~maxY, 2~2, ... , 2~maxY, ... , maxY~maxY에 대해서

되대값을 segment tree로 구현을 했는데

3%까지 가고 틀렸습니다.

라고 나오네요... 무엇이 잘못된 것인지 문의드립니다.

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_INDEX = 3000;

//1 << ((int)ceil(log2(MAX_INDEX))+1)
const int MAX_TREESIZE = 8192;

typedef long long ll;
typedef struct point {
	int x;
	int y;
	int value;
	void setInfo(int in_x, int in_y, int in_value) {
		x = in_x;
		y = in_y;
		value = in_value;
	}
} point;

point points[MAX_INDEX + 1];
//segment tree, sum
ll sums[MAX_TREESIZE];
//segment tree 좌측으로부터 시작되었을 때의 최대값
ll lSums[MAX_TREESIZE];
//segment tree 우측으로부터 시작되었을 때의 최대값
ll rSums[MAX_TREESIZE];
//segment tree 구간 내 최대값
ll maxSums[MAX_TREESIZE];

int N, TREESIZE = MAX_TREESIZE;

bool sortX(const point& a, const point& b) {
	return (a.x < b.x);
}

bool sortY(const point& a, const point& b) {
	return (a.y < b.y);
}

//segment tree를 0으로 초기화한다.
void init() {
	for (int i = 1; i <= TREESIZE; ++i) maxSums[i] = rSums[i] = lSums[i] = sums[i] = 0;
}

void update(int node, int from, int to, int idx, int val) {
	if ((from > idx) || (to < idx)) return;

	if (from == to) {
		maxSums[node] = rSums[node] = lSums[node] = sums[node] += val;
		return;
	}

	int left = node * 2;
	int right = left + 1;
	int mid = (from + to) >> 1;

	update(left, from, mid, idx, val);
	update(right, (mid + 1), to, idx, val);

	sums[node] = sums[left] + sums[right];
	//우측에서 우측으로부터의 최대값, 우측의 합과 좌측의 우측으로부터의 최대값의 합 중 최대값 선택
	rSums[node] = max(rSums[right], (rSums[left] + sums[right]));
	//좌측에서 좌측으로부터의 최대값, 좌측의 합과 우측의 좌측으로부터의 최대값의 합 중 최대값 선택
	lSums[node] = max(lSums[left], (lSums[right] + sums[left]));
	//좌측에 최대값이 있는 경우, 우측에 최대값이 있는 경우, 좌축과 우측에 걸친 경우 중 최대값 선택
	maxSums[node] = max(max(maxSums[left], maxSums[right]), (rSums[left] + lSums[right]));
}

int main() {
	int maxX = 0, maxY = 0, pre = -1;
	int i, j, idxS = 0, idx, x, y, val;

	scanf("%d", &N);

	for (i = 0; i < N; ++i) {
		scanf("%d%d%d", &x, &y, &val);
		points[i].setInfo(x, y, val);
	}

	//x좌표로 정렬해서 x좌표를 다시 매김(1, ... , maxX)
	sort(points, points + N, sortX);
	for (i = 0; i < N; ++i) {
		if (points[i].x != pre) {
			++maxX;
			pre = points[i].x;
		}
		points[i].x = maxX;
	}

	//segment tree size 구함
	TREESIZE = 1 << ((int)ceil(log2(maxX)) + 1);

	//y좌표로 정렬해서 y좌표로 다시 매김(1, ... , maxY)
	sort(points, points + N, sortY);
	pre = -1;
	for (i = 0; i < N; ++i) {
		if (points[i].y != pre) {
			++maxY;
			pre = points[i].y;
		}
		points[i].y = maxY;
	}

	//처음 값으로 answer값을 초기화함
	ll answer = points[0].value;

	//1~1, ..., 1~maxY, 2~2, ..., 2~maxY, ..., maxY~maxY를 조사해서 최대값을 구함
	for (i = 1; i <= maxY; ++i) {
		//segment tree 초기화
		init();
		
		//y가 i가 되는 최초 index를 찾는다.
		while (points[idxS].y < i) ++idxS;

		idx = idxS;
		for (j = i; j <= maxY; ++j) {
			//y가 j인 값을 반영시킨다.
			while ((idx < N) && (points[idx].y == j)) {
				update(1, 1, maxX, points[idx].x, points[idx].value);
				++idx;
			}
			//최대값을 갱신한다.
			if (maxSums[1] > answer) answer = maxSums[1];
		}
	}

	printf("%lld\n", answer);

	return 0;
}

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

문제

문제

출처

ICPC

금광 문제 무엇이 잘못된 것일까요?

kskim90 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말