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. const int N = 1e5 + 5; 
  12.  
  13. int n, m, q; 
  14. int b[N], g[N]; 
  15.  
  16. void solve() {
  17. 	cin >> n >> m; 
  18. 	for (int i = 1; i <= n; i++) cin >> b[i]; 
  19. 	for (int i = 1; i <= m; i++) cin >> g[i];
  20.  
  21. 	sort(b + 1, b + n + 1); 
  22. 	sort(g + 1, g + m + 1); 
  23.  
  24. 	cin >> q;
  25. 	while (q--) {
  26. 		ll x, y;
  27. 		cin >> x >> y; 
  28.  
  29. 		ll ans = 0;   
  30. 		for (int i = 1, l = m + 1, r = m; i <= n; i++) {
  31. 			// r là vị trí xa nhất thoả mãn b[i] * g[r] <= y 
  32. 			while (r > 0 && 1ll * b[i] * g[r] > y) r--; 
  33. 			// l là vị trí nhỏ nhất thoả mãn b[i] * g[l] >= x
  34. 			while (l - 1 > 0 && 1ll * b[i] * g[l - 1] >= x) l--; 
  35. 			ans += r - l + 1; 
  36. 		}
  37.  
  38. 		cout << ans << '\n'; 
  39. 	} 
  40. }
  41.  
  42. int main() {
  43. 	ios::sync_with_stdio(false); 
  44. 	cin.tie(nullptr); 
  45. 	int tt; 
  46. 	cin >> tt; 
  47. 	while (tt--) {
  48. 		solve(); 
  49. 	}
  50. }
  51.  
Success #stdin #stdout 0s 5264KB
comments (?)
stdin
copy 
1
4 3
5 1 2 1
6 2 3
3
1 5
6 6
2 30
stdout
copy 
5
3
12
https://ideone.com/Jx5IIJ
language:
C++14 (gcc 8.3)
created:
346 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!