bzoj5142 [Usaco2017 Dec]Haybale Feast

bzoj5142 [Usaco2017 Dec]Haybale Feast

​​ Description

Farmer John is preparing a delicious meal for his cows! In his barn, he has NN haybales (1≤N≤100,0 00). The iith haybale has a certain flavor Fi (1≤Fi≤10^9) and a certain spiciness Si(1≤Si≤10^9). The meal will consist of a single course, being a contiguous interval containing one or more consecu tive haybales (Farmer John cannot change the order of the haybales). The total flavor of the meal is the sum of the flavors in the interval. The spiciness of the meal is the maximum spiciness of all h aybales in the interval.Farmer John would like to determine the minimum spiciness his single-course meal could achieve, given that it must have a total flavor of at least MM (1≤M≤10^18). 给长度为n<=1e5的两个序列f[], s[] <= 1e9和一个long long M。 如果[1, n] 的一个子区间[a, b]满足 f[a]+f[a+1]+..+f[b] >= M， 我们就称[a, b]合法 ，一个合法区间[a, b]的值为max(s[a], s[a+1], …, s[b])。 让你求出可能的合法区间最小值为多少。

Input

The first line contains the integers N and M, the number of haybales and the minimum total flavor the meal must have, respectively. The next N lines describe the N haybales with two integers per line, first the flavor F and then the spiciness S.

Output

Please output the minimum spiciness in a single course meal that satisfies the minimum flavor requirement. There will always be at least one single-course meal that satisfies the flavor requirement.

Sample Input

5 10 4 10 6 15 3 5 4 9 3 6 Sample Output

9 HINT

Source

Gold

自己yy了一个log 的做法 但是写着写着发现是错的 于是自己有个很显然的两个log的做法 按照b排序 然后每次二分出最大值不超过当前b的区间是多大 然后看这个区间能否大于等于m 但是两个Log 这么不优秀还是不写了

于是膜了下icefox巨佬的blog

发现只需要按照b排序 然后查询线段树最大连续子段和即可

#include#include#include#define ll long long#define N 100010#define lc (x<<1)#define rc (x<<1|1)using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S) {T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline ll read(){ ll x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}int n;ll m;struct node1{int a,b,id;}ss[N];struct node{ll mxs,ls,rs;bool cov;}tree[N<<2];inline bool cmp(const node1 &a,const node1 &b){return a.b>1; if (p<=mid) insert1(lc,l,mid,p,v);else insert1(rc,mid+1,r,p,v);update(x);}int main(){ freopen("bzoj5142.in","r",stdin); n=read();m=read();ll ans=0; for (int i=1;i<=n;++i) ss[i].a=read(),ss[i].b=read(),ss[i].id=i; sort(ss+1,ss+n+1,cmp); for (int i=1;i<=n;++i){ insert1(1,1,n,ss[i].id,ss[i].a); if (tree[1].mxs>=m) {ans=ss[i].b;break;} }printf("%lld\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。