fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define pb push_back
  6. #define lo long long 
  7. class node{
  8. 	public:
  9. 		node* left,*right;
  10. 		vector<lo>vt;
  11. 		//int val;
  12. 		node()
  13. 		{
  14. 			left=right=NULL;
  15. 		}
  16. 		node(lo x)
  17. 		{
  18. 			left=right=NULL;
  19. 			vt.pb(x);
  20. 		}
  21. };
  22. lo find(vector<lo>vt,lo k)
  23. {
  24. 	return lower_bound(vt.begin(),vt.end(),k)-vt.begin();
  25. }
  26. vector<lo> merge(vector<lo>v1,vector<lo>v2)
  27. {
  28. 	lo i=0,j=0,n=v1.size(),m=v2.size();
  29. 	vector<lo>ans;
  30. 	while(i<n and j<m)
  31. 	{
  32. 		if(v1[i]<=v2[j]){ans.pb(v1[i]);i++;}
  33. 		else{ans.pb(v2[j]);j++;}
  34. 	}
  35. 	while(i<n){ans.pb(v1[i]);i++;}
  36. 	while(j<m){ans.pb(v2[j]);j++;}
  37. 	return ans;
  38. }
  39. node* build(lo l,lo r,lo a[])
  40. {
  41.  
  42. 	if(l==r){return new node(a[l]);}
  43. 	lo mid=l+(r-l)/2;
  44. 	node* root= new node();
  45. 	root->left = build(l,mid,a);
  46. 	root->right = build(mid+1,r,a);
  47. 	//root->val = min(root->right->val,root->left->val);
  48. 	root->vt = merge(root->right->vt,root->left->vt);
  49. 	return root;
  50. }
  51. lo query(node* root,lo l,lo r,lo ll,lo ul,lo k)
  52. {
  53. 	if(l>r){return 0;}
  54. 	if(l>ul or r<ll){return 0;}
  55. 	if(l>=ll and r<=ul){return find(root->vt,k);}
  56. 	lo mid=l+(r-l)/2;
  57. 	lo n1=query(root->left,l,mid,ll,ul,k);
  58. 	lo n2=query(root->right,mid+1,r,ll,ul,k);
  59. 	return n1+n2;
  60. }
  61.  
  62. int main() {
  63. 	ios_base::sync_with_stdio(false); 
  64.     cin.tie(NULL); 
  65. 	lo n,t;
  66. 	cin>>n>>t;
  67. 	lo a[n],p[n],prev=0;
  68. 	for(int i=0;i<n;i++){cin>>a[i];p[i]=a[i]+prev;prev=p[i];}
  69. 	node* root=build(0,n-1,p);
  70. 	lo ans=query(root,0,n-1,0,n-1,t);
  71. 	for(int i=0;i<n;i++)
  72. 	{
  73. 		ans+=query(root,0,n-1,i+1,n-1,t+p[i]);
  74. 	}
  75. 	cout<<ans<<endl;
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 4368KB
comments (?)
stdin
copy 
4 -1
-2 1 -2 3
stdout
copy 
3
https://ideone.com/rKdDMD
language:
C++14 (gcc 8.3)
created:
4 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!