oj.uz

Submission #969429

# Submission time Handle Problem Language Result Execution time Memory
969429 2024-04-25T06:52:02 Z AliHasanli Index (COCI21_index) C++17
60 / 110
 909 ms 12376 KB 
#include<bits/stdc++.h>
using namespace std;
int a[50005];
vector<int>seg[200005];
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 10 ms 5212 KB Output is correct
2 Correct 11 ms 5212 KB Output is correct
3 Correct 8 ms 5148 KB Output is correct
4 Correct 8 ms 5212 KB Output is correct
5 Correct 9 ms 5212 KB Output is correct
6 Correct 8 ms 5212 KB Output is correct
7 Correct 8 ms 5212 KB Output is correct
8 Correct 11 ms 5212 KB Output is correct
9 Correct 8 ms 5212 KB Output is correct
10 Correct 10 ms 5208 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5212 KB Output is correct
2 Correct 11 ms 5212 KB Output is correct
3 Correct 8 ms 5148 KB Output is correct
4 Correct 8 ms 5212 KB Output is correct
5 Correct 9 ms 5212 KB Output is correct
6 Correct 8 ms 5212 KB Output is correct
7 Correct 8 ms 5212 KB Output is correct
8 Correct 11 ms 5212 KB Output is correct
9 Correct 8 ms 5212 KB Output is correct
10 Correct 10 ms 5208 KB Output is correct
11 Correct 884 ms 11976 KB Output is correct
12 Correct 890 ms 11920 KB Output is correct
13 Correct 900 ms 11908 KB Output is correct
14 Correct 891 ms 12104 KB Output is correct
15 Correct 888 ms 11892 KB Output is correct
16 Correct 875 ms 11976 KB Output is correct
17 Correct 884 ms 12120 KB Output is correct
18 Correct 909 ms 12376 KB Output is correct
19 Correct 886 ms 12140 KB Output is correct
20 Correct 889 ms 11892 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5212 KB Output is correct
2 Correct 11 ms 5212 KB Output is correct
3 Correct 8 ms 5148 KB Output is correct
4 Correct 8 ms 5212 KB Output is correct
5 Correct 9 ms 5212 KB Output is correct
6 Correct 8 ms 5212 KB Output is correct
7 Correct 8 ms 5212 KB Output is correct
8 Correct 11 ms 5212 KB Output is correct
9 Correct 8 ms 5212 KB Output is correct
10 Correct 10 ms 5208 KB Output is correct
11 Correct 884 ms 11976 KB Output is correct
12 Correct 890 ms 11920 KB Output is correct
13 Correct 900 ms 11908 KB Output is correct
14 Correct 891 ms 12104 KB Output is correct
15 Correct 888 ms 11892 KB Output is correct
16 Correct 875 ms 11976 KB Output is correct
17 Correct 884 ms 12120 KB Output is correct
18 Correct 909 ms 12376 KB Output is correct
19 Correct 886 ms 12140 KB Output is correct
20 Correct 889 ms 11892 KB Output is correct
21 Runtime error 15 ms 10844 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -