oj.uz

Submission #943776

# Submission time Handle Problem Language Result Execution time Memory
943776 2024-03-11T21:33:52 Z Ahmed57 Abracadabra (CEOI22_abracadabra) C++17
35 / 100
 1445 ms 27400 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){
                    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

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

# Verdict Execution time Memory Grader output
1 Correct 1445 ms 26264 KB Output is correct
2 Correct 1401 ms 27400 KB Output is correct
3 Correct 1331 ms 26596 KB Output is correct
4 Correct 1316 ms 25512 KB Output is correct
5 Correct 1413 ms 27156 KB Output is correct
6 Correct 1321 ms 25484 KB Output is correct
7 Correct 1401 ms 27196 KB Output is correct
8 Correct 1317 ms 25960 KB Output is correct
9 Correct 1307 ms 25492 KB Output is correct
10 Correct 1330 ms 25776 KB Output is correct
11 Correct 1340 ms 26288 KB Output is correct
12 Correct 1314 ms 24956 KB Output is correct
13 Correct 1373 ms 26748 KB Output is correct
14 Correct 1347 ms 26456 KB Output is correct
15 Correct 1390 ms 26904 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1307 ms 25300 KB Output is correct
18 Correct 1309 ms 24748 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 6748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 10180 KB Output is correct
2 Correct 211 ms 10820 KB Output is correct
3 Correct 199 ms 10328 KB Output is correct
4 Correct 182 ms 6088 KB Output is correct
5 Correct 190 ms 7764 KB Output is correct
6 Correct 169 ms 6232 KB Output is correct
7 Correct 185 ms 7112 KB Output is correct
8 Correct 166 ms 6596 KB Output is correct
9 Correct 177 ms 7288 KB Output is correct
10 Correct 171 ms 5576 KB Output is correct
11 Correct 158 ms 5768 KB Output is correct
12 Correct 159 ms 5576 KB Output is correct
13 Correct 173 ms 5900 KB Output is correct
14 Correct 161 ms 5576 KB Output is correct
15 Correct 162 ms 5596 KB Output is correct
16 Correct 9 ms 2648 KB Output is correct
17 Correct 183 ms 10492 KB Output is correct
18 Correct 152 ms 4944 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1445 ms 26264 KB Output is correct
2 Correct 1401 ms 27400 KB Output is correct
3 Correct 1331 ms 26596 KB Output is correct
4 Correct 1316 ms 25512 KB Output is correct
5 Correct 1413 ms 27156 KB Output is correct
6 Correct 1321 ms 25484 KB Output is correct
7 Correct 1401 ms 27196 KB Output is correct
8 Correct 1317 ms 25960 KB Output is correct
9 Correct 1307 ms 25492 KB Output is correct
10 Correct 1330 ms 25776 KB Output is correct
11 Correct 1340 ms 26288 KB Output is correct
12 Correct 1314 ms 24956 KB Output is correct
13 Correct 1373 ms 26748 KB Output is correct
14 Correct 1347 ms 26456 KB Output is correct
15 Correct 1390 ms 26904 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1307 ms 25300 KB Output is correct
18 Correct 1309 ms 24748 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Runtime error 16 ms 6748 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -