oj.uz

Submission #918751

# Submission time Handle Problem Language Result Execution time Memory
918751 2024-01-30T11:18:12 Z JakobZorz Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 26192 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,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<vector<Query>>qrs(n+1);
    vector<int>ans(q);
    for(int i=0;i<q;i++){
        Query nq;
        nq.ord=i;
        cin>>nq.t>>nq.i;
        nq.t=min(nq.t,n);
        nq.i--;
        qrs[nq.t].push_back(nq);
    }
    
    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];
    }
    
    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(qrs[round].size()){
            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];
                }
            }
            
            for(auto i:qrs[round]){
                ans[i.ord]=vec[i.i];
            }
        }
        
        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;
    }
    
    for(int i:ans){
        cout<<i<<"\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 163 ms 23176 KB Output is correct
2 Correct 159 ms 21664 KB Output is correct
3 Correct 149 ms 21072 KB Output is correct
4 Correct 146 ms 19536 KB Output is correct
5 Correct 158 ms 24056 KB Output is correct
6 Correct 144 ms 24912 KB Output is correct
7 Correct 155 ms 26192 KB Output is correct
8 Correct 147 ms 23376 KB Output is correct
9 Correct 147 ms 21808 KB Output is correct
10 Correct 148 ms 20872 KB Output is correct
11 Correct 141 ms 21452 KB Output is correct
12 Correct 142 ms 20156 KB Output is correct
13 Correct 147 ms 20000 KB Output is correct
14 Correct 148 ms 23888 KB Output is correct
15 Correct 151 ms 20156 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 133 ms 19352 KB Output is correct
18 Correct 141 ms 19372 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3029 ms 25020 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 3016 ms 7248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 23176 KB Output is correct
2 Correct 159 ms 21664 KB Output is correct
3 Correct 149 ms 21072 KB Output is correct
4 Correct 146 ms 19536 KB Output is correct
5 Correct 158 ms 24056 KB Output is correct
6 Correct 144 ms 24912 KB Output is correct
7 Correct 155 ms 26192 KB Output is correct
8 Correct 147 ms 23376 KB Output is correct
9 Correct 147 ms 21808 KB Output is correct
10 Correct 148 ms 20872 KB Output is correct
11 Correct 141 ms 21452 KB Output is correct
12 Correct 142 ms 20156 KB Output is correct
13 Correct 147 ms 20000 KB Output is correct
14 Correct 148 ms 23888 KB Output is correct
15 Correct 151 ms 20156 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 133 ms 19352 KB Output is correct
18 Correct 141 ms 19372 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Execution timed out 3029 ms 25020 KB Time limit exceeded
22 Halted 0 ms 0 KB -