oj.uz

Submission #918723

# Submission time Handle Problem Language Result Execution time Memory
918723 2024-01-30T10:00:54 Z JakobZorz Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 25680 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;
};

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
 
 
 */

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 24084 KB Output is correct
2 Correct 326 ms 23904 KB Output is correct
3 Correct 324 ms 22864 KB Output is correct
4 Correct 292 ms 22232 KB Output is correct
5 Correct 320 ms 23724 KB Output is correct
6 Correct 294 ms 22648 KB Output is correct
7 Correct 324 ms 23752 KB Output is correct
8 Correct 308 ms 22804 KB Output is correct
9 Correct 289 ms 22240 KB Output is correct
10 Correct 301 ms 22784 KB Output is correct
11 Correct 304 ms 22988 KB Output is correct
12 Correct 267 ms 22096 KB Output is correct
13 Correct 295 ms 22600 KB Output is correct
14 Correct 306 ms 23136 KB Output is correct
15 Correct 303 ms 23208 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 220 ms 22316 KB Output is correct
18 Correct 254 ms 22096 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3010 ms 25680 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 5384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 24084 KB Output is correct
2 Correct 326 ms 23904 KB Output is correct
3 Correct 324 ms 22864 KB Output is correct
4 Correct 292 ms 22232 KB Output is correct
5 Correct 320 ms 23724 KB Output is correct
6 Correct 294 ms 22648 KB Output is correct
7 Correct 324 ms 23752 KB Output is correct
8 Correct 308 ms 22804 KB Output is correct
9 Correct 289 ms 22240 KB Output is correct
10 Correct 301 ms 22784 KB Output is correct
11 Correct 304 ms 22988 KB Output is correct
12 Correct 267 ms 22096 KB Output is correct
13 Correct 295 ms 22600 KB Output is correct
14 Correct 306 ms 23136 KB Output is correct
15 Correct 303 ms 23208 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 220 ms 22316 KB Output is correct
18 Correct 254 ms 22096 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Execution timed out 3010 ms 25680 KB Time limit exceeded
22 Halted 0 ms 0 KB -