Submission #918733

#	Time	Username	Problem	Language	Result	Execution time	Memory
918733		JakobZorz	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3038 ms	43584 KiB

Main

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
 
struct Query{
    int t,i,ans,ord;
};

void sort1(vector<Query>&vec){
    vector<vector<Query>>cnt(200001);
    for(auto i:vec)
        cnt[i.t].push_back(i);
    vec.clear();
    for(auto&i:cnt)
        for(auto&j:i)
            vec.push_back(j);
}

void sort2(vector<Query>&vec){
    vector<Query>vec2(vec.size());
    for(auto&i:vec)
        vec2[i.ord]=i;
    vec=vec2;
}

void solve(){
    int n,q;
    cin>>n>>q;
    vector<int>init(n);
    vector<int>nxt(n);
    for(int&i:init)
        cin>>i;
    
    stack<pair<int,int>>st;
    st.push({n+1,n});
    for(int i=n-1;i>=0;i--){
        while(st.top().first<init[i])
            st.pop();
        nxt[i]=st.top().second;
        st.push({init[i],i});
    }
    
    vector<Query>qrs(q);
    for(int i=0;i<q;i++)
        qrs[i].ord=i;
    for(auto&i:qrs){
        cin>>i.t>>i.i;
        i.t=min(i.t,n);
        i.i--;
    }
    sort1(qrs);
    
    set<pair<int,pair<int,int>>>s;
    int sl=n;
    vector<int>end(n,-1);
    int end_end=n;
    for(int curr=0;curr<n;){
        s.insert({init[curr],{curr,nxt[curr]}});
        curr=nxt[curr];
    }
    
    int cq=0;
    for(int round=0;round<=n;round++){
        while(sl-((--s.end())->second.second-(--s.end())->second.first)>=n/2){
            int last_len=(--s.end())->second.second-(--s.end())->second.first;
            sl-=last_len;
            end_end-=last_len;
            for(int i=0;i<last_len;i++)
                end[end_end+i]=init[(--s.end())->second.first+i];
            s.erase(--s.end());
        }
        
        if(cq<q&&qrs[cq].t==round){
            vector<int>vec=end;
            int ci=0;
            for(auto i:s){
                for(int j=i.second.first;j<i.second.second;j++){
                    vec[ci++]=init[j];
                }
            }
            
            while(cq<q&&qrs[cq].t==round){
                qrs[cq].ans=vec[qrs[cq].i];
                cq++;
            }
        }
        
        if(sl==n/2)
            continue;
        
        auto curr=(--s.end())->second;
        s.erase(--s.end());
        sl-=curr.second-curr.first;
        auto nw=curr;
        nw.second=nw.first+n/2-sl;
        s.insert({init[nw.first],nw});
        sl+=nw.second-nw.first;
        curr.first=nw.second;
        
        int prev=curr.first;
        for(int i=curr.first+1;i<curr.second;i++){
            if(init[i]>init[prev]){
                s.insert({init[prev],{prev,i}});
                sl+=i-prev;
                prev=i;
            }
        }
        s.insert({init[prev],{prev,curr.second}});
        sl+=curr.second-prev;
    }
    
    sort2(qrs);
    for(auto&i:qrs){
        cout<<i.ans<<"\n";
    }
}
 
int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("input.in","r",stdin);freopen("output.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}

/*
6 3
1 5 6 2 3 4
1 2
0 4
1 5
 
2
2
5
 

6 6
2 1 5 4 6 3
0 1
1 1
0 3
1 3
0 6
10 6
 
2
2
5
4
3
3
 

10 10
7 5 2 9 10 8 4 3 6 1
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
 
2
3
6
1
7
5
8
4
9
10
 
 
 */

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