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.  
  10. const int N = 2e5 + 5; 
  11.  
  12. int n;  
  13. int x[N], p[N]; 
  14.  
  15. int ft[N]; 
  16.  
  17. void update(int i, int val) {
  18. 	for (; i <= n; i += i & (-i)) ft[i] += val; 
  19. }
  20.  
  21. int getSum(int i) {
  22. 	int ans = 0; 
  23. 	for (; i > 0; i -= i & (-i)) ans += ft[i]; 
  24. 	return ans; 
  25. }
  26.  
  27. int getIndex(int i) {
  28. 	int l = 1, r = n, ans = -1; 
  29. 	// tìm x nhỏ nhất sao cho getSum(x) >= i
  30. 	while (l <= r) {
  31. 		int mid = (l + r) >> 1; 
  32. 		if (getSum(mid) >= i) {
  33. 			ans = mid;   
  34. 			r = mid - 1; 
  35. 		}
  36. 		else {
  37. 			l = mid + 1; 
  38. 		}
  39. 	}
  40. 	return ans; 
  41. }
  42.  
  43. int main() {
  44. 	ios::sync_with_stdio(0); cin.tie(0);  	
  45. 	cin >> n; 
  46. 	for (int i = 1; i <= n; i++) cin >> x[i]; 
  47. 	for (int i = 1; i <= n; i++) cin >> p[i]; 
  48.  
  49. 	for (int i = 1; i <= n; i++) update(i, 1); 
  50.  
  51. 	for (int i = 1; i <= n; i++) {
  52. 		// tìm chỉ số thực tế của p[i] trong mảng x hiện tại
  53. 		int j = getIndex(p[i]); 
  54. 		cout << x[j] << ' ';
  55.  
  56. 		// xoá x[j] khỏi mảng 
  57. 		update(j, -1); 
  58. 	}
  59. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
5
2 6 1 4 2
3 1 3 1 1
stdout
copy 
1 2 2 6 4
https://ideone.com/PV9Mut
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!