Submission #25586281

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
const int MAX = 2e5;
int dq[400005];
int s, e;
int sort_s, sort_e;
int Q;
multiset<int> ms;
int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  cin >> Q;
  s = 0, e = 0;
  sort_s = sort_e = -1;
  for(int i=0;i<Q;++i) {
    int q; cin >> q;
    if (q == 1) {
      int x; cin >> x;
      dq[e++] = x;
    }
    else if (q == 2) {
      int x;
      if (s < sort_e) {
        x = *ms.begin();
        ms.erase(ms.find(x));
      }
      else x = dq[s];
      ++s;
      cout << x << '\n';
    }
    else {
      if (sort_e == -1) {
        for(int idx=s;idx<e;++idx) ms.insert(dq[idx]);
        sort_s = s;
        sort_e = e;
      }
      else if (s >= sort_e) {
        int idx = s;
        while(idx < e) ms.insert(dq[idx++]);
        sort_e = e;
      }
      else {
        int idx = sort_e;
        while(idx < e) ms.insert(dq[idx++]);
        sort_e = e;
      }
    }
  }
  return 0;
}

Submission Info

Judge Result