Submission #2576991

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)

struct RSQ{
  int n=(1<<17),data[(1<<18)];
  RSQ(){
    memset(data,0,sizeof(data));
  }
  // 0 index
  void add(int i,int v){
    i++;
    while(i<=n){
      data[i]+=v;
      i+=i&-i;
    }
  }
  int sum(int i){
    int res=0;
    while(i>0){
      res+=data[i];
      i-=i&-i;
    }
    return res;
  }
  //[a,b) 0indexed
  int sum(int x,int y){
    return sum(y)-sum(x);
  }
  //K番目に小さい値
  int K_number(int k){
    int l = 0,r = (1<<18)+1;
    while( l < r ) {
      int mid = (l+r) / 2;
      if( sum( 1 , mid+1 ) >= k ) r = mid;
      else l = mid+1;
    }
    return l;
  }
};

int main(){
    int n,k;
    cin>>n>>k;
    int a[n];
    map<int,int>m;
    r(i,n)cin>>a[i],m[a[i]]=i+1;
    RSQ R;
    for(int i=0;i<k-1;i++)R.add(a[i],1);
    for(int i=k-1;i<n;i++){
        R.add(a[i],1);
        cout<<m[R.K_number(k)]<<endl;
    }
}

Submission Info

Judge Result