Niuke small Bai monthly race 52 D ring insectivorous (feet +st table)

Sign in — major IT Written interview preparation platform _ Cattle from Niuke.com is the magic weapon of Internet Job Hunting ,C++、Java、 front end 、 product 、 Operational skills learning / Test preparation / Job search question bank , Online Baidu Alibaba Tencent Netease and other Internet famous enterprises written interview simulation test practice , Discuss the classic test questions with Niu Ren , Improve your technical ability in an all-round way https://ac.nowcoder.com/acm/contest/11229/D Obviously, the title description is a ring , So the array is doubled , Then take the interval through the double pointer ruler , use st The table shows that the range of pretreated cream is the largest , When taking a ruler, you need to pay attention to the boundary ,r-l Need to be less than or equal to n, Otherwise, you will eat air and make the answer wrong .

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define lowbit(x) ((x)&(-x))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
const int MAXN=1e6+5;
const int INF=0x3f3f3f3f;
const ll NNF=0x3f3f3f3f3f3f3f3f;


int n;
ll s;
ll a[MAXN];
ll st[MAXN][24];

ll query(int x,int y){
	int s=log2(y-x+1);
	return max(st[x][s],st[y-(1<<s)+1][s]);
}

void solve(){
	scanf("%d %lld",&n,&s);
	for(int i=1;i<=n;i++) scanf("%lld",a+i);
	for(int i=1;i<=n;i++) scanf("%lld",&st[i][0]);
	for(int i=n+1;i<=2*n;i++){
		a[i]=a[i-n];
//		b[i]=b[i-n];
		st[i][0]=st[i-n][0];
	}
	for(int i=1;i<=23;i++){
		for(int j=1;j+(1<<i)-1<=2*n;j++){
			st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
		}
	}
	int l,r;
	l=r=1;
	ll sum=0;
//	int mx=0;
	ll ans=INF;
	while(l<=r){
		while(r<=2*n&&sum<s){
//			mx=max(mx,a[r]);
			sum+=a[r++];
		}
		while(r-l>n){
			sum-=a[l++];
		}
		if(sum>=s){
			ll mx=query(l,r-1);
			ans=min(ans,mx);
		}else if(r>2*n) break;
		if(l<=r){
			sum-=a[l++];
		}
	}
	if(ans==INF) printf("-1");
	else printf("%lld",ans);
}


int main(){
	solve();
	return 0;
}