結果

問題 No.2223 Merged Med
ユーザー jiangly
提出日時 2023-02-17 22:15:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,100 ms / 7,000 ms
コード長 3,489 bytes
コンパイル時間 2,985 ms
コンパイル使用メモリ 213,284 KB
最終ジャッジ日時 2025-02-10 17:04:51
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using i64 = long long;
template<class Info,
    class Merge = std::plus<Info>>
struct SegmentTree {
    const int n;
    const Merge merge;
    std::vector<Info> info;
    SegmentTree(int n) : n(n), merge(Merge()), info(4 << std::__lg(n)) {}
    SegmentTree(std::vector<Info> init) : SegmentTree(init.size()) {
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = merge(info[2 * p], info[2 * p + 1]);
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p + 1, m, r, x, y));
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
};

constexpr int inf = 1E9;
struct Info {
    int sum;
    int min;
    int pre;
    int suf;
    Info() : sum{0}, min{inf}, pre{inf}, suf{inf} {};
    Info(int x) : sum{x}, min{std::min(x, 0)}, pre{min}, suf{min} {}
};

Info operator+(Info a, Info b) {
    Info c;
    c.sum = a.sum + b.sum;
    c.min = std::min({a.min, b.min, a.suf + b.pre});
    c.pre = std::min(a.pre, a.sum + b.pre);
    c.suf = std::min(a.suf + b.sum, b.suf);
    return c;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::vector<int> l(q), r(q), lo(q, 1), hi(q, n);
    for (int i = 0; i < q; i++) {
        std::cin >> l[i] >> r[i];
        l[i]--;
    }
    
    while (true) {
        bool ok = true;
        
        std::vector<std::pair<int, int>> events;
        for (int i = 0; i < q; i++) {
            if (lo[i] < hi[i]) {
                int x = (lo[i] + hi[i]) / 2;
                events.emplace_back(x, n + i);
                ok = false;
            }
        }
        
        if (ok) {
            break;
        }
        
        for (int i = 0; i < n; i++) {
            events.emplace_back(a[i], i);
        }
        
        SegmentTree<Info> seg(std::vector<Info>(n, -1));
        std::sort(events.begin(), events.end());
        
        for (auto [x, i] : events) {
            if (i < n) {
                seg.modify(i, 1);
            } else {
                i -= n;
                auto info = seg.rangeQuery(l[i], r[i]);
                if (info.sum - std::min(0, info.min + 1) > 0) {
                    hi[i] = x;
                } else {
                    lo[i] = x + 1;
                }
            }
        }
    }
    
    for (int i = 0; i < q; i++) {
        std::cout << lo[i] << "\n";
    }
    
    return 0;
}
0