fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9. const int N = 1e5 + 5;  
  10. const int M = 2e5 + 5; 
  11.  
  12. int n, L, R; 
  13. int a[N]; 
  14. ll pref[N]; 
  15.  
  16. int ft[M]; 
  17.  
  18. void init() {
  19. 	for (int i = 1; i <= 2 * (n + 1); i++) ft[i] = 0; 
  20. }
  21.  
  22. void update(int i, int val) {
  23. 	for (; i > 0; i -= i & (-i)) ft[i] += val; 
  24. }
  25.  
  26. int getSum(int i) {
  27. 	int ans = 0;  
  28. 	for (; i <= 2 * (n + 1); i += i & (-i)) ans += ft[i]; 
  29. 	return ans; 
  30. }
  31.  
  32. ll countSum(ll X) {
  33. 	//     pref[j] - pref[i] <= X 
  34. 	// <=> pref[i] >= pref[j] - X 
  35.  
  36. 	// nén những giá trị cần thiết
  37. 	vector<ll> vals;  
  38. 	for (int i = 0; i <= n; i++) {
  39. 		vals.push_back(pref[i]); 
  40. 		vals.push_back(pref[i] - X); 
  41. 	}
  42. 	sort(vals.begin(), vals.end());  
  43. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());  
  44.  
  45. 	// (chú ý khởi tạo lại cây BIT)
  46. 	init();   
  47.  
  48. 	ll ans = 0; 
  49. 	for (int j = 0; j <= n; j++) {
  50. 		// giá trị nén của pref[j] - X
  51. 		int val_j = lower_bound(vals.begin(), vals.end(), pref[j] - X) - vals.begin() + 1;
  52. 		ans += getSum(val_j);  
  53.  
  54. 		// giá trị nén của pref[j]
  55. 		val_j = lower_bound(vals.begin(), vals.end(), pref[j]) - vals.begin() + 1; 
  56. 		update(val_j, 1); 
  57. 	}
  58.  
  59. 	return ans; 
  60. }
  61.  
  62. int main() {
  63. 	ios::sync_with_stdio(0); cin.tie(0);  	
  64. 	cin >> n >> L >> R;  
  65. 	for (int i = 1; i <= n; i++) cin >> a[i], pref[i] = pref[i - 1] + a[i]; 
  66.  
  67. 	ll ans = countSum(R) - countSum(L - 1);
  68.  
  69. 	cout << ans << '\n'; 
  70. }
  71.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
4 2 4
1 2 3 4
stdout
copy 
4
https://ideone.com/2CS8w5
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!