結果
| 問題 |
No.3305 Shift Sort
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 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 |
ソースコード
#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;
}