fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define mp make_pair
  3. #define pii pair<int, int>
  4.  
  5. using namespace std;
  6.  
  7. struct compare{
  8.     bool operator()(pii& p1, pii& p2){
  9.         if(p1.second == p2.second) return p1.first < p2.first;
  10.         return p1.second > p2.second;
  11.     }  
  12. };
  13.  
  14. vector<pii> pairs[3];
  15.  
  16. priority_queue<pii, vector<pii>, compare> q1, q2;
  17.  
  18. int m, dp[100001], n, seg[200001], lazy[200001] = {0};
  19.  
  20. class seg_tree{
  21. 	int seg[200001], lazy[200001];
  22. 	public :
  23. 		seg_tree(){
  24. 			for(int j = 0; j < 200001; j++)
  25. 				seg[j] = lazy[j] = 0;
  26. 		}
  27.  
  28. 	void update_lazy(int, int, int);
  29. 	void update(int, int, int, int, int, int);
  30. 	int query(int, int, int, int, int);
  31. };
  32.  
  33. void seg_tree :: update_lazy(int l, int r, int i){
  34. 	if(l != r) lazy[i*2+1] += lazy[i], lazy[i*2+2] += lazy[i];
  35. 	seg[i] += lazy[i];
  36. 	lazy[i] = 0;
  37. }
  38.  
  39. void seg_tree :: update(int l, int r, int i, int x, int y, int val){
  40. 	if(lazy[i]) update_lazy(l, r, i);
  41. 	if(r < x || l > y) return;
  42. 	if(l >= x && r <= y){
  43. 		seg[i] += val;
  44. 		if(l != r) lazy[i*2+1] += val, lazy[i*2+2] += val;
  45. 		return;
  46. 	}
  47. 	int mid = (l+r)/2;
  48. 	update(l, mid, i*2+1, x, y, val);
  49. 	update(mid+1, r, i*2+2, x, y, val);
  50. 	if(l != r) seg[i] = max(seg[i*2+1], seg[i*2+2]);
  51. }
  52.  
  53. int seg_tree :: query(int l, int r, int i, int x, int y){
  54. 	if(lazy[i]) update_lazy(l, r, i);
  55. 	if(r < x || l > y) return 0;
  56. 	if(l >= x && r <= y) return seg[i];
  57. 	int mid = (l+r)/2;
  58. 	int left = query(l, mid, i*2+1, x, y);
  59. 	int right = query(mid+1, r, i*2+2, x, y);
  60. 	if(l != r) seg[i] = max(seg[i*2+1], seg[i*2+2]);
  61. 	return max(left, right);
  62. }
  63.  
  64. seg_tree *s1, *s2;
  65.  
  66. void build(){
  67. 	cin >> m >> n;
  68. 	string which[n + 1];
  69. 	int starting[n + 1], ending[n + 1];
  70.  
  71. 	for(int j = 0; j < n; j++)
  72. 		cin >> which[j];
  73. 	for(int j = 0; j < n; j++)
  74. 		cin >> starting[j];
  75. 	for(int j = 0; j < n; j++)
  76. 		cin >> ending[j];
  77.  
  78. 	for(int j = 0; j < n; j++){
  79.         if(starting[j] > ending[j]) continue;
  80. 		if(which[j][0] == 'E') q1.push(mp(starting[j], ending[j]));
  81. 		else if(which[j][0] == 'D') q2.push(mp(starting[j], ending[j]));
  82. 		else if(which[j][0] == 'C') q1.push(mp(starting[j], ending[j]));
  83. 		else q2.push(mp(starting[j], ending[j]));
  84. 	}
  85.  
  86. 	s1 = new seg_tree;
  87. 	s2 = new seg_tree;
  88. }
  89.  
  90.  
  91. void build_dp(){
  92. 	dp[0] = 0;
  93. 	for(int j = 1; j <= m; j++){
  94. 		int ans = 0;
  95.  
  96. 		while(!q1.empty() && q1.top().second == j){
  97. 			pii p = q1.top();
  98. 			q1.pop();
  99. 			s1->update(0, m, 0, 1, p.first, 1);
  100. 			int curr = s1->query(0, m, 0, 1, p.first);
  101. 			if(ans < curr) ans = curr;
  102. 		}
  103.  
  104. 		while(!q2.empty() && q2.top().second == j){
  105. 			pii p = q2.top();
  106. 			q2.pop();
  107. 			s2->update(0, m, 0, 1, p.first, 1);
  108. 			int curr = s2->query(0, m, 0, 1, p.first);
  109. 			if(ans < curr) ans = curr;
  110. 		}
  111.  
  112. 		dp[j] = ans;
  113. 		s1->update(0, m, 0, j, j, dp[j]);
  114. 		s2->update(0, m, 0, j, j, dp[j]);
  115. 	}
  116. }
  117.  
  118. int main(){
  119. 	int t;
  120.     cin >> t;
  121. 	while(t--){
  122. 		build();
  123. 		build_dp();
  124. 		int ans[n + 1], k = 1;
  125. 		for(int j = 1; j <= m; j++){
  126. 			while(k <= n && k <= dp[j])
  127. 				ans[k++] = j;
  128. 		}
  129. 		for(int j = k; j <= n; j++)
  130. 			ans[j] = -1;
  131. 		for(int j = 1; j <= n; j++)
  132. 			cout << ans[j] << " ";
  133. 		cout << endl;
  134. 	}
  135. 	return 0;
  136. }
  137.  
Success #stdin #stdout 0s 9336KB
comments (?)
stdin
copy 
2
10 3
E D C
4 1 4
7 5 8
10 6
E D C M E D
1 1 1 2 9 7
2 2 2 4 10 10
stdout
copy 
5 8 -1 
2 2 4 10 -1 -1
https://ideone.com/5nSRUd
language:
C++14 (gcc 8.3)
created:
6 years 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!