fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std; 
  4.  
  5. typedef long long ll; 
  6. typedef pair<int, int> ii; 
  7.  
  8. const ll LINF = 1e18; 
  9. const int INF = 1e9;
  10.  
  11. // - Ở bài này các em cũng cố gắng nghĩ ra thuật O(q * n^3) sau đó cố gắng tối ưu xuống O(q * n^2)
  12. // - Sau khi đã có thuật O(q * n^2) thì ta có thể chọn tối ưu tiếp theo 2 hướng là Prefix Sum 2D hoặc DP Range
  13. // (Tham khảo sol bài: H. Queries for Number of Palindromes)
  14. const int N = 5e3 + 5; 
  15. const int MAX_A = 1e6; 
  16. const int BASE = 1e6; 
  17.  
  18. int n, q; 
  19. int a[N]; 
  20. ll ans[N][N]; // ans[l][r] = Đáp án của đoạn [l, r]
  21. int cnt[MAX_A + BASE + 5];
  22.  
  23. int main() {
  24. 	ios::sync_with_stdio(false); 
  25. 	cin.tie(nullptr); 
  26. 	cin >> n >> q; 
  27. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  28.  
  29. 	//     a[i] + a[j] + a[k] = 0
  30. 	// <=> a[j] = -(a[i] + a[k])
  31. 	for (int i = 1; i + 1 <= n; i++) {
  32. 		for (int k = i + 1; k <= n; k++) {
  33. 			int sum = a[i] + a[k]; 
  34. 			if (-MAX_A <= sum && sum <= MAX_A) ans[i][k] = cnt[-sum + BASE]; 
  35. 			++cnt[a[k] + BASE]; 
  36. 		}
  37. 		for (int k = i + 1; k <= n; k++) --cnt[a[k] + BASE]; 
  38. 	}
  39.  
  40. 	for (int l = n - 2; l >= 1; l--) {
  41. 		for (int r = l + 2; r <= n; r++) ans[l][r] += ans[l + 1][r] + ans[l][r - 1] - ans[l + 1][r - 1]; 
  42. 	}
  43.  
  44. 	while (q--) {
  45. 		int l, r; 
  46. 		cin >> l >> r; 
  47. 		cout << ans[l][r] << '\n';
  48. 	}
  49. }
  50.  
Success #stdin #stdout 0s 5524KB
comments (?)
stdin
copy 
7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7
stdout
copy 
2
1
4
https://ideone.com/w1MYhv
language:
C++14 (gcc 8.3)
created:
19 days 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!