oj.uz

Submission #1071801

# Submission time Handle Problem Language Result Execution time Memory
1071801 2024-08-23T11:25:33 Z ezzzay Index (COCI21_index) C++14
60 / 110
 2500 ms 80096 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=2e5+15;
int L[N],R[N];
int a[N];
vector<int>ans;
vector<int>st[N*4];
void merge(int x){
    st[x].clear();
   int i=0,j=0;
   while(1){
       if(i==st[x*2].size() and j==st[x*2+1].size()){
           break;
       }
       if(i==st[x*2].size()){
           st[x].pb(st[x*2+1][j]);
           j++;
       }
       else if(j==st[x*2+1].size()){
           st[x].pb(st[x*2][i]);
           i++;
       }
       else if(st[x*2][i]<st[x*2+1][j]){
           st[x].pb(st[x*2][i]);
           i++;
       }
       else {
           st[x].pb(st[x*2+1][j]);
           j++;
       }
   }
}
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));
}
map<pair<int,int>,int>mp;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    int g=0;
    set<int>st;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st.insert(a[i]);
        g=max(a[i],g);
    }
    build(1,1,n);
    while(q--){
        int l,r;
        cin>>l>>r;
        if(mp[{l,r}]){
            ans.pb(mp[{l,r}]);
            continue;
        }
        int lo=0,hi=min(r-l+1,g);
        
        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;
            }
        }
        mp[{l,r}]=hi;
        ans.pb(hi);
    }
    for(auto p:ans)cout<<p<<'\n';
}

Compilation message

index.cpp: In function 'void merge(long long int)':
index.cpp:16:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |        if(i==st[x*2].size() and j==st[x*2+1].size()){
      |           ~^~~~~~~~~~~~~~~~
index.cpp:16:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |        if(i==st[x*2].size() and j==st[x*2+1].size()){
      |                                 ~^~~~~~~~~~~~~~~~~~
index.cpp:19:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |        if(i==st[x*2].size()){
      |           ~^~~~~~~~~~~~~~~~
index.cpp:23:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |        else if(j==st[x*2+1].size()){
      |                ~^~~~~~~~~~~~~~~~~~
index.cpp: In function 'long long int check(long long int, long long int)':
index.cpp:50:9: warning: unused variable 'p' [-Wunused-variable]
   50 |     int p=0;
      |         ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21340 KB Output is correct
2 Correct 7 ms 21364 KB Output is correct
3 Correct 7 ms 21340 KB Output is correct
4 Correct 7 ms 21340 KB Output is correct
5 Correct 7 ms 21340 KB Output is correct
6 Correct 7 ms 21336 KB Output is correct
7 Correct 6 ms 21340 KB Output is correct
8 Correct 6 ms 21336 KB Output is correct
9 Correct 6 ms 21340 KB Output is correct
10 Correct 7 ms 21340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21340 KB Output is correct
2 Correct 7 ms 21364 KB Output is correct
3 Correct 7 ms 21340 KB Output is correct
4 Correct 7 ms 21340 KB Output is correct
5 Correct 7 ms 21340 KB Output is correct
6 Correct 7 ms 21336 KB Output is correct
7 Correct 6 ms 21340 KB Output is correct
8 Correct 6 ms 21336 KB Output is correct
9 Correct 6 ms 21340 KB Output is correct
10 Correct 7 ms 21340 KB Output is correct
11 Correct 571 ms 36216 KB Output is correct
12 Correct 586 ms 36040 KB Output is correct
13 Correct 568 ms 36044 KB Output is correct
14 Correct 559 ms 36028 KB Output is correct
15 Correct 559 ms 36300 KB Output is correct
16 Correct 556 ms 36044 KB Output is correct
17 Correct 564 ms 36020 KB Output is correct
18 Correct 573 ms 36360 KB Output is correct
19 Correct 560 ms 36132 KB Output is correct
20 Correct 579 ms 36040 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21340 KB Output is correct
2 Correct 7 ms 21364 KB Output is correct
3 Correct 7 ms 21340 KB Output is correct
4 Correct 7 ms 21340 KB Output is correct
5 Correct 7 ms 21340 KB Output is correct
6 Correct 7 ms 21336 KB Output is correct
7 Correct 6 ms 21340 KB Output is correct
8 Correct 6 ms 21336 KB Output is correct
9 Correct 6 ms 21340 KB Output is correct
10 Correct 7 ms 21340 KB Output is correct
11 Correct 571 ms 36216 KB Output is correct
12 Correct 586 ms 36040 KB Output is correct
13 Correct 568 ms 36044 KB Output is correct
14 Correct 559 ms 36028 KB Output is correct
15 Correct 559 ms 36300 KB Output is correct
16 Correct 556 ms 36044 KB Output is correct
17 Correct 564 ms 36020 KB Output is correct
18 Correct 573 ms 36360 KB Output is correct
19 Correct 560 ms 36132 KB Output is correct
20 Correct 579 ms 36040 KB Output is correct
21 Execution timed out 2535 ms 80096 KB Time limit exceeded
22 Halted 0 ms 0 KB -