Submission #1179690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179690		alexdd	Abracadabra (CEOI22_abracadabra)	C++17	0 / 100	1344 ms	36256 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];

set<int> roots;
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];
    }
    return -1;
    //assert(0);
}
void afis()
{
    for(auto it:roots) cout<<it<<" "<<tori[unde[it]]<<" roots\n";
    cout<<"\n\n\n";
}
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)
    {
        roots.insert(a[poz]);
        poz += tori[poz];
    }
    //afis();
    for(int t=1;t<=MAXT;t++)
    {
        int pref=0,mij=-1;
        bool perfectly_split=0;
        for(auto val_it:roots)
        {
            int it = unde[val_it];
            pref += tori[it];
            if(pref >= n/2)
            {
                if(pref==n/2)
                    perfectly_split=1;
                mij = it;
                break;
            }
        }
        assert(mij!=-1);
        if(perfectly_split)
        {
            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;
        }

        int oldri = mij + tori[mij];
        tori[mij] = n/2 - (pref - tori[mij]);
        //cout<<a[mij]<<" "<<tori[mij]<<"  mij & newtori\n";
        int cur = mij + tori[mij];
        while(cur<oldri && a[cur] < a[mij])
        {
            roots.insert(a[cur]);
            //cout<<a[cur]<<" new root\n";
            cur += tori[cur];
        }

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

        //afis();

    }
    assert(0);
}

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