BZOJ5343 [Ctsc2018]混合果汁【二分 + 主席树】

题目链接

题解

明显要二分一下美味度，然后用尽量少的价格去购买饮料，看看能否买到\(L\)升，然后看看能否控制价格在\(g\)内

尽量少的价格，就优先先选完便宜的饮料，由于询问的是一定美味度范围的，主席树上询问即可

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 100005,maxm = 5000005;

const LL INF = 1000000000000000001ll;

inline LL read(){

	LL out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int n,m;

struct node{

	int d,p,l;

}e[maxn];

inline bool operator <(const node& a,const node& b){

	return a.d < b.d;

}

int Maxp;

LL S[maxn],sum[maxm],val[maxm];

int ls[maxm],rs[maxm],cnt,rt[maxn];

void add(int& u,int pre,int l,int r,int pos,int v){

	sum[u = ++cnt] = sum[pre]; val[u] = val[pre];

	ls[u] = ls[pre]; rs[u] = rs[pre];

	val[u] += 1ll * pos * v; sum[u] += v;

	if (l == r) return;

	int mid = l + r >> 1;

	if (mid >= pos) add(ls[u],ls[pre],l,mid,pos,v);

	else add(rs[u],rs[pre],mid + 1,r,pos,v);

}

LL query(int u,int v,int l,int r,LL ml){

	if (!u) return 0;

	if (l == r) return ml * l;

	int mid = l + r >> 1;

	LL t = sum[ls[u]] - sum[ls[v]];

	if (t >= ml) return query(ls[u],ls[v],l,mid,ml);

	return val[ls[u]] - val[ls[v]] + query(rs[u],rs[v],mid + 1,r,ml - t);

}

bool check(int d,LL g,LL L){

	int pre = lower_bound(e + 1,e + 1 + n,(node){d,0,0}) - e - 1;

	if (S[n] - S[pre] < L) return false;

	return query(rt[n],rt[pre],1,Maxp,L) <= g;

}

int main(){

	n = read(); m = read();

	int M = 0;

	REP(i,n){

		e[i].d = read();

		e[i].p = read();

		e[i].l = read();

		M = max(M,e[i].d);

		Maxp = max(Maxp,e[i].p);

	}

	sort(e + 1,e + 1 + n);

	for (int i = 1; i <= n; i++)

		S[i] = S[i - 1] + e[i].l;

	for (int i = 1; i <= n; i++){

		add(rt[i],rt[i - 1],1,Maxp,e[i].p,e[i].l);

	}

	LL g,L;

	while (m--){

		g = read(); L = read();

		int l = 1,r = M,mid;

		while (l < r){

			mid = l + r + 1 >> 1;

			if (check(mid,g,L)) l = mid;

			else r = mid - 1;

		}

		if (check(l,g,L)) printf("%d\n",l);

		else puts("-1");

	}

	return 0;

}

巴特西

BZOJ5343 [Ctsc2018]混合果汁【二分 + 主席树】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ5343 [Ctsc2018]混合果汁 【二分 + 主席树】

题目链接

题解

最新文章

热门文章

BZOJ5343 [Ctsc2018]混合果汁【二分 + 主席树】