취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 20654번 문제인 음료수는 사드세요 제발이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/20654 

문제에서 주어지는 각 사람의 g, L값에 따라, 이 사람이 맛이 K 이상인 음료를 살 수 있을지를 결정할 수 있다면 해당 쿼리의 답은 그러한 결정을 약 (lg100000)번 하며 맛의 범위를 이진탐색을 통해 좁히는 것으로 구해낼 수 있을 것이다.

맛이 K 이상인 음료를 살 수 있을지 여부는 맛이 K 이상인 모든 음료들을 저렴한 순으로 구입을 시도하는 것으로 알아낼 수 있다. 이는 arr[i]를 (맛이 k 이상인 음료들 중) 가격이 i인 음료의 양으로 정의할 때 arr[i]를 이용한 구간 음료의 양의 합, 구간 음료의 값의 합을 관리하는 세그먼트트리를 만들어 해결할 수 있다.

"세그먼트트리를 맛있는 음료서부터 순서대로 채워나가면서 각 쿼리별 mid값과 맞아떨어질 때 쿼리별 이진탐색을 한 단계씩 진행하는 것"을 약 (lg100000)회 진행하는 것으로 이 문제를 해결할 수 있다. 이와 같이 쿼리들의 답을 구해나가는 이진탐색의 단계를 하나씩 함께 진행해나가는 오프라인 문제 해결 전략을 병렬 이진 탐색(Parallel Binary Search)이라 부른다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

struct drink {
	int d, p, l;
	drink() {};
	drink(int d, int p, int l) {
		this->d = d, this->p = p, this->l = l;
	}
};

bool dcomp(drink& d1, drink& d2) {
	return d1.d > d2.d;
}

struct query {
	int idx;
	int low, high, mid;
	ll P, L;
	query() {};
	query(int idx, int low, int high, ll P, ll L) {
		this->idx = idx, this->low = low, this->high = high, this->mid = (high + low) / 2 + 1, this->P = P, this->L = L;
	}
};

bool qcomp(query& q1, query& q2) {
	return q1.mid > q2.mid;
}

bool qcomp2(query& q1, query& q2) {
	return q1.idx < q2.idx;
}

int N, M;
ll seg[262145][2]; // {리터합, 가격합}
drink drinks[100000];
query queries[100000];

void upd(int L, int R, int qI, ll qVal, int sI) {
	if (qI < L || R < qI) return;
	if (L == R) {
		seg[sI][0] += qVal, seg[sI][1] += qVal * L;
		return;
	}
	upd(L, (L + R) / 2, qI, qVal, sI * 2), upd((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1);
	seg[sI][0] = seg[sI * 2][0] + seg[sI * 2 + 1][0], seg[sI][1] = seg[sI * 2][1] + seg[sI * 2 + 1][1];
}

ll qry(ll qVal) { // qVal:리터
	if (seg[1][0] < qVal) return 1000000000000000001LL;
	ll ret = 0;
	int L = 1, R = 100000, sI = 1;
	while (L < R) {
		if (seg[sI * 2][0] < qVal) {
			qVal -= seg[sI * 2][0];
			ret += seg[sI * 2][1];
			L = (L + R) / 2 + 1;
			sI = sI * 2 + 1;
		}
		else {
			R = (L + R) / 2;
			sI = sI * 2;
		}
	}
	return ret + qVal * L;
}

void BS() {
	for (int i = 0; i < 262145; i++) seg[i][0] = seg[i][1] = 0;
	sort(queries, queries + M, qcomp);

	int di = 0, qi = 0;
	while (di < N && qi < M) {
		if (drinks[di].d >= queries[qi].mid) {
			upd(1, 100000, drinks[di].p, drinks[di].l, 1);
			di++;
		}
		else {
			if (queries[qi].low < queries[qi].high) {
				ll tmp = qry(queries[qi].L);
				if (queries[qi].P < tmp) queries[qi].high = queries[qi].mid - 1;
				else queries[qi].low = queries[qi].mid;
				queries[qi].mid = (queries[qi].low + queries[qi].high) / 2 + 1;
			}
			qi++;
		}
	}
	while (qi < M) {
		if (queries[qi].low < queries[qi].high) {
			ll tmp = qry(queries[qi].L);
			if (queries[qi].P < tmp) queries[qi].high = queries[qi].mid - 1;
			else queries[qi].low = queries[qi].mid;
			queries[qi].mid = (queries[qi].low + queries[qi].high) / 2 + 1;
		}
		qi++;
	}
}

void PBS() {
	for (int i = 0; i < 17; i++) {
		BS();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int d, p, l; cin >> d >> p >> l;
		drinks[i] = drink(d, p, l);
	}
	sort(drinks, drinks + N, dcomp);

	for (int i = 0; i < M; i++) {
		ll P, L; cin >> P >> L;
		queries[i] = query(i, 0, 100000, P, L);
	}

	PBS();

	sort(queries, queries + N, qcomp2);

	for (int i = 0; i < M; i++) {
		if (queries[i].low) cout << queries[i].low << '\n';
		else cout << -1 << '\n';
	}
}