結果
問題 |
No.3305 Shift Sort
|
ユーザー |
|
提出日時 | 2025-10-09 05:24:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 630 ms / 2,000 ms |
コード長 | 1,356 bytes |
コンパイル時間 | 1,548 ms |
コンパイル使用メモリ | 137,448 KB |
実行使用メモリ | 19,904 KB |
最終ジャッジ日時 | 2025-10-09 05:24:25 |
合計ジャッジ時間 | 15,501 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <queue> #include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> #include <iomanip> #include <numeric> #include <atcoder/segtree> using namespace atcoder; using namespace std; using ll = long long; int op(int a, int b) { return min(a, b); } int e() { return ((int)1e9); } int op2(int a, int b) { return max(a, b); } int e2() { return 0; } int main() { int N, Q;cin >> N >> Q; vector<int> A(N+1, 0); vector<int> C(N+1, 0); for (int i = 1;i <= N;i++) { cin >> A[i]; C[A[i]]++; } for (int i = 1;i <= N;i++) C[i] += C[i-1]; vector<int> L(Q), R(Q); vector<vector<int>> EV(N+1); for (int i = 0;i < Q;i++) { cin >> L[i] >> R[i]; EV[L[i]].push_back(i); } segtree<int, op, e> MNSEG(A); segtree<int, op2, e2> MXSEG(A); deque<int> st; vector<int> RES(Q); for (int i = N;i >= 1;i--) { while (!st.empty() and A[st.front()] < A[i]) st.pop_front(); st.push_front(i); for (auto id : EV[i]) { int r = R[id]; int mn = MNSEG.prod(i,r+1); int mx = MXSEG.prod(i,r+1); int ok = 0; int ng = st.size(); while (ng - ok > 1) { int mid = (ok + ng) / 2; if (st.at(mid) <= r) { ok = mid; } else { ng = mid; } } int ov = (C[mx] - C[mn-1]) - (r-i+1); int res = (mx-mn) - ok - ov; RES[id] = res; } } for (int i = 0;i < Q;i++) cout << RES[i] << endl; }