Submission #1311059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311059		aaaaaaaa	Bubble Sort Machine (JOI25_bubble)	C++20	11 / 100	36 ms	4560 KiB

bubble

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, q;
    cin >> n;
    vector<int> a(n + 1, 0), pmn(n + 2, inf);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i){
        pmn[i] = min(pmn[i - 1], a[i]);
    }
    vector<pair<int, int>> id;
    for(int i = 1; i <= n; ++i){
        if(pmn[i] != pmn[i - 1]){
            id.push_back({i - 1, pmn[i]});
        }
    } cin >> q;
    int update = 0;
    while(q--){
        int t, l, r;
        cin >> t;
        if(t == 1){
            update += 1;
        }else{
            cin >> l >> r;
            assert(l == r);
            if(update >= id.back().first){
                cout << id.back().second << "\n";
                continue;
            }
            int st = 0, en = (int) id.size() - 1, ans = -1;
            while(st <= en){
                int mid = st + (en - st) / 2;
                if((mid + 1) >= (int) id.size()) en = mid - 1;
                int l = id[mid].first, r = id[mid + 1].first - 1;
                if(update < l) en = mid - 1;
                else if(update > r) st = mid + 1;
                else{
                    ans = id[mid].second;
                    break;
                }
            }
            assert(ans != -1);
            cout << ans << "\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