글 읽기 - 코드 질문있어요;

na982 6년 전 0

아래 코드는 오답 코드 인데

주석으로 되어있는 my_lower_bound 함수를 이용하면 정답이 되더군요;

어찌 어찌 하다가 수정해서 맞췄는데;

이런 바이너리 서치 같은 코드를 구현할때 팁 같은게 있을까요?;

stl을 사용하면 됩니다 이런 답변 말구요~ㅎㅎㅎ 구현할때 도움이 될만한 팁있으시면 공유 부탁 드려요~

감사합니다.

#include <stdio.h>
#include <vector>
using namespace std;

const int MAX_ST = 262144;
                  
struct SegTree {
	int size, start;
	vector<int> arr[MAX_ST];

	SegTree(int n) {
		size = n;
		start = 1;
		while (start < size) start *= 2;
	}

	void add(int index, int val) {
		index += start;
		arr[index].push_back(val);
	}
	void build(int cur) {
		if (cur >= start)	return;
		int left = cur * 2, right = cur * 2 + 1;
		build(left);
		build(right);
		int i = 0, j = 0;
		while (i < arr[left].size() && j < arr[right].size()) {
			if (arr[left][i] < arr[right][j]) {
				arr[cur].push_back(arr[left][i++]);
			}
			else {
				arr[cur].push_back(arr[right][j++]);
			}
		}
		while (i < arr[left].size()) {
			arr[cur].push_back(arr[left][i++]);
		}
		while (j < arr[right].size()) {
			arr[cur].push_back(arr[right][j++]);
		}
	}

	//ret = position..
	int range(int left, int right, int key) {
		return range(left, right, key, 1, 0, start);
	}

	int my_lower_bound(vector<int>& vec, int key) {
		int min_count = -1;
		int left = -1, right = vec.size();
		while (left < right) {
			int mid = (left + right) / 2;
			if (vec[mid] <= key) {
				min_count = mid;
				left = mid + 1;
			}
			else {
				right = mid - 1;
			}
		}
		return min_count + 1;
	}
    /*
    int my_lower_bound(vector<int>& vec, int key) {
		int min_count = -1;
		int left = 0, right = vec.size() - 1;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (vec[mid] <= key) {
				min_count = mid;
				left = mid + 1;
			}
			else {
				right = mid - 1;
			}
		}
		return min_count + 1;
	}
    */

	int range(int left, int right, int key, int node, int node_left, int node_right) {
		if (node_right <= left || right <= node_left)	return 0;
		if (left <= node_left && node_right <= right) {
			return my_lower_bound(arr[node], key);
		}
		int mid = (node_left + node_right) / 2;
		return range(left, right, key, node * 2, node_left, mid) + range(left, right, key, node * 2 + 1, mid, node_right);
	}
};

int n, m;

int main()
{
	scanf("%d %d", &n, &m);
	SegTree ST(n);
	int v;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &v);
		ST.add(i, v);
	}
	ST.build(1);

	int a, b, c;
	while (m--) {
		scanf("%d %d %d", &a, &b, &c);
		--a;

		int left = -1000000001, right = 1000000001, ret = 0;
		while (left <= right) {
			int mid = (left + right) / 2;
			int min_count = ST.range(a, b, mid);

			if (min_count < c) {
				left = mid + 1;
			}
			else if(min_count >= c) {
				right = mid - 1;
				ret = mid;
			}
		}

		printf("%d\n", ret);
	}

	return 0;
}

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

문제

문제

출처

ICPC

코드 질문있어요;

na982 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말