Submission #992071

#	Time	Username	Problem	Language	Result	Execution time	Memory
992071		Savu_Stefan_Catalin	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	408 ms	42940 KiB

Main

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
const int NMAX=2e5+5,MM=1e6+5;
int ar[4*NMAX+505],n,q,val[NMAX+5],a[NMAX+5],inv[NMAX+5],ap[NMAX+5],urm[NMAX+5];
pair<pair<int,int>,int> t[MM];
int ras[MM];
pair<int,int> add(pair<int,int> a,pair<int,int> b)
{
    return {a.first+b.first,a.second+b.second};
}
void update(int st,int dr,int nod,int poz,int val)
{
    if (st==dr)
    {
        ar[nod]=val;
        return ;
    }
    int mij=(st+dr)/2;
    if (poz<=mij) update(st,mij,nod*2,poz,val);
    else update(mij+1,dr,nod*2+1,poz,val);
    ar[nod]=ar[nod*2]+ar[nod*2+1];
}
pair<int,int> query(int st,int dr,int nod,int val)
{
    if (st==dr)
    {
        return {st,ar[nod]};
    }
    int mij=(st+dr)/2;
    if (ar[nod*2]<val) return add(query(mij+1,dr,nod*2+1,val-ar[nod*2]),{0,ar[nod*2]});
    else return query(st,mij,nod*2,val);
}
void operation()
{
    int cen=0,allval=0;
    {
    pair<int,int> nod=query(1,n,1,n/2+1);
    int x=n/2+1-(nod.second-val[nod.first]);
    if (x==1) return ;
    allval=val[nod.first]-(x-1);
    val[nod.first]=x-1;
    update(1,n,1,nod.first,val[nod.first]);
    cen=a[inv[nod.first]+x-1];
    }
    int nod=cen;
    while (ap[nod]==0)
    {
        ap[nod]=1;
        val[nod]=min(allval,inv[urm[nod]]-inv[nod]);
        update(1,n,1,nod,val[nod]);
        allval-=val[nod];
        nod=urm[nod];
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for (int i=1;i<=n;++i)
    {
        cin>>a[i];
        inv[a[i]]=i;
    }
    inv[n+1]=n+1;
    stack <int> s;
    for (int i=1;i<=n;++i)
    {
        while (!s.empty()&&a[s.top()]<a[i]) {urm[a[s.top()]]=a[i]; s.pop();}
        s.push(i);
    }
    while (!s.empty()) {urm[a[s.top()]]=n+1; s.pop();}
    for (int i=1;i<=q;++i)
    {
        cin>>t[i].first.first>>t[i].first.second;
        t[i].second=i;
    }
    sort(t+1,t+q+1);
    {
        ap[n+1]=1;
        int nod=a[1];
        while (nod!=n+1)
        {
            ap[nod]=1;
            val[nod]=inv[urm[nod]]-inv[nod];
            update(1,n,1,nod,inv[urm[nod]]-inv[nod]);
            nod=urm[nod];
        }
    }
    int cat=0;
    for (int i=1;i<=q;++i)
    {
        while (cat<t[i].first.first&&cat<=n+5) {cat++; operation();}
        {
            auto nod=query(1,n,1,t[i].first.second);
            int x=t[i].first.second-(nod.second-val[nod.first]);
            ras[t[i].second]=a[inv[nod.first]+x-1];
        }
    }
    for (int i=1;i<=q;++i)
        cout<<ras[i]<<'\n';
    return 0;
}

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