Submission #943777

#	Time	Username	Problem	Language	Result	Execution time	Memory
943777		Ahmed57	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	1733 ms	50420 KiB

Main

#include "bits/stdc++.h"
 
using namespace std;
#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#endif
int n;
int bit[1000001];
void add(int e,int v){
    while(e<=n){
        bit[e]+=v;
        e+=e&-e;
    }
}
int sum(int e){
    int su = 0;
    while(e>=1){
        su+=bit[e];
        e-=e&-e;
    }
    return su;
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int q;
    cin>>n>>q;
    int arr[n+1],pos[n+1];
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
        pos[arr[i]] = i;
    }
    int nxt[n+1];
    stack<int> st;
    for(int i = n;i>=1;i--){
        while(!st.empty()&&arr[i]>=arr[st.top()])st.pop();
        if(st.size())nxt[i] = st.top();
        else nxt[i] = n+1;
        st.push(i);
    }
    int cur = 1;
    set<int> s;
    while(cur<=n){
        s.insert(cur);
        add(arr[cur],nxt[cur]-cur);
        cur = nxt[cur];
    }
    std::vector<array<int,3>> qu;
    for(int i = 1;i<=q;i++){
        int a,b;
        cin>>a>>b;
        a = min(a,n);
        qu.push_back({a,b,i});
    }sort(qu.begin(),qu.end());
    int level = 0;
    int ANS[q+1];
    for(int i = 0;i<qu.size();i++){
        while(level<qu[i][0]){
            int no = n/2+1;
            int l = 1 , r = n , ans = 0;
            while(l<=r){
                int mid = (l+r)/2;
                if(sum(mid)>=no){
                    ans = mid;
                    r = mid-1;
                }else l = mid+1;
            }
            int po = pos[ans]+(no-sum(ans-1)-1);
            no = po;
            auto it = s.lower_bound(no);
            int en = n+1;
            if(it!=s.end()){
                en = (*it);
            }
            if(it==s.end()||(*it)!=no){
                it--;
                add(arr[(*it)],(-(en-(*it))) +(no-(*it)));
            }
            while(no<=n){
                auto it = s.lower_bound(no);
                if(it==s.end()||(*it)!=no){
                    int nx = nxt[no];
                    auto lol = s.lower_bound(no);
                    if(lol!=s.end()){
                        nx = min(nx,(*lol));
                    }
                    s.insert(no);
                    add(arr[no],nx-no);
                    no = nx;
                }else break;
            }
            level++;
        }
        int l = 1 , r = n , ans = 0;
        while(l<=r){
            int mid = (l+r)/2;
            if(sum(mid)>=qu[i][1]){
                ans = mid;
                r = mid-1;
            }else l = mid+1;
        }
        ANS[qu[i][2]] = arr[pos[ans]+(qu[i][1]-sum(ans-1)-1)];
    }
    for(int i = 1;i<=q;i++)cout<<ANS[i]<<endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i = 0;i<qu.size();i++){
      |                   ~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25