oj.uz

Submission #1071797

# Submission time Handle Problem Language Result Execution time Memory
1071797 2024-08-23T11:24:48 Z ezzzay Index (COCI21_index) C++14
60 / 110
 2500 ms 76904 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int L[N],R[N];
int a[N];
vector<int>ans;
vector<int>st[N*4];
void merge(int x){
    st[x].clear();
    for(auto p:st[x*2])st[x].pb(p);
    for(auto p:st[x*2+1])st[x].pb(p);
    sort(st[x].begin(),st[x].end());
}
void build(int node, int L, int R){
    if(L==R){
        st[node].pb(a[L]);
        return;
    }
    int mid=(L+R)/2;
    build(node*2,L,mid);
    build(node*2+1,mid+1,R);
    merge(node);
}
int check(int val, int x){
    val--;
    auto it=upper_bound(st[x].begin(),st[x].end(),val);
    int p=0;
    return st[x].size()-(it-st[x].begin());
}
int find(int node, int L, int R, int l, int r, int val){
    if(r<L or R<l)return 0;
    if(l<=L and R<=r){
        return check(val,node);
    }
    int mid=(L+R)/2;
    return(find(node*2,L,mid,l,r,val)+find(node*2+1,mid+1,R,l,r,val));
}
signed main(){
    int n,q;
    cin>>n>>q;
    
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(q--){
        int l,r;
        cin>>l>>r;
        int lo=0,hi=1e9;
        while(hi>=lo){
            int mid=(hi+lo)/2;
            int k=find(1,1,n,l,r,mid);
            if(k>=mid){
                lo=mid+1;
            }
            else{
                hi=mid-1;
            }
        }
        ans.pb(hi);
    }
    for(auto p:ans)cout<<p<<endl;
}

Compilation message

index.cpp: In function 'long long int check(long long int, long long int)':
index.cpp:31:9: warning: unused variable 'p' [-Wunused-variable]
   31 |     int p=0;
      |         ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29272 KB Output is correct
2 Correct 11 ms 29276 KB Output is correct
3 Correct 11 ms 29276 KB Output is correct
4 Correct 14 ms 29276 KB Output is correct
5 Correct 12 ms 29312 KB Output is correct
6 Correct 15 ms 29276 KB Output is correct
7 Correct 15 ms 29476 KB Output is correct
8 Correct 11 ms 29276 KB Output is correct
9 Correct 11 ms 29276 KB Output is correct
10 Correct 10 ms 29480 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29272 KB Output is correct
2 Correct 11 ms 29276 KB Output is correct
3 Correct 11 ms 29276 KB Output is correct
4 Correct 14 ms 29276 KB Output is correct
5 Correct 12 ms 29312 KB Output is correct
6 Correct 15 ms 29276 KB Output is correct
7 Correct 15 ms 29476 KB Output is correct
8 Correct 11 ms 29276 KB Output is correct
9 Correct 11 ms 29276 KB Output is correct
10 Correct 10 ms 29480 KB Output is correct
11 Correct 709 ms 40180 KB Output is correct
12 Correct 679 ms 40436 KB Output is correct
13 Correct 654 ms 40136 KB Output is correct
14 Correct 674 ms 40208 KB Output is correct
15 Correct 674 ms 40140 KB Output is correct
16 Correct 680 ms 40132 KB Output is correct
17 Correct 665 ms 40140 KB Output is correct
18 Correct 649 ms 40136 KB Output is correct
19 Correct 672 ms 40136 KB Output is correct
20 Correct 649 ms 40136 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29272 KB Output is correct
2 Correct 11 ms 29276 KB Output is correct
3 Correct 11 ms 29276 KB Output is correct
4 Correct 14 ms 29276 KB Output is correct
5 Correct 12 ms 29312 KB Output is correct
6 Correct 15 ms 29276 KB Output is correct
7 Correct 15 ms 29476 KB Output is correct
8 Correct 11 ms 29276 KB Output is correct
9 Correct 11 ms 29276 KB Output is correct
10 Correct 10 ms 29480 KB Output is correct
11 Correct 709 ms 40180 KB Output is correct
12 Correct 679 ms 40436 KB Output is correct
13 Correct 654 ms 40136 KB Output is correct
14 Correct 674 ms 40208 KB Output is correct
15 Correct 674 ms 40140 KB Output is correct
16 Correct 680 ms 40132 KB Output is correct
17 Correct 665 ms 40140 KB Output is correct
18 Correct 649 ms 40136 KB Output is correct
19 Correct 672 ms 40136 KB Output is correct
20 Correct 649 ms 40136 KB Output is correct
21 Execution timed out 2548 ms 76904 KB Time limit exceeded
22 Halted 0 ms 0 KB -