fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. void solve(){
  9. 	int n, m;
  10. 	cin >> n >> m;
  11.  
  12. 	vector<int> a(n);
  13. 	vector<int> b(m);
  14.  
  15. 	for(int i = 0; i < n; i++){
  16. 		cin >> a[i];
  17. 	}
  18.  
  19. 	for(int i = 0; i < m; i++){
  20. 		cin >> b[i];
  21. 	}
  22. 	int r = a[0];
  23. 	sort(a.begin(), a.end());
  24.  
  25. 	sort(b.begin(), b.end());
  26. 	vector<int> s;
  27. 	int cnt = 0;
  28. 	for(int i = 0; i < m; i++){
  29. 		if(b[i] <= r)cnt++;
  30. 		else if(b[i] > a[n - 1])cnt++;
  31. 		else {
  32. 			auto x = a.end() - lower_bound(a.begin(), a.end(), b[i]);
  33. 			s.push_back(x + 1);
  34. 		}
  35. 	}
  36.  
  37. 	sort(s.begin(), s.end());
  38. 	int p = s.size();
  39.  
  40. 	for(int i = 1; i <= m; i++){
  41. 		int tot = (m / i) * i;
  42.  
  43. 		if(tot <= cnt){
  44. 			cout << m / i << " ";
  45. 			continue;
  46. 		}
  47.  
  48. 		int gone_con = cnt / i;
  49.  
  50. 		ll sum = 0;
  51.  
  52. 		ll idx = (p - 1) - (m % i);
  53. 		while(idx >= 0){
  54. 			sum += s[idx];
  55. 			idx -= i;
  56. 		}
  57. 		cout << sum + gone_con << " ";
  58.  
  59. 	}
  60. 	cout << "\n";
  61. }
  62.  
  63. int main(){
  64. 	ios_base::sync_with_stdio(false);
  65. 	cin.tie(nullptr);
  66.  
  67. 	int t = 1;
  68. 	cin >> t;
  69.  
  70. 	for(int i = 1; i <= t; i++){
  71. 		solve();
  72. 	}
  73. 	return 0;
  74. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
4
4 4
4 3 7 5
2 5 4 6
5 5
5 0 4 8 6
1 3 9 2 7
6 7
1 1 4 5 1 4
1 9 1 9 8 1 0
7 6
1 9 1 9 8 1 0
1 1 4 5 1 4
stdout
copy 
7 4 2 3 
6 2 1 1 2 
7 3 2 1 1 1 1 
15 9 5 4 4 4
https://ideone.com/nApqJg
language:
C++14 (gcc 8.3)
created:
1 day 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!