제출 #970766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
970766		berr	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	584 ms	74536 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
#define int long long
vector<int> ar, pos;

struct segtree{
    int n, type, tl, tr, val, pos, el;

    vector<int> st, a;
    int base=0;

    int merge(int x, int y){
        if(type) return max(x, y);
        return x + y;
    }
    segtree(int _n){
        n = _n; type = 0;
        st.resize(4*n);
    }

    segtree(int _n, vector<int> _a){
        n = _n; a = _a; type = 1;
        st.resize(4*n);
        build(1, 0, n-1);
    }

    void build(int v, int l, int r){
        if(l==r) st[v] = a[l];
        else{
            int mid = (l+r) / 2;
            build(v*2, l, mid);
            build(v*2+1, mid+1, r);
            st[v] = merge(st[v*2], st[v*2+1]);
        }
    }

    void upd(int v, int l, int r){
        if(l==r) st[v] = val;
        else{
            int mid = (l+r) /2;
            if(pos <= mid) upd(v*2, l, mid);
            else upd(v*2+1, mid+1, r);
            st[v] = merge(st[v*2], st[v*2+1]);
        }
    }

    void update(int _pos, int va){
        pos = _pos; val=va;
        upd(1, 0, n-1);
    }

    array<int, 2> get1(int v, int l, int r){
        if(l==r){
            return {val-el-1, l};
        }
        else{
            int mid = (l+r)/2;
            if(el+st[v*2] >=val&&st[v*2]>0) return get1(v*2, l, mid);
            el+=st[v*2];
            return get1(v*2+1, mid+1, r);
        }
    }
    array<int, 2> get(int h){
        val = h, el = 0;
        return get1(1, 0, n-1);
    }

    int get0(int v, int l, int r){
        if(l>tr || r < tl) return 0;
        else if(l>= tl && r<= tr) return st[v];
        else{
            int mid = (l+r) /2;
            return merge(get0(v*2, l, mid), get0(v*2+1, mid+1, r));
        }
    }

    int get(int l, int r){
        tl = l; tr = r;
        return get0(1, 0, n-1);
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m; cin >> n >> m;
    vector<int> a(n);

    for (auto &i: a) cin >> i, i--;

    segtree st_sizes(n);
    segtree st_max(n, a);

    vector<array<int, 2>> val(n, {-1, -1});
    int l=0;
    for(int i=1; i<n; i++){
        if(a[l]<a[i]){
            val[a[l]]={l, i-1};
            l=i;
        }
    }
    ar = a;
    pos.resize(n);

    for(int i=0; i<n; i++) pos[a[i]]=i;

    val[a[l]] = {l, n-1};

    for(int i=0; i<n; i++){
        if(val[i][0]!=-1){
            st_sizes.update(i, val[i][1]-val[i][0]+1);
        }
    }
    vector<array<int, 2>> q(m);
    vector<int> ans(m);

    for(auto &[i, l]: q) cin >> i >> l, i=min(i,  n);

    vector<int> id(m);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int a, int b){
        return q[a][0] < q[b][0];
    });

    int it = 0;
    for(auto i: id){
        while(it < q[i][0]){
            auto [value, g]=st_sizes.get(n/2);
            int po = pos[g];
           
            if(value==val[g][1]-val[g][0]+1){
                it++;
                continue;
            }


            int k =po+value+1;
            int r = val[g][1];

            while(k<=r){
                int v = st_max.get(k, r);
                val[v]={pos[v], r};
                st_sizes.update(v, r-pos[v]+1);
                r = pos[v]-1;
            }

            st_sizes.update(g, k-po);
            val[g]={po, k-1};

            it++;
        }
        auto [value, g]=st_sizes.get(q[i][1]);
        ans[i]=a[pos[g]+value];
    }

    for(auto i: ans) cout<<i+1<<"\n";


}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25