結果
| 問題 |
No.3305 Shift Sort
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2025-10-07 16:48:03 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 150 ms / 2,000 ms |
| コード長 | 1,421 bytes |
| コンパイル時間 | 4,793 ms |
| コンパイル使用メモリ | 262,140 KB |
| 実行使用メモリ | 8,064 KB |
| 最終ジャッジ日時 | 2025-10-07 16:48:14 |
| 合計ジャッジ時間 | 10,181 ms |
|
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)
template <class T> bool chmin(T& x, T y) {
return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
return x < y ? (x = y, true) : false;
}
struct io_setup {
io_setup() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} io_setup;
using mint = atcoder::modint998244353;
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n);
rep(i, 0, n) cin >> a[i];
reverse(a.begin(), a.end());
vector<int> l(q), r(q);
rep(i, 0, q) cin >> l[i] >> r[i];
rep(i, 0, q) l[i]--;
rep(i, 0, q) {
l[i] = n - l[i];
r[i] = n - r[i];
}
swap(l, r);
vector<int> p(q);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j) {
if (r[i] == r[j]) return l[i] < l[j];
return r[i] < r[j];
});
int nr = 0;
atcoder::fenwick_tree<int> ft(n);
set<pair<int, int>> st;
vector<int> ans(q);
for (int i : p) {
while (nr < r[i]) {
while (!st.empty() && st.begin()->first < a[nr]) {
ft.add(st.begin()->second, -1);
st.erase(st.begin());
}
ft.add(nr, 1);
st.insert({a[nr], nr});
nr++;
}
ans[i] = r[i] - l[i] - ft.sum(l[i], r[i]);
}
rep(i, 0, q) cout << ans[i] << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) solve();
}