fork download
  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
stdin
6
2 3 6 1 5 4
5 2 1 4 6 3
stdout
6 5 5 5 4 1