fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #define int long long
  5. #define pb push_back
  6. #define eb emplace_back
  7. #define mp make_pair
  8. #define mt make_tuple
  9. #define ld(a) while(a--)
  10. #define tci(v,i) for(auto i=v.begin();i!=v.end();i++)
  11. #define tcf(v,i) for(auto i : v)
  12. #define all(v) v.begin(),v.end()
  13. #define rep(i,start,lim) for(long long (i)=(start);i<(lim);i++)
  14. #define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  15. #define osit ostream_iterator
  16. #define INF 		0x3f3f3f3f
  17. #define LLINF       1000111000111000111LL
  18. #define PI 			3.14159265358979323
  19. #define endl '\n'
  20. #define trace1(x)                cerr<<#x<<": "<<x<<endl
  21. #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  22. #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  23. #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  24. #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  25. #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  26. const int N=1000006;
  27. using namespace std;
  28. using namespace __gnu_pbds; // inc this
  29.  
  30. typedef vector<int> vi;
  31. typedef vector<vi> vvi;
  32. typedef long long ll;
  33. typedef vector<long long> vll;
  34. typedef vector<vll> vvll;
  35. typedef long double ld;
  36. typedef pair<int,int> ii;
  37. typedef vector<ii> vii;
  38. typedef vector<vii> vvii;
  39. typedef tuple<int,int,int> iii;
  40. typedef set<int> si;
  41. typedef complex<double> pnt;
  42. typedef vector<pnt> vpnt;
  43. typedef priority_queue<ii,vii,greater<ii> > spq;
  44. const ll MOD=1000000007LL;
  45. template<typename T> T gcd(T a,T b){if(a==0) return b; return gcd(b%a,a);}
  46. template<typename T> T power(T x,T y,ll m=MOD){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}
  47. typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> order_set;
  48. order_set x;
  49. int T;
  50. int32_t main(){
  51. 	sync;
  52. 	int n,t; cin>>n>>t;
  53. 	vi v(n); vi p(n);
  54. 	rep(i,0,n) cin>>v[i];
  55. 	p[0]=v[0];
  56. 	rep(i,1,n) p[i]=v[i]+p[i-1];
  57. 	// set<int> s; 
  58. 	int ans=0;
  59. 	//map<int,int> m;
  60. 	x.insert({0,T++});
  61. 	rep(i,0,n){
  62. 		// if(v[i]>=t) ++ans;
  63. 		int req=p[i]-t;
  64. 		ans+=x.order_of_key({req+1,0});
  65. 		x.insert({p[i],T++});
  66. 	          trace4(i,p[i],req,x.order_of_key({req+1,0}));
  67. 	}
  68. 	 ans=(n*(n+1))/2-ans;
  69. 	 cout<<ans;
  70. }
Success #stdin #stdout #stderr 0s 15248KB
comments (?)
stdin
copy 
5 4 
5 -1 3 4 -1
stdout
copy 
5
stderr
copy 
i: 0 | p[i]: 5 | req: 1 | x.order_of_key({req+1,0}): 1
i: 1 | p[i]: 4 | req: 0 | x.order_of_key({req+1,0}): 1
i: 2 | p[i]: 7 | req: 3 | x.order_of_key({req+1,0}): 1
i: 3 | p[i]: 11 | req: 7 | x.order_of_key({req+1,0}): 4
i: 4 | p[i]: 10 | req: 6 | x.order_of_key({req+1,0}): 3
https://ideone.com/Y45eW0
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 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!