Submission #1179706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179706		alexdd	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	498 ms	40400 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXT = 3e5;
const int INF = 1e8;
int n,q;
int a[200005],tori[200005],unde[200005];
int rez[1000005];
vector<pair<int,int>> qrys[MAXT+5];
vector<int> comp[200005];

int aib[200005];
void upd(int poz, int newv)
{
    for(int i=poz;i<=n;i+=(i&(-i)))
        aib[i] += newv;
}
int qry(int poz)
{
    int aux=0;
    for(int i=poz;i>0;i-=(i&(-i)))
        aux += aib[i];
    return aux;
}
int cautare_binara(int k)
{
    int cur=0,initk=k;
    for(int p=17;p>=0;p--)
    {
        if(cur + (1<<p) <= n && aib[cur + (1<<p)] < k)
        {
            k -= aib[cur + (1<<p)];
            cur += (1<<p);
        }
    }
    assert(qry(cur) < initk);
    assert(qry(cur+1) >= initk);
    return cur+1;
}


int answer_qry(int poz)
{
    /*int pref=0;
    for(auto val_it:roots)
    {
        int it = unde[val_it];
        if(pref + tori[it] >= poz)
        {
            return a[it + (poz - pref) - 1];
        }
        pref += tori[it];
    }
    assert(0);*/
    int val_it = cautare_binara(poz);
    int it = unde[val_it];
    int pref = qry(val_it) - tori[it];

    return a[it + (poz - pref) - 1];
}


signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        unde[a[i]] = i;
    }
    deque<int> dq;
    for(int i=n;i>0;i--)
    {
        while(!dq.empty() && a[i] > a[dq.back()])
            dq.pop_back();
        if(dq.empty())
            tori[i] = n+1 - i;
        else
            tori[i] = dq.back() - i;
        dq.push_back(i);
    }
    for(int i=1;i<=q;i++)
    {
        int t,poz;
        cin>>t>>poz;
        if(t==0)
        {
            rez[i] = a[poz];
        }
        else
        {
            t = min(t, MAXT);
            qrys[t].push_back({poz,i});
        }
    }
    int poz=1;
    while(poz<=n)
    {
        upd(a[poz], tori[poz]);
        poz += tori[poz];
    }
    //afis();
    for(int t=1;t<=MAXT;t++)
    {
        int val_mij = cautare_binara(n/2);
        int pref = qry(val_mij);
        int mij = unde[val_mij];

        if(pref == n/2)
        {
            for(int u=t;u<=MAXT;u++)
                for(auto [poz,id]:qrys[u])
                    rez[id] = answer_qry(poz);

            for(int i=1;i<=q;i++)
                cout<<rez[i]<<"\n";
            return 0;
        }

        upd(a[mij], -tori[mij]);
        int oldri = mij + tori[mij];
        tori[mij] = n/2 - (pref - tori[mij]);
        upd(a[mij], +tori[mij]);
        int cur = mij + tori[mij];
        while(cur<oldri && a[cur] < a[mij])
        {
            if(cur + tori[cur] >= oldri)
                tori[cur] = oldri - cur;
            upd(a[cur], tori[cur]);
            cur += tori[cur];
        }

        for(auto [poz,id]:qrys[t])
            rez[id] = answer_qry(poz);

        //afis();

    }
    assert(0);
}

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