Submission

(PPPPP)(PPPPPPPPPPPPPPP)

Score: 100

User: hmmm

Problemset: Nostalgia v2

Language: cpp

Time: 0.028 second

Submitted On: 2025-01-26 13:33:32

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N*2],st[4*N*2];

inline void bu(int i,int l,int r){
  if(l==r){
    st[i]=a[l];
  }
  else{
    int mid=(l+r)/2;
    bu(i*2,l,mid);
    bu(i*2+1,mid+1,r);
    st[i]=min(st[i*2],st[i*2+1]);
  }
}

inline int qur(int i,int l,int r,int ql,int qr){
  if(ql>r || qr<l) return INT_MAX;
  if(ql<=l && r<=qr) return st[i];
  else{
    int mid=(l+r)/2;
    return min(qur(i*2,l,mid,ql,qr),qur(i*2+1,mid+1,r,ql,qr));
  }
}

int  main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n;
  cin >> n;
  for(int i=1;i<=n;i++) cin >> a[i];
  for(int i=1;i<=n;i++){
    int x;
    cin >> x;
    a[i]=x-a[i];
//    a[i]+=a[i-1];
//    cout << a[i] << ' ';
  }
  for(int i=1;i<=n;i++){
    a[i+n]=a[i];
  }
  for(int i=1;i<=2*n;i++){
  	a[i]+=a[i-1];
//  	cout << a[i] << ' ';
  }
  int ans=0;
  bu(1,1,2*n);
  for(int i=1;i<=n;i++){
    if(qur(1,1,2*n,i,i+n-1)>=a[i-1]) ans++;
//  	cout << qur(1,1,2*n,i,i+n-2) << ' ' << a[i]<< "\n";
  }
  cout << ans;
}
/*
4 7 5 6
6 4 7 5
  
2 -3 2 -1
  
2 -1 1   0 | 2 -1 1 0     >0
  -3 -1 -2   0              >2
      2  1   3  0          >-1 /
*/