oj.uz

Submission #918786

# Submission time Handle Problem Language Result Execution time Memory
918786 2024-01-30T12:36:26 Z JakobZorz Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 24372 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;

int n;
int l[200001];
int r[200001];
vector<int>init;

void insert(int a,int b){
    l[init[a]]=a;
    r[init[a]]=b;
}

pair<int,int>get(int sum){
    for(int i=0;i<=n;i++){
        sum-=r[i]-l[i];
        if(sum<0)
            return{i,sum+r[i]-l[i]};
    }
    abort();
}

void solve(){
    int q;
    cin>>n>>q;
    init.resize(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<pair<int,int>>>qrs(n+1);
    vector<int>ans(q,-1);
    for(int i=0;i<q;i++){
        int t,qi;
        cin>>t>>qi;
        t=min(t,n);
        qrs[t].push_back({qi-1,i});
    }
    
    for(int curr=0;curr<n;){
        insert(curr,nxt[curr]);
        curr=nxt[curr];
    }
    
    for(int round=0;round<=n;round++){
        for(auto i:qrs[round]){
            auto res=get(i.first);
            
            ans[i.second]=init[l[res.first]+res.second];
        }
        
        auto res=get(n/2);
        
        if(res.second==0)
            continue;
        
        int nl=l[res.first]+res.second;
        int nr=r[res.first];
        insert(l[res.first],nl);
        
        for(int curr=nl;curr<nr;){
            int nx=min(nxt[curr],nr);
            insert(curr,nx);
            curr=nx;
        }
    }
    
    for(int i:ans){
        if(i==-1)
            abort();
        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 6
1 4 2 3 5 6
0 1
0 2
0 3
0 4
0 5
0 6

1
4
2
3
5
6
 
4 4
4 3 2 1
0 1
0 2
0 3
0 4
 
4
3
2
1

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
 
6 6
4 5 6 1 2 3
10 1
10 2
10 3
10 4
10 5
10 6
 
1
2
3
4
5
6
 
10 10
5 4 3 10 9 8 7 6 2 1
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
 
1
2
5
4
3
6
8
7
10
9
 
 */

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 18564 KB Output is correct
2 Correct 465 ms 21328 KB Output is correct
3 Correct 460 ms 20948 KB Output is correct
4 Correct 674 ms 19420 KB Output is correct
5 Correct 717 ms 22744 KB Output is correct
6 Correct 666 ms 23132 KB Output is correct
7 Correct 700 ms 24372 KB Output is correct
8 Correct 638 ms 22096 KB Output is correct
9 Correct 653 ms 21100 KB Output is correct
10 Correct 633 ms 20688 KB Output is correct
11 Correct 671 ms 21328 KB Output is correct
12 Correct 660 ms 18804 KB Output is correct
13 Correct 656 ms 19760 KB Output is correct
14 Correct 669 ms 22280 KB Output is correct
15 Correct 692 ms 20640 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 422 ms 18904 KB Output is correct
18 Correct 615 ms 18816 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3026 ms 19396 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 3053 ms 6276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 18564 KB Output is correct
2 Correct 465 ms 21328 KB Output is correct
3 Correct 460 ms 20948 KB Output is correct
4 Correct 674 ms 19420 KB Output is correct
5 Correct 717 ms 22744 KB Output is correct
6 Correct 666 ms 23132 KB Output is correct
7 Correct 700 ms 24372 KB Output is correct
8 Correct 638 ms 22096 KB Output is correct
9 Correct 653 ms 21100 KB Output is correct
10 Correct 633 ms 20688 KB Output is correct
11 Correct 671 ms 21328 KB Output is correct
12 Correct 660 ms 18804 KB Output is correct
13 Correct 656 ms 19760 KB Output is correct
14 Correct 669 ms 22280 KB Output is correct
15 Correct 692 ms 20640 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 422 ms 18904 KB Output is correct
18 Correct 615 ms 18816 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Execution timed out 3026 ms 19396 KB Time limit exceeded
22 Halted 0 ms 0 KB -