思路:用线段树维护最小值,用双指针法找合法区间并与当前答案取min,但wa了4个点qwq
代码:
#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define of(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
const int inf=0x3f3f3f3f;
const ll INF=9e18;
const int mod=-1;//lL?
const int Maxn=1e5+10;
ll f[Maxn],s[Maxn],tree[Maxn<<2];
int n,m;
void build(int L,int R,int p)
{
if(L==R) {tree[p]=s[L]; return ;}
ll mid=L+R>>1;
build(L,mid,p<<1); build(mid+1,R,p<<1|1);
tree[p]=std::max(tree[p<<1],tree[p<<1|1]);
}
ll query(int L,int R,int p,int t_l,int t_r)
{
if(t_l<=L&&R<=t_r) return tree[p];
ll mid=L+R>>1;
ll ans=-INF;
if(t_l<=mid) ans=std::max(ans,query(L,mid,p<<1,t_l,t_r));
if(t_r>mid) ans=std::max(ans,query(mid+1,R,p<<1|1,t_l,t_r));
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
fo(i,1,n) scanf("%lld%lld",&f[i],&s[i]);
build(1,n,1);
int pos1,pos2; pos1=pos2=1;
ll cnt=0,ans=INF;
while(pos2<=n)
{
while(pos2<=n&&cnt<m) cnt+=f[pos2++];
if(cnt<m) break;
if(cnt>=m) ans=std::min(ans,query(1,n,1,pos1,pos2));
cnt-=f[pos1++];
}
printf("%lld\n",ans);
return 0;
}
/*
in1:
out1:
*/