Submission #1179704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179704		alexdd	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3095 ms	31756 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];
    }
    assert(0);
}
void afis()
{
    for(auto it:roots) cout<<it<<" "<<tori[unde[it]]<<" roots\n";
    cout<<"\n\n\n";
}

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;
    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);
        }
    }
    return cur+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)
    {
        roots.insert(a[poz]);
        upd(a[poz], tori[poz]);
        poz += tori[poz];
    }
    //afis();
    for(int t=1;t<=MAXT;t++)
    {
        /*int pref=0,mij=-1;
        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);*/

        int val_mij = cautare_binara(n/2);
        int pref = qry(val_mij);
        assert(pref >= n/2);
        assert(qry(val_mij-1) < n/2);
        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])
        {
            roots.insert(a[cur]);
            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: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25