fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int LL;
  5.  
  6. #define inp_s     ios_base::sync_with_stdio(false)
  7. #define DRT()     int test_case;cin>>test_case;while(test_case--)
  8.  
  9. #define VI        vector<int>
  10. #define VS        vector<string>
  11. #define VLL       vector<LL>
  12. #define PII       pair<int,int>
  13. #define all(c)    c.begin(),c.end()
  14. #define sz(c)     c.size()
  15. #define clr(c)    c.clear()
  16. #define msi       map<string,int>
  17. #define msit      map<string,int>::iterator
  18. #define pb        push_back
  19. #define mp        make_pair
  20.  
  21. #define GI(x)     scanf("%d",&x)
  22.  
  23. #define FOR(i,a,b)      for(int i=a;i<b;i++)
  24. #define RFOR(i,a,b)     for(int i=b-1;i>=a;i--)
  25.  
  26. #define gcd(a,b)  __gcd(a,b)
  27. #define MOD       1000000007
  28. #define EPS       1E-10
  29.  
  30. #define PI  acos(-1)
  31.  
  32. #define endn	"\n"
  33.  
  34. #define CASE(x)   cout << "Case #" << x << ": ";
  35.  
  36. VLL segTree(4000000);
  37. VLL lazy(4000000);
  38. int n;
  39.  
  40. LL query(int idx,int l,int r,int pos)
  41. {
  42. 	if(lazy[pos])
  43. 	{
  44. 		segTree[pos] += (lazy[pos] * (r-l+1));
  45. 		segTree[pos] %= MOD;
  46. 		if(l != r)
  47. 		{
  48. 			lazy[2*pos] += lazy[pos];
  49. 			lazy[2*pos + 1] += lazy[pos];
  50.  
  51. 			lazy[2*pos] %= MOD;
  52. 			lazy[2*pos+1] %= MOD;
  53. 		}
  54. 		lazy[pos] = 0;
  55. 	}
  56. 	if(l > idx || r < idx || l > r) return INT_MIN;
  57. 	if(l == r && r == idx) return segTree[pos];
  58. 	int mid = (l + r)/2;
  59. 	return max( query(idx,l,mid,2*pos) , query(idx,mid+1,r,2*pos+1) );
  60. }
  61.  
  62. LL getVal(int i)
  63. {
  64. 	return query(i,1,n+1,1);
  65. }
  66.  
  67. void range_update(int qLeft,int qRight,LL val,int l,int r,int pos)
  68. {
  69. 	if(lazy[pos])
  70. 	{
  71. 		segTree[pos] += (lazy[pos] * (r-l+1));
  72. 		segTree[pos] %= MOD;
  73. 		if(l != r)
  74. 		{
  75. 			lazy[2*pos] += lazy[pos];
  76. 			lazy[2*pos + 1] += lazy[pos];
  77.  
  78. 			lazy[2*pos] %= MOD;
  79. 			lazy[2*pos+1] %= MOD;
  80. 		}
  81. 		lazy[pos] = 0;
  82. 	}
  83. 	if(l > qRight || r < qLeft || l > r) return ;
  84. 	if(l >= qLeft && r <= qRight)
  85. 	{
  86. 		lazy[pos] += val;
  87. 		lazy[pos] %= MOD;
  88. 		return ;
  89. 	}
  90. 	int mid = (l + r)/2;
  91. 	range_update(qLeft,qRight,val,l,mid,2*pos);
  92. 	range_update(qLeft,qRight,val,mid+1,r,2*pos+1);
  93. }
  94.  
  95. int main()
  96. {
  97. 	int h;
  98. 	cin >> n >> h;
  99. 	VLL arr(n+1);
  100. 	arr[0] = 0;
  101. 	FOR(i,1,n+1) cin >> arr[i];
  102. 	FOR(i,1,n+1) arr[i] = arr[i-1] + arr[i];
  103. 	range_update(1,1,1,1,n+1,1);
  104. 	FOR(i,0,n+1)
  105. 	{
  106. 		int lb = i + 1;
  107. 		int ub = (int)(upper_bound(all(arr) , arr[i] + h) - arr.begin()) - 1;
  108. 		LL val = getVal(i+1);
  109. 		if(lb <= ub)
  110. 		range_update(lb+1,ub+1,val,1,n+1,1);
  111. 	}
  112. 	cout << getVal(n+1) << endl;
  113. 	return 0;
  114. }
Success #stdin #stdout 0.05s 3236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/gnBviP
language:
C++ (gcc 8.3)
created:
9 years 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!