两只老哥求卡常
查看原帖
两只老哥求卡常
667250
Xiphi楼主2023/12/4 20:12
#include<bits/stdc++.h>
using namespace std;
#define BF_SIZE 100000
bool IOerr = 0;
inline char nc() {
	static char buf[BF_SIZE], * p1 = buf + BF_SIZE, * pend = buf + BF_SIZE;
	if (p1 == pend) {
		p1 = buf;
		pend = buf + fread(buf, 1, BF_SIZE, stdin);
		if (pend == p1) { IOerr = 1; return -1; }
	}
	return *p1++;
}
inline bool bla(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
inline long long read()
{
	char ch;
	long long x = 0;
	while (bla(ch = nc()));
	if (IOerr) { return 0; }
	for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = (x << 1) + (x << 3) + ch - '0');
	return x;
}
long long n,s;
long long sum[200005],a[200005];
int b[200005];
int L[200005],R[200005];
long long st[25][200005];
#define ll long long
ll query(int l,int r){
	int len=log2(r-l+1);
	return min(st[len][l],st[len][r-(1<<len)+1]);
}
signed main(){
	n=read(),s=read();
	for(int i=1;i<=n;++i) a[i]=read(),st[0][i]=a[i];
	for(int i=1;i<=n;++i) b[i]=read(),sum[i]=sum[i-1]+b[i];
	for(int i=1;i<=20;++i){
		for(int j=1;(j+(1<<i)-1)<=n;++j){
			st[i][j]=min(st[i-1][j],st[i-1][(1<<(i-1))+j]);
		}
	}
	for(int i=1;i<=n;++i){
        int l=1,r=i;
        while(l<=r){
            int mid=l+r>>1;
            if(query(mid,i)==a[i]){
                r=mid-1;L[i]=mid;
            }else l=mid+1;
        }
        l=i,r=n;
        while(l<=r){
            int mid=l+r>>1;
            if(query(i,mid)==a[i]){
                l=mid+1;R[i]=mid;
            }else r=mid-1;
        }
    }
    long long ans=0;
    for(int i=1;i<=n;++i){
        if(R[i]-i+1>i-L[i]+1){
            for(int j=L[i];j<=i;++j){
            	int l=i,r=R[i],t=-1;
            	ll B=s-a[i];
            	while(l<=r){
            		int mid=l+r>>1;
            		if((sum[mid]-sum[j-1])<=B){
            			t=mid,l=mid+1;
					}else r=mid-1;
				}
				if(t!=-1) ans+=(t-i+1);
            }
        }else{
            for(int j=i;j<=R[i];++j){
            	int l=L[i],r=i,t=-1;
            	ll B=s-a[i];
            	while(l<=r){
            		int mid=l+r>>1;
            		if((sum[j]-sum[mid-1])<=B){
            			t=mid,r=mid-1;
					}else l=mid+1;
				}
				if(t!=-1) ans+=(i-t+1);
            }
        }
	}
    cout<<ans;
    return 0;
}
2023/12/4 20:12
加载中...