Submission #662299

#	Time	Username	Problem	Language	Result	Execution time	Memory
662299		fatemetmhr	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	675 ms	42100 KiB

Main

// heiy ... ye rooze jadid ...

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 1e6 + 10;
const int maxnt = 1e6 + 10;

int sum[maxnt], a[maxn5], rev[maxn5], out[maxn5], per[maxn5];
int rig[maxn5], sz[maxn5], t[maxn5], ind[maxn5], last[maxn5];
bool mark[maxn5];
vector <int> av;

inline bool cmp(int i, int j){return t[i] < t[j];}

void upd(int l, int r, int id, int val, int v){
    if(r - l == 1){
        sum[v] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid)
        upd(l, mid, id, val, v * 2);
    else
        upd(mid, r, id, val, v * 2 + 1);
    sum[v] = sum[v * 2] + sum[v * 2 + 1];
}

pair<int, int> find_first(int l, int r, int val, int v){
    if(r - l == 1)
        return {l, sum[v]};
    int mid = (l + r) >> 1;
    if(sum[v * 2] >= val)
        return find_first(l, mid, val, v * 2);
    auto ans = find_first(mid, r, val - sum[v * 2], v * 2 + 1);
    return {ans.fi, ans.se + sum[v * 2]};
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, q; cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i]--;
        rev[a[i]] = i;
    }
    for(int i = 0; i < q; i++){
        cin >> t[i] >> ind[i];
        per[i] = i;
    }
    fill(rig, rig + n + 10, n);
    for(int i = n - 1; i >= 0; i--){
        while(av.size() && a[av.back()] < a[i])
            av.pop_back();
        if(av.size())
            rig[i] = av.back();
        av.pb(i);
    }

    for(int i = 0; i != n; i = rig[i]){
        upd(0, n, a[i], rig[i] - i, 1);
        sz[i] = rig[i] - i;
        mark[i] = true;
        //cout << "ok " << i << ' ' << rig[i] << ' ' << sz[i] << endl;
        last[i] = rig[i];
    }


    sort(per, per + q, cmp); // bar hasbe t[i]

    int done = 0;
    bool re = false;

    for(int i = 0; i < q; i++){
        while(done < t[per[i]] && !re){
            done++;
            auto tmp = find_first(0, n, n / 2, 1);
            int p = tmp.fi, r = tmp.se - n / 2;
            if(r == 0){
                re = true;
                break;
            }
            int v = rev[p] + sz[rev[p]] - r;
            int vv = v;
            //cout << "now " << done << ' ' << p << ' ' << r << ' ' << v << ' ' << rev[p] << ' ' << sz[rev[p]] << ' ' << tmp.se << endl;
            sz[rev[p]] -= r;
            upd(0, n, p, sz[rev[p]], 1);
            for(; !mark[v] && v != n ; v = rig[v]){
                mark[v] = true;
                sz[v] = min(last[rev[p]], rig[v]) - v;
                last[v] = min(last[rev[p]], rig[v]);
                //cout << "it's " << v << ' ' << rig[v] << ' ' << sz[v] << endl;
                upd(0, n, a[v], sz[v], 1);
            }
            last[rev[p]] = vv;
        }
        auto tmp = find_first(0, n, ind[per[i]], 1);
        int p = tmp.fi, r = tmp.se - ind[per[i]];
        r = sz[rev[p]] - r - 1;
        out[per[i]] = a[rev[p] + r] + 1;
    }

    for(int i = 0; i < q; i++)
        cout << out[i] << '\n';
    
}

/*
8 1
6 8 3 5 4 7 2 1 
3 5

*/

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