oj.uz

답안 #943774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943774 2024-03-11T21:20:15 Z Ahmed57 Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 1419 ms 26956 KB 
#include "bits/stdc++.h"
 
using namespace std;
#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#endif
int n;
int bit[100001];
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){
                    s.insert(no);
                    add(arr[no],nxt[no]-no);
                    no = nxt[no];
                }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

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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1419 ms 26956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 6744 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 180 ms 7880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1419 ms 26956 KB Output isn't correct
2 Halted 0 ms 0 KB -