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, m;  
  13. int h[N], r[N];
  14.  
  15. int seg[4 * N]; 
  16.  
  17. void build(int id, int l, int r) {
  18. 	if (l == r) {
  19. 		seg[id] = h[l]; 
  20. 		return; 
  21. 	}
  22. 	int mid = (l + r) >> 1; 
  23. 	build(id << 1, l, mid); 
  24. 	build(id << 1 | 1, mid + 1, r); 
  25. 	seg[id] = max(seg[id << 1], seg[id << 1 | 1]); 
  26. }
  27.  
  28. void update(int id, int l, int r, int pos, int val) {
  29. 	if (l > pos || r < pos) return; 
  30.  
  31. 	if (l == r) {
  32. 		seg[id] += val; 
  33. 		return; 
  34. 	}
  35.  
  36. 	int mid = (l + r) >> 1; 
  37. 	update(id << 1, l, mid, pos, val); 
  38. 	update(id << 1 | 1, mid + 1, r, pos, val); 
  39.  
  40. 	seg[id] = max(seg[id << 1], seg[id << 1 | 1]); 
  41. }
  42.  
  43. // Tìm khách sạn đầu tiên có số phòng >= x
  44. int getFirst(int id, int l, int r, int x) {
  45. 	if (seg[id] < x) return 0;  
  46.  
  47. 	if (l == r) return l;   
  48.  
  49. 	int mid = (l + r) >> 1;   
  50. 	int ans_child_l = getFirst(id << 1, l, mid, x);  
  51.  
  52. 	if (ans_child_l > 0) return ans_child_l;  
  53. 	return getFirst(id << 1 | 1, mid + 1, r, x); 
  54. }
  55.  
  56. int where[N];  
  57.  
  58. int main() {
  59. 	ios::sync_with_stdio(0); cin.tie(0);  	
  60. 	cin >> n >> m; 
  61. 	for (int i = 1; i <= n; i++) cin >> h[i];  
  62. 	for (int i = 1; i <= m; i++) cin >> r[i]; 
  63.  
  64. 	build(1, 1, n);
  65.  
  66. 	for (int i = 1; i <= m; i++) {
  67. 		where[i] = getFirst(1, 1, n, r[i]);  
  68. 		if (where[i] > 0) update(1, 1, n, where[i], -r[i]); 
  69. 	}
  70.  
  71. 	for (int i = 1; i <= m; i++) cout << where[i] << ' '; 
  72. }
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
8 5
3 2 4 1 5 5 2 6
4 4 7 1 1
stdout
copy 
3 5 0 1 1
https://ideone.com/Qjll9n
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!