結果

問題 No.2223 Merged Med
ユーザー jianglyjiangly
提出日時 2023-02-17 22:15:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 919 ms / 7,000 ms
コード長 3,489 bytes
コンパイル時間 2,562 ms
コンパイル使用メモリ 219,944 KB
実行使用メモリ 8,040 KB
最終ジャッジ日時 2023-09-26 19:32:34
合計ジャッジ時間 18,567 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,384 KB
testcase_02 AC 2 ms
4,384 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,384 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 312 ms
4,900 KB
testcase_14 AC 161 ms
4,428 KB
testcase_15 AC 418 ms
7,208 KB
testcase_16 AC 727 ms
7,420 KB
testcase_17 AC 256 ms
5,128 KB
testcase_18 AC 146 ms
4,380 KB
testcase_19 AC 277 ms
5,144 KB
testcase_20 AC 898 ms
7,980 KB
testcase_21 AC 915 ms
7,884 KB
testcase_22 AC 918 ms
7,912 KB
testcase_23 AC 906 ms
7,980 KB
testcase_24 AC 906 ms
7,992 KB
testcase_25 AC 907 ms
7,880 KB
testcase_26 AC 919 ms
8,036 KB
testcase_27 AC 901 ms
7,928 KB
testcase_28 AC 912 ms
8,000 KB
testcase_29 AC 909 ms
7,984 KB
testcase_30 AC 343 ms
8,040 KB
testcase_31 AC 301 ms
7,968 KB
testcase_32 AC 10 ms
4,380 KB
testcase_33 AC 795 ms
7,912 KB
testcase_34 AC 613 ms
7,900 KB
testcase_35 AC 563 ms
7,884 KB
権限があれば一括ダウンロードができます

ソースコード

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