Submission #1190820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190820		dzuizz	Index (COCI21_index)	C++20	110 / 110	621 ms	10852 KiB

index

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
constexpr int N=200005,Q=200005,S=447;
int bit[N],p[N],v[Q];
int maxp,n,q,l,r=-1,lf,rg,mid;
int sum(int idx){
  int ret=0;
  for(;idx>0;idx-=idx&-idx) ret+=bit[idx];
  return ret;
}
int sum(int l,int r){ return sum(r)-sum(l-1); }
void add(int idx,int v){ for(;idx<=maxp;idx+=idx&-idx) bit[idx]+=v; }
signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin>>n>>q;
  for(int i=0;i<n;++i)
    cin>>p[i],maxp=max(maxp,p[i]);
  pair<pair<int,int>,int> qry[q];
  for(int i=0;i<q;++i){
    cin>>qry[i].first.first>>qry[i].first.second;
    --qry[i].first.first,--qry[i].first.second;
    qry[i].second=i;
  }
  sort(qry,qry+q,[&](const pair<pair<int,int>,int>&a,const pair<pair<int,int>,int>&b){ return a.f.f/S==b.f.f/S?(a.f.f/S)&1?a.f.s>b.f.s:a.f.s<b.f.s:a.f.f<b.f.f; });
  for(auto&qr:qry){
    auto [nl,nr]=qr.first;
    while(l>nl) add(p[--l],1);
    while(r<nr) add(p[++r],1);
    while(l<nl) add(p[l++],-1);
    while(r>nr) add(p[r--],-1);
    lf=1,rg=maxp;
    while(lf<=rg){
      mid=(lf+rg)>>1;
      if(sum(mid,maxp)>=mid) v[qr.second]=mid,lf=mid+1;
      else rg=mid-1;
    }
  }
  for(int i=0;i<q;++i)
    cout<<v[i]<<'\n';
  return 0;
}

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