oj.uz

Submission #918714

# Submission time Handle Problem Language Result Execution time Memory
918714 2024-01-30T09:52:13 Z JakobZorz Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 32268 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);
    for(int&i:init)
        cin>>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;
    int prev=0;
    for(int i=1;i<n;i++){
        if(init[i]>init[prev]){
            s.insert({init[prev],{prev,i}});
            prev=i;
        }
    }
    s.insert({init[prev],{prev,n}});
    
    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 321 ms 27884 KB Output is correct
2 Correct 316 ms 27220 KB Output is correct
3 Correct 304 ms 26620 KB Output is correct
4 Correct 281 ms 25236 KB Output is correct
5 Correct 306 ms 27024 KB Output is correct
6 Correct 286 ms 25424 KB Output is correct
7 Correct 312 ms 27220 KB Output is correct
8 Correct 286 ms 25680 KB Output is correct
9 Correct 288 ms 25424 KB Output is correct
10 Correct 291 ms 25660 KB Output is correct
11 Correct 297 ms 25784 KB Output is correct
12 Correct 258 ms 24464 KB Output is correct
13 Correct 290 ms 25680 KB Output is correct
14 Correct 294 ms 26196 KB Output is correct
15 Correct 290 ms 26244 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 232 ms 24948 KB Output is correct
18 Correct 247 ms 24660 KB Output is correct
19 Correct 0 ms 544 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 32268 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 3020 ms 6064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 27884 KB Output is correct
2 Correct 316 ms 27220 KB Output is correct
3 Correct 304 ms 26620 KB Output is correct
4 Correct 281 ms 25236 KB Output is correct
5 Correct 306 ms 27024 KB Output is correct
6 Correct 286 ms 25424 KB Output is correct
7 Correct 312 ms 27220 KB Output is correct
8 Correct 286 ms 25680 KB Output is correct
9 Correct 288 ms 25424 KB Output is correct
10 Correct 291 ms 25660 KB Output is correct
11 Correct 297 ms 25784 KB Output is correct
12 Correct 258 ms 24464 KB Output is correct
13 Correct 290 ms 25680 KB Output is correct
14 Correct 294 ms 26196 KB Output is correct
15 Correct 290 ms 26244 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 232 ms 24948 KB Output is correct
18 Correct 247 ms 24660 KB Output is correct
19 Correct 0 ms 544 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Execution timed out 3029 ms 32268 KB Time limit exceeded
22 Halted 0 ms 0 KB -