Submission #1307344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307344		simona1230	Abracadabra (CEOI22_abracadabra)	C++20	100 / 100	1213 ms	47596 KiB

Main

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e6+5;

int n,q;
int a[maxn];

int t[maxn],x[maxn];
vector<int> v[maxn];
int ans[maxn];
int op[maxn];

void read()
{
    cin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        op[a[i]]=i;
    }

    for(int i=1; i<=q; i++)
    {
        cin>>t[i]>>x[i];
        v[min(n,t[i])].push_back(i);
        if(t[i]==0)ans[i]=a[x[i]];
    }
}

struct group
{
    int id;
    group() {}
    group(int _id)
    {
        id=_id;
    }

    bool operator<(const group&g)const
    {
        return a[id]<a[g.id];
    }
};

set<group> s;
int sz[maxn],nxt[maxn];
int tr[800001];
void upd(int i,int l,int r,int id,int vl)
{
    if(l==r)
    {
        //cout<<"in "<<l<<" "<<vl<<endl;
        tr[i]=vl;
        return;
    }

    int m=(l+r)/2;
    if(id<=m)upd(i*2,l,m,id,vl);
    else upd(i*2+1,m+1,r,id,vl);

    tr[i]=tr[i*2]+tr[i*2+1];
}

pair<int,int> query(int i,int l,int r,int x,int bf)
{
    if(l==r)return {bf+tr[i],l};
    int m=(l+r)/2;
    if(tr[i*2]>=x)return query(i*2,l,m,x,bf);
    return query(i*2+1,m+1,r,x-tr[i*2],bf+tr[i*2]);
}

void prec()
{
    stack<int> h;
    for(int i=n; i>=1; i--)
    {
        while(h.size()&&a[h.top()]<a[i])h.pop();
        if(h.size())nxt[i]=h.top();
        else nxt[i]=n+1;
        h.push(i);
    }

    int i=1;
    while(i<=n)
    {
        sz[i]=nxt[i]-i;
        upd(1,1,n,a[i],sz[i]);
        s.insert({i});
        i=nxt[i];
    }
}



void solve()
{
    int br=-1;
    int cnt=0;
    auto it=s.begin();

    while(cnt<n/2)
    {
        cnt+=sz[it->id];
        if(cnt>n/2)br=it->id;
        else if(cnt<n/2)it++;
    }

    if(br==-1)
    {
        for(int lp=1;lp<=n;lp++)
        {
            for(int i=0; i<v[lp].size(); i++)
            {
                int idx=x[v[lp][i]];
                pair<int,int> h=query(1,1,n,idx,0);
                //cout<<idx<<" ? "<<h.first<<" "<<op[h.second]<<" "<<sz[op[h.second]]<<endl;
                ans[v[lp][i]]=a[op[h.second]+sz[op[h.second]]-1-(h.first-idx)];
            }
        }
    }

    //cout<<"here"<<endl;

    /*for(int i=1;i<=n;i++)
        cout<<nxt[i]<<endl;
    cout<<endl;*/
    int lp=0;
    while(br!=-1)
    {
        lp++;

        it=s.find({br});
        group g=*it;
        int rt=br+sz[br];

        int bf=cnt-sz[g.id];
        int nid=n/2-bf+g.id;

        while(nid<rt)
        {
            sz[nid]=min(rt,nxt[nid])-nid;
            upd(1,1,n,a[nid],sz[nid]);
            s.insert({nid});
            nid=nxt[nid];
        }

        s.erase({br});
        sz[br]=n/2-bf;
        upd(1,1,n,a[br],sz[br]);
        s.insert({br});

        it=s.find(br);

        while(cnt>n/2)
        {
            cnt-=sz[it->id];
            if(cnt==n/2)br=-1;
            else if(cnt<n/2)br=it->id;
            else it--;
        }

        for(int i=0; i<v[lp].size(); i++)
        {
            int idx=x[v[lp][i]];
            pair<int,int> h=query(1,1,n,idx,0);
            //cout<<idx<<" ? "<<h.first<<" "<<op[h.second]<<" "<<sz[op[h.second]]<<endl;
            ans[v[lp][i]]=a[op[h.second]+sz[op[h.second]]-1-(h.first-idx)];
        }

        if(br!=-1)cnt+=sz[br];
        else
        {
            while(lp<n)
            {
                lp++;
                for(int i=0; i<v[lp].size(); i++)
                {
                    int idx=x[v[lp][i]];
                    pair<int,int> h=query(1,1,n,idx,0);
                    //cout<<idx<<" ? "<<h.first<<" "<<op[h.second]<<" "<<sz[op[h.second]]<<endl;
                    ans[v[lp][i]]=a[op[h.second]+sz[op[h.second]]-1-(h.first-idx)];
                }
            }
        }
    }

    for(int i=1; i<=q; i++)
        cout<<ans[i]<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    read();
    prec();
    solve();
    return 0;
}

/*
10 0
3 2 7 5 4 6 1 8 9 10
*/

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

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

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

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