BOJ 20654 음료수는 사드세요 제발

문제 링크입니다.

문제 요약

리터 당 가격과 맛, 사용 가능한 최대 양이 정해져 있는 $N$개의 액체가 주어집니다. 예산 $g_i$ 내로 요구량 $L_i$ 이상의 음료를 최대한 맛있게 제작하는 쿼리들을 처리하세요. 음료의 맛은 들어간 액체들의 맛 중 최솟값으로 정해집니다.

풀이

음료의 맛에 대한 이분 탐색을 수행하면 하나의 쿼리를 쉽게 해결할 수 있습니다. 기준 맛 이상의 액체만 모은 뒤 가성비 좋은 액체부터 음료에 넣으면 됩니다.

이 과정에서 이분 탐색의 한 스텝마다 모든 액체를 맛 기준으로 정렬했다 가성비 기준으로 정렬했다 하는 과정이 필요합니다. 운 나쁘면 스텝 당 ${\cal O}(N \lg N)$의 시간이 걸릴 수도 있다는 거죠. 그래서 쿼리들을 독립적으로 이분 탐색하기에는 시간이 모자랍니다.

상황을 타개하기 위해 모든 쿼리에 대한 이분 탐색을 병렬로 처리합니다. 기본적으로 각 스텝마다 액체는 맛이 큰 순으로 사용 가능한 액체에 추가하며, 각 쿼리에 할당된 맛의 기준에 맞게 액체가 모였을 때마다 해당 쿼리에서 요구하는 음료 양을 제작했을 때의 가격이 예산 안으로 들어오는지 확인하면 됩니다.

가성비 순으로 요구량을 충족하는 지 확인하기 위해, 가성비 구간에 대한 액체의 총량과 총 가격을 관리하는 세그먼트 트리를 활용합니다. 액체를 추가하는 것과 앞에서부터 요구량만큼 액체를 모았을 때의 총 가격 모두 ${\cal O}(\lg N)$ 쯤해서 계산할 수 있습니다.

따라서 전체 문제를 ${\cal O}(N \lg ^2 N)$에 해결할 수 있습니다. 사실 뭐는 $N$이고 뭐는 $p$고 한데 어차피 제한이 똑같으니 넘어갑시다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

pll operator+ (pll a, pll b){return {a.first+b.first, a.second+b.second};}
void operator+= (pll& a, pll b){a = a+b; return;}

pll tree[404040];

void upd(int now, int l, int r, int i, pll v){
	if(l == r){tree[now] = v; return;}
	int mid = l+r>>1;
	if(i <= mid) upd(now<<1, l, mid, i, v);
	else upd(now<<1|1, mid+1, r, i, v);
	tree[now] = tree[now<<1]+tree[now<<1|1];
}

pll qry(int now, int l, int r, ll v){
	if(v >= tree[now].first) return {v-tree[now].first, tree[now].second};
	if(l == r) return {0, tree[now].second/tree[now].first*v};
	int mid = l+r>>1;
	pll ret = qry(now<<1, l, mid, v);
	if(ret.first){
		pll ret2 = qry(now<<1|1, mid+1, r, ret.first);
		ret.first = ret2.first; ret.second += ret2.second;
	} 
	return ret;
}

struct drink{
	ll d, p, l; int pidx;
} d[101010];

struct query{
	ll g, L; int l, r; int idx;
} q[101010];

int n, m;

void solve(){
	memset(tree, 0, sizeof(tree));
	sort(q+1, q+m+1, [&](query& a, query& b){
		return (a.l+a.r>>1) > (b.l+b.r>>1);
	});
	int di = 1;
	for(int qi = 1; qi <= m; qi++){
		if(q[qi].l == q[qi].r) continue;
		int mid = (q[qi].l+q[qi].r>>1)+1;
		while(di <= n && d[di].d >= mid){upd(1, 1, n, d[di].pidx, {d[di].l, d[di].p*d[di].l}); di++;}
		pll ret = qry(1, 1, n, q[qi].L);
		if(ret.first || ret.second > q[qi].g) q[qi].r = mid-1;
		else q[qi].l = mid;
	}
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m; for(int i = 1; i <= n; i++) cin >> d[i].d >> d[i].p >> d[i].l;
	sort(d+1, d+n+1, [&](drink& a, drink& b){
		return a.p < b.p;
	}); for(int i = 1; i <= n; i++) d[i].pidx = i;
	sort(d+1, d+n+1, [&](drink& a, drink& b){
		return a.d > b.d;
	});
	for(int i = 1; i <= m; i++){
		cin >> q[i].g >> q[i].L;
		q[i].l = -1; q[i].r = 100000; q[i].idx = i;
	}
	for(int i = 0; i < 17; i++) solve();
	sort(q+1, q+m+1, [&](query& a, query& b){
		return a.idx < b.idx;
	});
	for(int i = 1; i <= m; i++) cout << q[i].r << '\n';
}