Submission #1190796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190796		dzuizz	Index (COCI21_index)	C++20	0 / 110	14 ms	320 KiB

index

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N=2e5+5,s=500;
int P[N],fw[N];
int n,q,maxp;
pair<pair<int,int>,int> qry[N];
int sum(int idx){
  int ret=0;
  for(; idx>0; idx-=idx&-idx) ret+=fw[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) { fw[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]);
  }
  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.first.first/s==b.first.first/s?(a.first.first/s)&1?a.first.second>b.first.second:a.first.second<b.first.second:a.first.first<b.first.first;
  });
  int l=0,r=-1;
  int ans[q];
  for(auto&[lr,i]:qry){
    auto&[nl,nr]=lr;
    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);
    int lf=1,rg=maxp;
    while(lf<rg){
      int mid=(lf+rg+1)>>1;
      if(sum(mid,maxp)>=mid) lf=mid;
      else rg=mid-1;
    }
    ans[i]=lf;
  }
  for(auto&x:ans)cout<<x<<'\n';
  return 0;
}

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