結果

問題 No.3305 Shift Sort
ユーザー alcea
提出日時 2025-10-05 16:19:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 725 ms / 2,000 ms
コード長 1,406 bytes
コンパイル時間 3,812 ms
コンパイル使用メモリ 258,564 KB
実行使用メモリ 17,928 KB
最終ジャッジ日時 2025-10-05 16:20:29
合計ジャッジ時間 17,371 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int op(int x,int y){
  return max(x,y);
}
int e(){
  return -1;
}
int main(){
  int n,q;
  cin>>n>>q;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i],a[i]--;
  int l[q],r[q];
  for(int i=0;i<q;i++){
    cin>>l[i]>>r[i];
    l[i]--;
  }
  segtree<int,op,e> seg(n);
  vector<vector<int>> le(n);
  vector<int> ri(n,-1);
  for(int i=0;i<n;i++){
    int fr=seg.prod(a[i],n);
    if(fr>=0){
      ri[i]=fr;
      le[fr].push_back(i+1);
    }
    seg.set(a[i],i);
  }
  /*cerr<<"!";
  for(int i=0;i<n;i++){
    for(int e:le[i]) cerr<<i<<" "<<e<<endl;
  }
  cerr<<"!";*/
  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