結果
| 問題 |
No.3305 Shift Sort
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2025-10-05 15:44:02 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 167 ms / 2,000 ms |
| コード長 | 1,083 bytes |
| コンパイル時間 | 2,594 ms |
| コンパイル使用メモリ | 291,320 KB |
| 実行使用メモリ | 27,976 KB |
| 最終ジャッジ日時 | 2025-10-05 15:44:11 |
| 合計ジャッジ時間 | 7,145 ms |
|
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#include<atcoder/fenwicktree>
using namespace atcoder;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll N,Q;
cin>>N>>Q;
vector<ll> P(N);
vector<ll> IP(N);
for(int i=0;i<N;i++){
cin>>P[i];
P[i]--;
IP[P[i]]=i;
}
vector<vector<array<ll,2>>> query(N);
for(int q=0;q<Q;q++){
ll L,R;
cin>>L>>R;
L--;
query[L].push_back({R,q});
}
priority_queue<array<ll,2>,vector<array<ll,2>>,greater<array<ll,2>>> PQ;
vector<vector<ll>> LZ(N);
for(ll i=N-1;i>=0;i--){
while(!PQ.empty()){
auto [n,id]=PQ.top();
if(n>P[i])break;
PQ.pop();
LZ[i].emplace_back(id);
}
PQ.push({P[i],i});
}
vector<ll> AN(Q);
fenwick_tree<ll> FW(N);
for(int i=N-1;i>=0;i--){
for(auto id:LZ[i])FW.add(id,1);
for(auto [R,id]:query[i]){
AN[id]=FW.sum(i,R);
}
}
for(int i=0;i<Q;i++)cout<<AN[i]<<"\n";
}