Submission #983430

#	Time	Username	Problem	Language	Result	Execution time	Memory
983430		alexdd	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3024 ms	30152 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int bulan = 5000;
int n,q;
vector<int> a;
vector<int> qrys[bulan+5];
int rez[1000005],u[1000005];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    a.resize(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    int t;
    for(int i=1;i<=q;i++)
    {
        cin>>t>>u[i];
        u[i]--;
        t = min(t,bulan);
        qrys[t].push_back(i);
        rez[i]=-1;
    }
    for(int pas=0;pas<=bulan+2;pas++)
    {
        for(auto x:qrys[pas])
            rez[x] = a[u[x]];
        deque<int> le,ri;
        vector<int> newa;
        for(int i=0;i<n/2;i++)
            le.push_back(a[i]);
        for(int i=n/2;i<n;i++)
            ri.push_back(a[i]);
        for(int i=0;i<n;i++)
        {
            if(!le.empty() && (ri.empty() || le.front()<ri.front()))
            {
                newa.push_back(le.front());
                le.pop_front();
            }
            else
            {
                newa.push_back(ri.front());
                ri.pop_front();
            }
        }
        if(a==newa)
        {
            break;
        }
        a = newa;
    }
    for(int i=1;i<=q;i++)
    {
        if(rez[i]==-1) rez[i] = a[u[i]];
        cout<<rez[i]<<"\n";
    }
    return 0;
}

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