Submission #751229

#	Time	Username	Problem	Language	Result	Execution time	Memory
751229		bgnbvnbv	Index (COCI21_index)	C++14	110 / 110	2272 ms	23608 KiB

index

#include<bits/stdc++.h>
#define pli pair<long long,long long>
using namespace std;
using ll=long long;
const ll maxN=3e5+5;
ll n, a[maxN],id[maxN],st[4*maxN];
void build(ll id, ll l, ll r)
{
    if(l==r)
    {
        st[id]=0;
        return;
    }
    ll mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
void update(ll id, ll l, ll r, ll pos, ll val)
{
    if(pos<l||pos>r) return;
    if(l==r)
    {
        st[id]=val;
        return;
    }
    ll mid=(l+r)/2;
    update(id*2,l,mid,pos,val);
    update(id*2+1,mid+1,r,pos,val);
    st[id]=st[id*2]+st[id*2+1];
}
ll get(ll id, ll l, ll r, ll i, ll j)
{
    if(r<i||j<l) return 0;
    if(i<=l&&r<=j)
    {
        return st[id];
    }
    ll mid=(l+r)/2;
    return get(id*2,l,mid,i,j)+get(id*2+1,mid+1,r,i,j);
}
bool lf(ll x, ll y)
{
    return a[x]>a[y];
}
struct TQuery
{
    ll l, r, mid, low, high;
}q[maxN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int que;
    cin >> n>> que;
    for(int i=1;i<=n;i++) cin >> a[i],id[i]=i;
    sort(id+1,id+n+1,lf);
    //for(int i=1;i<=n;i++) cout << id[i]<<' ';
    for(int i=1;i<=que;i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].low=1;
        q[i].high=q[i].r-q[i].l+1;
    }
    vector<pli> v;
    while(true)
    {
        v.clear();
        build(1,1,n);
        for(int i=1;i<=que;i++)
        {
            if(q[i].low>q[i].high)
            {
                continue;
            }
            else
            {
                q[i].mid=(q[i].low+q[i].high)/2;
                v.push_back({q[i].mid,i});
            }
        }
        if(v.size()==0) break;
        sort(v.begin(),v.end(),greater<pli>());
        int j=1;
        for(int i=0;i<v.size();i++)
        {
            while(a[id[j]]>=v[i].first)
            {
                update(1,1,n,id[j],1);
                j++;
            }
            ll idx=v[i].second;
            ll x=get(1,1,n,q[idx].l,q[idx].r);
            if(x>=q[idx].mid) q[idx].low=q[idx].mid+1;
            else q[idx].high=q[idx].mid-1;

        }
    }
    for(int i=1;i<=que;i++)
    {
        cout << q[i].high<<'\n';
    }
}

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int i=0;i<v.size();i++)
      |                     ~^~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50