fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int S = 1 << 19;
  5. struct seg_node {
  6. 	int sum;
  7. 	int suff;
  8. };
  9. seg_node seg[2*S];
  10.  
  11. void update_node(int i) {
  12. 	if (i >= S) {
  13. 		seg[i].suff = max(0, seg[i].sum);
  14. 	} else {
  15. 		seg[i].sum = seg[2*i].sum + seg[2*i+1].sum;
  16. 		seg[i].suff = max(seg[2*i+1].suff, seg[2*i+1].sum + seg[2*i].suff);
  17. 	}
  18. }
  19.  
  20. void update(int i, int d) {
  21. 	seg[i+S].sum += d;
  22. 	for (int a = i+S; a; a /= 2) {
  23. 		update_node(a);
  24. 	}
  25. }
  26.  
  27. int main() {
  28. 	ios::sync_with_stdio(0), cin.tie(0);
  29. 	int N; cin >> N;
  30. 	vector<int> P(N);
  31. 	vector<int> invP(N);
  32. 	for (int i = 0; i < N; i++) {
  33. 		cin >> P[i]; P[i] --;
  34. 		invP[P[i]] = i;
  35. 	}
  36.  
  37. 	int curAns = N;
  38. 	for (int i = 0; i < N; i++) {
  39. 		while (seg[1].suff <= 0) {
  40. 			curAns--;
  41. 			update(invP[curAns], 1);
  42. 		}
  43. 		cout << curAns+1 << " \n"[i+1==N];
  44.  
  45. 		int loc; cin >> loc; loc--;
  46. 		update(loc, -1);
  47. 	}
  48.  
  49. 	return 0;
  50. }
  51.  
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
6
2 3 6 1 5 4
5 2 1 4 6 3
stdout
copy 
6 5 5 5 4 1
https://ideone.com/LjZkPy
language:
C++14 (gcc 8.3)
created:
4 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!