結果

問題 No.3305 Shift Sort
コンテスト
ユーザー alcea
提出日時 2025-10-05 15:45:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,321 bytes
コンパイル時間 2,092 ms
コンパイル使用メモリ 205,144 KB
実行使用メモリ 15,000 KB
最終ジャッジ日時 2025-10-05 15:46:12
合計ジャッジ時間 14,231 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,q;
  cin>>n>>q;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  int l[q],r[q];
  for(int i=0;i<q;i++){
    cin>>l[i]>>r[i];
    l[i]--;
  }
  vector<int> b(n);
  for(int i=0;i<n;i++) b[n-1-i]=a[i];
  vector<vector<int>> le(n);
  vector<int> ri(n,-1);
  for(int i=0;i<n;i++){
    int fr=upper_bound(b.begin()+n-1-i,b.end(),a[i])-b.begin();
    if(fr!=n){
      fr=n-1-fr;
      ri[i]=fr;
      le[fr].push_back(i+1);
    }
  }
  /*for(int i=0;i<n;i++){
    for(int e:le[i]) cerr<<i<<" "<<e<<endl;
  }*/
  int m=sqrt(n)+5;
  int idx[q];
  iota(idx,idx+q,0);
  sort(idx,idx+q,[&](int i,int j){
    if(l[i]/m!=l[j]/m) return l[i]<l[j];
    else return r[i]<r[j];
  });
  int answer[q];
  int nl=0,nr=0,ans=0;
  for(int i:idx){
    while(nr<r[i]){
      ans+=nl<=ri[nr];
      nr++;
    }
    while(r[i]<nr){
      nr--;
      ans-=nl<=ri[nr];
    }
    while(nl>l[i]){
      nl--;
      ans+=upper_bound(le[nl].begin(),le[nl].end(),nr)-le[nl].begin();
    }
    while(nl<l[i]){
      ans-=upper_bound(le[nl].begin(),le[nl].end(),nr)-le[nl].begin();
      //cerr<<upper_bound(le[nl].begin(),le[nl].end(),nr)-le[nl].begin()<<endl;
      nl++;
    }
    answer[i]=ans;
    //cerr<<i<<" "<<l[i]<<" "<<r[i]<<endl;
  }
  for(int i=0;i<q;i++) cout<<answer[i]<<endl;
}
0