oj.uz

Submission #969430

# Submission time Handle Problem Language Result Execution time Memory
969430 2024-04-25T06:53:21 Z AliHasanli Index (COCI21_index) C++17
60 / 110
 2500 ms 46540 KB 
#include<bits/stdc++.h>
using namespace std;
int a[200005];
vector<int>seg[800005];
void build(int no,int l,int r)
{
    //cout<<"B "<<no<<" "<<l<<" "<<r<<endl;
    if(l==r){seg[no].push_back(a[l]);return;}
    build(2*no,l,(l+r)/2);
    build(2*no+1,(l+r)/2+1,r);
    seg[no].resize(seg[no*2].size()+seg[no*2+1].size());
    merge(seg[2*no+1].begin(), seg[2*no+1].end(), seg[2*no].begin(), seg[2*no].end(), seg[no].begin());
}
int query(int n,int l,int r,int ql,int qr,int h)
{
    //cout<<"A "<<n<<endl;
    if(l>r || ql>qr || r<ql || qr<l)return 0;
    if(ql<=l && r<=qr)
    {
        if(lower_bound(seg[n].begin(),seg[n].end(),h)==seg[n].end())return 0;
        int index=lower_bound(seg[n].begin(),seg[n].end(),h)-seg[n].begin();
        return seg[n].size()-index;
    }
    return query(2*n,l,(l+r)/2,ql,qr,h)+query(2*n+1,(l+r)/2+1,r,ql,qr,h);
}
int ans(int a,int b,int n)
{
    int answer=0;
    int l=1,r=200000;
    int mid;
    while(l<=r)
    {mid=(l+r)/2;
        //cout<<l<<" "<<r<<" "<<mid<<endl;
    if(query(1,1,n,a,b,mid)>=mid)
        answer=max(answer,mid),l=mid+1;
    else r=mid-1;
    }
    return answer;
}
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    build(1,1,n);
    //cout<<"C"<<endl;
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        cout<<ans(a,b,n)<<endl;
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19292 KB Output is correct
2 Correct 11 ms 19292 KB Output is correct
3 Correct 11 ms 19292 KB Output is correct
4 Correct 13 ms 19292 KB Output is correct
5 Correct 11 ms 19288 KB Output is correct
6 Correct 13 ms 19292 KB Output is correct
7 Correct 11 ms 19288 KB Output is correct
8 Correct 11 ms 19292 KB Output is correct
9 Correct 11 ms 19292 KB Output is correct
10 Correct 11 ms 19292 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19292 KB Output is correct
2 Correct 11 ms 19292 KB Output is correct
3 Correct 11 ms 19292 KB Output is correct
4 Correct 13 ms 19292 KB Output is correct
5 Correct 11 ms 19288 KB Output is correct
6 Correct 13 ms 19292 KB Output is correct
7 Correct 11 ms 19288 KB Output is correct
8 Correct 11 ms 19292 KB Output is correct
9 Correct 11 ms 19292 KB Output is correct
10 Correct 11 ms 19292 KB Output is correct
11 Correct 897 ms 25240 KB Output is correct
12 Correct 908 ms 25680 KB Output is correct
13 Correct 902 ms 25232 KB Output is correct
14 Correct 936 ms 25428 KB Output is correct
15 Correct 896 ms 25700 KB Output is correct
16 Correct 901 ms 25348 KB Output is correct
17 Correct 898 ms 25416 KB Output is correct
18 Correct 901 ms 25260 KB Output is correct
19 Correct 870 ms 25236 KB Output is correct
20 Correct 885 ms 25504 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19292 KB Output is correct
2 Correct 11 ms 19292 KB Output is correct
3 Correct 11 ms 19292 KB Output is correct
4 Correct 13 ms 19292 KB Output is correct
5 Correct 11 ms 19288 KB Output is correct
6 Correct 13 ms 19292 KB Output is correct
7 Correct 11 ms 19288 KB Output is correct
8 Correct 11 ms 19292 KB Output is correct
9 Correct 11 ms 19292 KB Output is correct
10 Correct 11 ms 19292 KB Output is correct
11 Correct 897 ms 25240 KB Output is correct
12 Correct 908 ms 25680 KB Output is correct
13 Correct 902 ms 25232 KB Output is correct
14 Correct 936 ms 25428 KB Output is correct
15 Correct 896 ms 25700 KB Output is correct
16 Correct 901 ms 25348 KB Output is correct
17 Correct 898 ms 25416 KB Output is correct
18 Correct 901 ms 25260 KB Output is correct
19 Correct 870 ms 25236 KB Output is correct
20 Correct 885 ms 25504 KB Output is correct
21 Execution timed out 2530 ms 46540 KB Time limit exceeded
22 Halted 0 ms 0 KB -