fork download
copy 
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("Ofast")
  3. using namespace std;
  4. typedef long long ll;
  5. const int N=1000005;
  6. ll a[N],b[N],c[N],n,E;
  7. void compress(){
  8. 	vector<ll>s;
  9. 	s.reserve(n+1);
  10. 	for(int i=0;i<=n;i++)s.push_back(c[i]);
  11. 	sort(s.begin(),s.end());
  12. 	s.erase(unique(s.begin(),s.end()),s.end());
  13. 	for(int i=0;i<=n;i++)c[i]=lower_bound(s.begin(),s.end(),c[i])-s.begin()+1;
  14. }
  15. int sp[20][N];
  16. int MAX(int l,int r){
  17. 	if(l>r)return 0;
  18. 	int pw=__lg(r-l+1);
  19. 	return max(sp[pw][l],sp[pw][r-(1<<pw)+1]);
  20. }
  21. int tree[N+1];
  22. void add(int i,int val){
  23. 	for(;i<=N;i+=i&-i)tree[i]+=val;
  24. }
  25. int query(int i){
  26. 	int res=0;
  27. 	for(;i>=1;i-=i&-i)res+=tree[i];
  28. 	return res;
  29. }
  30. int query(int l,int r){
  31. 	return query(r)-query(l-1);
  32. }
  33. int main()
  34. {
  35. 	ios_base::sync_with_stdio(0);
  36. 	cin.tie(0);
  37. 	cout.tie(0);
  38. 	cin>>n>>E;
  39. 	for(int i=1;i<=n;i++)cin>>a[i];
  40. 	for(int i=1;i<=n;i++)cin>>b[i];
  41. 	for(int i=1;i<=n;i++)c[i]=(b[i]-a[i])+c[i-1];
  42. 	compress();
  43. 	for(int i=1;i<=n;i++)sp[0][i]=min(a[i],b[i]);
  44. 	for(int i=1;(1<<i)<=n;i++){
  45. 		for(int j=1;j+(1<<i)-1<=n;j++){
  46. 			sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1<<(i-1))]);
  47. 		}
  48. 	}
  49. 	ll ans=0;
  50. 	for(int l=1,r=1;l<=n;l++){
  51. 		while(r<=n&&MAX(l,r)<=E-max(a[r]-b[r],0LL)){
  52. 			add(c[r],1);
  53. 			E-=max(a[r]-b[r],0LL);
  54. 			r++;
  55. 		}
  56. 		ans+=query(c[l-1],N);
  57. 		if(l==r)r++;
  58. 		else add(c[l],-1),E+=max(a[l]-b[l],0LL);
  59. 	}
  60. 	cout<<ans;
  61. 	return 0;
  62. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JhUztQ
language:
C++14 (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!