Submission #918729

#	Time	Username	Problem	Language	Result	Execution time	Memory
918729		JakobZorz	Abracadabra (CEOI22_abracadabra)	C++17	0 / 100	3034 ms	18256 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;
};

bool cmp1(Query&a,Query&b){
    return a.t<b.t;
}

bool cmp2(Query&a,Query&b){
    return a.ord<b.ord;
}

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--;
    }
    //sort(qrs.begin(),qrs.end(),cmp1);
    
    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;
    }
    
    //sort(qrs.begin(),qrs.end(),cmp2);
    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
 
 
 */

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:67:9: warning: unused variable 'cq' [-Wunused-variable]
   67 |     int cq=0;
      |         ^~

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