oj.uz

Submission #387516

# Submission time Handle Problem Language Result Execution time Memory
387516 2021-04-08T17:04:16 Z Pichon5 Index (COCI21_index) C++17
60 / 110
 920 ms 11744 KB 
#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second

//"\n"
using namespace std;
const int tam =50000;
vi T[4*tam];
vi v;
int cant=0;
void init(int nodo, int b, int e){
    int L=2*nodo+1,R=L+1,mid=(b+e)/2;
    if(b==e){
        T[nodo].pb(v[b]);
        return;
    }
    init(L,b,mid);init(R,mid+1,e);
    T[nodo].resize(T[L].size()+T[R].size());
    merge(T[L].begin(),T[L].end(),T[R].begin(),T[R].end(),T[nodo].begin());
}
void query(int nodo, int b, int e, int izq, int der, int h){
    int L=2*nodo+1,R=L+1,mid=(b+e)/2;
    if(b>=izq && e<=der){
        int pos=T[nodo].size();
        int B=0,E=T[nodo].size()-1;
        while(B<=E){
            int MID=(B+E)/2;
            if(T[nodo][MID]>=h){
                pos=MID;
                E=MID-1;
            }else{
                B=MID+1;
            }
        }
        cant+=T[nodo].size()-pos;
        return;
    }
    if(der<=mid){
        query(L,b,mid,izq,der,h);
        return;
    }
    if(izq>=mid+1){
        query(R,mid+1,e,izq,der,h);
        return;
    }
    query(L,b,mid,izq,der,h);query(R,mid+1,e,izq,der,h);
}
int main()
{
    int n,q,x;
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>x;
        v.pb(x);
    } 
    init(0,0,n-1);    
    int a,b;
    while(q--){
        cin>>a>>b;
        a--;b--;
        int iz=0,de=200005;
        int res=0;
        while(iz<=de){
            int mid=(iz+de)/2;
            cant=0;
            query(0,0,n-1,a,b,mid);
            if(cant>=mid){
                res=mid;
                iz=mid+1;
            }else{
                de=mid-1;
            }
        }
        cout<<res<<endl;
    }
    
    
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5100 KB Output is correct
2 Correct 14 ms 5100 KB Output is correct
3 Correct 12 ms 5100 KB Output is correct
4 Correct 12 ms 5100 KB Output is correct
5 Correct 12 ms 5100 KB Output is correct
6 Correct 12 ms 5100 KB Output is correct
7 Correct 13 ms 5100 KB Output is correct
8 Correct 12 ms 5100 KB Output is correct
9 Correct 12 ms 5100 KB Output is correct
10 Correct 12 ms 5100 KB Output is correct
11 Correct 906 ms 11252 KB Output is correct
12 Correct 920 ms 11248 KB Output is correct
13 Correct 902 ms 11220 KB Output is correct
14 Correct 911 ms 11228 KB Output is correct
15 Correct 890 ms 11112 KB Output is correct
16 Correct 896 ms 11112 KB Output is correct
17 Correct 904 ms 11112 KB Output is correct
18 Correct 885 ms 11188 KB Output is correct
19 Correct 887 ms 11368 KB Output is correct
20 Correct 907 ms 11076 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5100 KB Output is correct
2 Correct 14 ms 5100 KB Output is correct
3 Correct 12 ms 5100 KB Output is correct
4 Correct 12 ms 5100 KB Output is correct
5 Correct 12 ms 5100 KB Output is correct
6 Correct 12 ms 5100 KB Output is correct
7 Correct 13 ms 5100 KB Output is correct
8 Correct 12 ms 5100 KB Output is correct
9 Correct 12 ms 5100 KB Output is correct
10 Correct 12 ms 5100 KB Output is correct
11 Correct 906 ms 11252 KB Output is correct
12 Correct 920 ms 11248 KB Output is correct
13 Correct 902 ms 11220 KB Output is correct
14 Correct 911 ms 11228 KB Output is correct
15 Correct 890 ms 11112 KB Output is correct
16 Correct 896 ms 11112 KB Output is correct
17 Correct 904 ms 11112 KB Output is correct
18 Correct 885 ms 11188 KB Output is correct
19 Correct 887 ms 11368 KB Output is correct
20 Correct 907 ms 11076 KB Output is correct
21 Runtime error 72 ms 11744 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -