Submission #1307242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307242		simona1230	Abracadabra (CEOI22_abracadabra)	C++20	0 / 100	813 ms	24020 KiB

Main

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e6+5;
int n,q;
int a[maxn];
int p[1001][1001];
int t,x;
void read()
{
    cin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        p[0][i]=a[i];
    }

}
int nxt[maxn];

void prec1()
{
    for(int i=1; i<=n; i++)
    {
        int j=1;
        int i1=1,i2=n/2+1;
        while(i1<=n/2||i2<=n)
        {
            if(i1>n/2)p[i][j++]=p[i-1][i2++];
            else if(i2>n)p[i][j++]=p[i-1][i1++];
            else if(p[i-1][i1]<p[i-1][i2])p[i][j++]=p[i-1][i1++];
            else p[i][j++]=p[i-1][i2++];
        }
    }
}

void solve1()
{
    for(int i=1; i<=q; i++)
    {
        int t,id;
        cin>>t>>id;
        cout<<p[min(n,t)][id]<<endl;
    }
}

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

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

int b[maxn];
set<group> s;
int sz[maxn];

void prec()
{
    for(int i=1; i<=n; i++)
        b[i]=a[i];

    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;
        s.insert({i});
        i=nxt[i];
    }
}

void solve()
{
    cin>>t>>x;
    if(t==0)
    {
        cout<<b[x]<<endl;
        for(int i=2; i<=q; i++)
        {
            cin>>t>>x;
            cout<<b[x]<<endl;
        }

        return;
    }

    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++;
    }

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

    /*for(int i=1;i<=n;i++)
        cout<<nxt[i]<<endl;
    cout<<endl;*/
    int lp=0;
    while(br!=-1&&lp<t)
    {
        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;

        //sz[nid]=g.id+sz[g.id]-nid;
        //s.insert(nid);
        while(nid<rt)
        {
            sz[nid]=nxt[nid]-nid;
            s.insert({nid});
            nid=nxt[nid];
        }

        s.erase({br});
        sz[br]=n/2-bf;
        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--;
        }

        if(br!=-1)cnt+=sz[br];
    }

    int i=1;
    for(it=s.begin(); it!=s.end(); it++)
    {
        group g=*it;
        int j=sz[g.id];
        //cout<<g.id<<" 0> "<<sz[g.id]<<endl;
        while(j--)
        {
            b[i++]=a[g.id];
            g.id++;
        }
    }

    cout<<b[x]<<endl;
    for(int i=1; i<q; i++)
    {
        cin>>t>>x;
        cout<<b[x]<<endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    read();
    if(n<=1)
    {
        prec1();
        solve1();
    }
    else
    {
        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
*/

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