oj.uz

Submission #918733

# Submission time Handle Problem Language Result Execution time Memory
918733 2024-01-30T10:15:05 Z JakobZorz Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 43584 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 40396 KB Output is correct
2 Correct 183 ms 38648 KB Output is correct
3 Correct 186 ms 37872 KB Output is correct
4 Correct 182 ms 35928 KB Output is correct
5 Correct 183 ms 41420 KB Output is correct
6 Correct 173 ms 39256 KB Output is correct
7 Correct 183 ms 43584 KB Output is correct
8 Correct 171 ms 37728 KB Output is correct
9 Correct 167 ms 36964 KB Output is correct
10 Correct 165 ms 37032 KB Output is correct
11 Correct 174 ms 36780 KB Output is correct
12 Correct 171 ms 35120 KB Output is correct
13 Correct 176 ms 35744 KB Output is correct
14 Correct 172 ms 39408 KB Output is correct
15 Correct 172 ms 37236 KB Output is correct
16 Correct 2 ms 4952 KB Output is correct
17 Correct 169 ms 38848 KB Output is correct
18 Correct 159 ms 35248 KB Output is correct
19 Correct 2 ms 4952 KB Output is correct
20 Correct 2 ms 4952 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3016 ms 40052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3038 ms 10064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 40396 KB Output is correct
2 Correct 183 ms 38648 KB Output is correct
3 Correct 186 ms 37872 KB Output is correct
4 Correct 182 ms 35928 KB Output is correct
5 Correct 183 ms 41420 KB Output is correct
6 Correct 173 ms 39256 KB Output is correct
7 Correct 183 ms 43584 KB Output is correct
8 Correct 171 ms 37728 KB Output is correct
9 Correct 167 ms 36964 KB Output is correct
10 Correct 165 ms 37032 KB Output is correct
11 Correct 174 ms 36780 KB Output is correct
12 Correct 171 ms 35120 KB Output is correct
13 Correct 176 ms 35744 KB Output is correct
14 Correct 172 ms 39408 KB Output is correct
15 Correct 172 ms 37236 KB Output is correct
16 Correct 2 ms 4952 KB Output is correct
17 Correct 169 ms 38848 KB Output is correct
18 Correct 159 ms 35248 KB Output is correct
19 Correct 2 ms 4952 KB Output is correct
20 Correct 2 ms 4952 KB Output is correct
21 Execution timed out 3016 ms 40052 KB Time limit exceeded
22 Halted 0 ms 0 KB -