結果
問題 |
No.924 紲星
|
ユーザー |
|
提出日時 | 2025-08-31 21:56:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,352 bytes |
コンパイル時間 | 3,454 ms |
コンパイル使用メモリ | 294,340 KB |
実行使用メモリ | 31,100 KB |
最終ジャッジ日時 | 2025-08-31 21:57:03 |
合計ジャッジ時間 | 9,995 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 TLE * 1 -- * 10 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/segtree> template <class T = long long> class Compressor { private: std::vector<T> cc; bool sorted; public: Compressor() : sorted(false) {} Compressor(const std::vector<T>& a) { for (auto x : a) cc.push_back(x); build(); } void add(const T& x) { cc.push_back(x); sorted = false; } T operator[](int i) const { assert(sorted); return cc[i]; } int operator()(const T& x) const { assert(sorted); return lower_bound(begin(cc), end(cc), x) - begin(cc); } int size() const { assert(sorted); return cc.size(); } void build() { sort(begin(cc), end(cc)); cc.erase(unique(begin(cc), end(cc)), end(cc)); sorted = true; } static std::vector<int> compressed(const std::vector<T>& a) { Compressor c(a); std::vector<int> res(a.size()); for(int i = 0; i < (int)a.size(); i++) res[i] = c(a[i]); return res; } }; template <class T> class FixedSet { struct S { T sum; int count; }; static S op(S a, S b) { return S{a.sum + b.sum, a.count + b.count}; } static S e() { return S{T{}, 0}; } using STree = atcoder::segtree<S, op, e>; STree d; Compressor<T> cc; size_t sz; int index(const T& x) { int p = cc(x); assert(0 <= p && p < cc.size() && cc[p] == x); return p; } public: FixedSet() {} FixedSet(const std::vector<T>& A) { cc = Compressor<T>(A); d = STree(cc.size()); sz = 0; } void add(const T& x, int c = 1) { int p = index(x); S pv = d.get(p); sz -= pv.count; int cnt = std::max(0, pv.count + c); d.set(p, S{x * cnt, cnt}); sz += cnt; } T top_k_sum(int k) { if (k == 0) return T{}; assert(k <= (int)size()); const auto f = [&](S x) { return x.count < k; }; int l = d.min_left(cc.size(), f) - 1; S res = d.prod(l, cc.size()); T sum = res.sum - cc[l] * (res.count - k); return sum; } T bottom_k_sum(int k) { if (k == 0) return T{}; assert(k <= (int)size()); const auto f = [&](S x) { return x.count < k; }; int r = d.max_right(0, f); S res = d.prod(0, r); T sum = res.sum + cc[r] * (k - res.count); return sum; } T kth_smallest(int k) { assert(0 < k && k <= sz); const auto f = [&](S x) { return x.count < k; }; int r = d.max_right(0, f); return cc[r]; } T kth_largest(int k) { return kth_smallest(sz - k + 1); } size_t size() const { return sz; } bool empty() const { return size() == 0; } int count(const T& x) { int pos = index(x); return d.get(pos).count; } T sum() const { return d.all_prod().sum; } }; using namespace std; int N, Q; const int maxn = 2 << 17; int A[maxn], L[maxn], R[maxn]; long long S[maxn]; int ord[maxn]; long long ans[maxn]; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); cin >> N >> Q; for (int i = 0; i < N; i++) { cin >> A[i]; S[i + 1] = S[i] + A[i]; } const int B = std::max<int>(1, 1.0 * N / std::max<double>(1.0, std::sqrt(Q * 2.0 / 3.0))); for (int i = 0; i < Q; i++) { ord[i] = i; cin >> L[i] >> R[i]; L[i]--; } sort(ord, ord + Q, [&](int i, int j) -> bool { int iblock = L[i] / B, jblock = L[j] / B; if (iblock != jblock) return iblock < jblock; if (iblock & 1) return R[i] < R[j]; return R[i] > R[j]; }); FixedSet<long long> st(vector<long long>{A, A + N}); int nl = 0, nr = 0; for (int qi = 0; qi < Q; qi++) { int i = ord[qi]; while (nl > L[i]) st.add(A[--nl]); while (nr < R[i]) st.add(A[nr++]); while (nl < L[i]) st.add(A[nl++], -1); while (nr > R[i]) st.add(A[--nr], -1); int W = R[i] - L[i]; int m = (W + 1) / 2; long long mid = st.kth_largest(m); long long top = st.top_k_sum(W - m); long long bot = (S[R[i]] - S[L[i]] - top); ans[i] = top - mid * (W - m) + mid * m - bot; } for (int i = 0; i < Q; i++) cout << ans[i] << "\n"; }