fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int M=3e5+10,INF=1e15;
  5. int n,d,a[M],p[M],ans[M];
  6. vector<pair<int,int>>q[M];
  7. struct SG{
  8. 	int s[4*M],m[4*M],lz[4*M];
  9. 	void b(int i,int l,int r){
  10. 		if(l==r){s[i]=m[i]=a[l];return;}
  11. 		int x=(l+r)/2;
  12. 		b(i*2,l,x);b(i*2+1,x+1,r);
  13. 		s[i]=s[i*2]+s[i*2+1];
  14. 		m[i]=min(m[i*2],m[i*2+1]);
  15. 	}
  16. 	void ps(int i,int l,int r){
  17. 		if(!lz[i])return;
  18. 		int x=(l+r)/2,v=lz[i];
  19. 		s[i*2]+=v*(x-l+1);m[i*2]+=v;lz[i*2]+=v;
  20. 		s[i*2+1]+=v*(r-x);m[i*2+1]+=v;lz[i*2+1]+=v;
  21. 		lz[i]=0;
  22. 	}
  23. 	void u(int i,int l,int r,int L,int R,int v){
  24. 		if(r<L||R<l)return;
  25. 		if(L<=l&&r<=R){
  26. 			s[i]+=v*(r-l+1);m[i]+=v;lz[i]+=v;return;
  27. 		}
  28. 		ps(i,l,r);
  29. 		int x=(l+r)/2;
  30. 		u(i*2,l,x,L,R,v);
  31. 		u(i*2+1,x+1,r,L,R,v);
  32. 		s[i]=s[i*2]+s[i*2+1];
  33. 		m[i]=min(m[i*2],m[i*2+1]);
  34. 	}
  35. 	int gs(int i,int l,int r,int L,int R){
  36. 		if(r<L||R<l)return 0;
  37. 		if(L<=l&&r<=R)return s[i];
  38. 		ps(i,l,r);
  39. 		int x=(l+r)/2;
  40. 		return gs(i*2,l,x,L,R)+gs(i*2+1,x+1,r,L,R);
  41. 	}
  42. 	int gm(int i,int l,int r,int L,int R){
  43. 		if(r<L||R<l)return INF;
  44. 		if(L<=l&&r<=R)return m[i];
  45. 		ps(i,l,r);
  46. 		int x=(l+r)/2;
  47. 		return min(gm(i*2,l,x,L,R),gm(i*2+1,x+1,r,L,R));
  48. 	}
  49. }seg;
  50. main(){
  51. 	ios::sync_with_stdio(0);
  52. 	cin.tie(0);
  53. 	cin>>n>>d;
  54. 	for(int i=1;i<=n;i++)cin>>a[i],p[i]=p[i-1]+a[i];
  55. 	seg.b(1,1,n);
  56. 	int Q;cin>>Q;
  57. 	for(int i=1,L,R;i<=Q;i++)cin>>L>>R,q[R].push_back({L,i});
  58. 	vector<pair<int,int>>stk={{-INF,0}};
  59. 	for(int i=1;i<=n;i++){
  60. 		int L=i,v=a[i];
  61. 		while(stk.back().first>v){
  62. 			int c=(stk.back().first-v+d-1)/d;
  63. 			seg.u(1,1,n,stk.back().second,L-1,-c*d);
  64. 			L=stk.back().second;
  65. 			v=seg.gs(1,1,n,L,L);
  66. 			stk.pop_back();
  67. 		}
  68. 		stk.push_back({a[i],L});
  69. 		for(auto [l,id]:q[i]){
  70. 			int sum=seg.gs(1,1,n,l,i);
  71. 			if(seg.gm(1,1,n,l,i)<0)ans[id]=-1;
  72. 			else ans[id]=((p[i]-p[l-1])-sum)/d;
  73. 		}
  74. 	}
  75. 	for(int i=1;i<=Q;i++)cout<<ans[i]<<"\n";
  76. }
Success #stdin #stdout 0.01s 15920KB
comments (?)
stdin
copy 
4 2
3 1 2 1
1
1 3
stdout
copy 
1
https://ideone.com/xrlDUK
language:
C++ (gcc 8.3)
created:
6 days 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!