Submission #1149655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149655		ace5	Abracadabra (CEOI22_abracadabra)	C++20	100 / 100	399 ms	61888 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const int maxlog = 20;

int segTree[4*maxn];
pair<int,int> st[maxlog][maxn];
int maxst[maxn];
int a[maxn];
int len[maxn];
int n;

void modify(int i,int x,int l,int r,int indV)
{
    if(l > i || r < i)
        return ;
    else if(l == r)
    {
        segTree[indV] = x;
        return ;
    }
    int m = (l+r)/2;
    modify(i,x,l,m,indV*2+1);
    modify(i,x,m+1,r,indV*2+2);
    segTree[indV] = segTree[indV*2+1] + segTree[indV*2+2];
}
pair<int,int> get(int l,int r,int indV,int k)
{
    if(l == r)
        return {l,k};
    int m = (l+r)/2;
    if(segTree[indV*2+2] > k)
    {
        return get(m+1,r,indV*2+2,k);
    }
    else
        return get(l,m,indV*2+1,k - segTree[indV*2+2]);
}

pair<int,int> MAX(int l,int r)
{
    return max(st[maxst[r-l+1]][l],st[maxst[r-l+1]][r-(1<<maxst[r-l+1])+1]);
}

void proc(int l,int r)
{
    while(l <= r)
    {
        pair<int,int> c = MAX(l,r);
        len[c.first] = r-c.second+1;
        modify(c.first,r-c.second+1,0,n-1,0);
        r = c.second-1;
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int q;
    cin >> n >> q;
    int ia[n];
    for(int i = 0;i < n;++i)
    {
        cin >> a[i];
        a[i]--;
        ia[a[i]] = i;
    }
    int tst = 0;
    for(int j = 1;j < maxn;++j)
    {
        maxst[j] = tst;
        if((1<<(tst+1)) <= j+1)
            tst++;
    }
    for(int u = 0;u < maxlog;++u)
    {
        for(int j = 0;j < n - (1<<u) + 1;++j)
        {
            st[u][j] = (u == 0 ? make_pair(a[j],j) : max(st[u-1][j],st[u-1][j+(1<<(u-1))]));
        }
    }
    proc(0,n-1);
    int ans[q];
    vector<vector<pair<int,int>>> que(n);
    for(int j = 0;j < q;++j)
    {
        int t,i;
        cin >> t >> i;
        i = n-i;
        que[min(t,n-1)].push_back({i,j});
    }
    for(int i = 0;i < n;++i)
    {
        for(int j = 0;j < que[i].size();++j)
        {
            pair<int,int> tk = get(0,n-1,0,que[i][j].first);
            int pos = ia[tk.first] + len[tk.first] - 1 - tk.second;
            ans[que[i][j].second] = a[pos];
        }
        pair<int,int> tk = get(0,n-1,0,n/2-1);
        int pos = ia[tk.first] + len[tk.first] - 1 - tk.second;
        if(pos != ia[tk.first])
        {
            modify(tk.first,pos-ia[tk.first],0,n-1,0);
            proc(pos,ia[tk.first] + len[tk.first] - 1);
            len[tk.first] = pos-ia[tk.first];
        }
    }
    for(int i = 0;i < q;++i)
    {
        cout << ans[i]+1 << "\n";
    }
    cout << "\n";
}

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