제출 #1274454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274454		i_love_spring	Bubble Sort Machine (JOI25_bubble)	C++20	11 / 100	127 ms	6716 KiB

bubble

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
void solve() {
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n;i++) {
    cin >> a[i];
  }
  vector<int> dec,dp,pos;
  dec.push_back(a[1]);
  dp.push_back(0);
  pos.push_back(1);
  for (int i = 2; i <= n;i++) {
    if (dec.back() > a[i]) { 
      dec.push_back(a[i]);
      dp.push_back(dp.back() + (i - pos.back()));
      pos.push_back(i);
    }
  }
  int q;
  cin >> q;
  int cnt = 0;
  reverse(dp.begin(), dp.end());
  reverse(dec.begin(), dec.end());
  dp.pop_back();
  while(q--) { 
    int qt;
    cin >> qt;
    if (qt == 1) cnt++;
    else {
      int l, r;
      cin >> l >> r;
      while (!dp.empty() && dp.back() <= cnt) {
        dp.pop_back();
        dec.pop_back();
      }
      cout << dec.back() << "\n";
    }
  }

}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  //cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  return 0;
} 

• Subtask 1: 0 / 5
• Subtask 2: 11 / 11
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 29
• Subtask 6: 0 / 17