結果
問題 |
No.3305 Shift Sort
|
ユーザー |
![]() |
提出日時 | 2025-10-05 15:56:27 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 557 ms / 2,000 ms |
コード長 | 2,216 bytes |
コンパイル時間 | 925 ms |
コンパイル使用メモリ | 107,932 KB |
実行使用メモリ | 15,780 KB |
最終ジャッジ日時 | 2025-10-05 15:57:17 |
合計ジャッジ時間 | 12,598 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; template <typename T> class segTree { private: const T e; int num; std::vector<T> dat; T (*const eval)(T &, T &) {}; public: segTree(std::vector<T> &v, T E, T (*func)(T &, T &)) : e(E), eval(func) { int siz = static_cast<int>(v.size()); for (num = 1; num < siz; num <<= 1); dat = std::vector<T> (2 * num - 1, e); for (int i = 0; i < siz; ++i) dat[i + num - 1] = v[i]; for (int i = num - 2; i >= 0; --i) dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]); } segTree(int n, T E, T (*func)(T &, T &)) : e(E), eval(func) { for (num = 1; num < n; num <<= 1); dat = std::vector<T> (2 * num - 1, e); } void update_a(int i, T val) { for (i += num - 1, dat[i] = val; i != 0;) { i = (i - 1) / 2; dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]); } } void update_r(int i, T val) { for (i += num - 1, dat[i] = eval(dat[i], val); i != 0;) { i = (i - 1) / 2; dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]); } } T getval(int left, int right) { left = std::max(0, left), right = std::min(num, right); T ansl = e, ansr = e; for (left += num - 1, right += num - 1; left < right; left >>= 1, right >>= 1) { if (!(left & 1)) ansl = eval(ansl, dat[left]); if (--right & 1) ansr = eval(dat[right], ansr); } return eval(ansl, ansr); } T getval(int id) {return dat[num - 1 + id];} }; int main() { int n, q; cin >> n >> q; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; vector<vector<pair<int, int>>> qu(n); for (int i = 0; i < q; ++i) { int l, r; cin >> l >> r; --l; qu[l].push_back({r, i}); } segTree<int> sg(n, 0, [](int &a, int &b) -> int {return a + b;}); vector<pair<int, int>> st; vector<int> ans(q); for (int i = n - 1; i >= 0; --i) { while (!st.empty() && st.back().first < a[i]) { sg.update_a(st.back().second, 0); st.pop_back(); } sg.update_a(i, 1); st.push_back({a[i], i}); for (auto [r, id] : qu[i]) { ans[id] = r - i - sg.getval(i, r); } } for (int i = 0; i < q; ++i) cout << ans[i] << endl; }