結果

問題 No.3314 Library Rearrangement
コンテスト
ユーザー 👑 ArcAki
提出日時 2025-04-17 07:13:32
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 707 ms / 3,000 ms
コード長 4,788 bytes
コンパイル時間 3,377 ms
コンパイル使用メモリ 292,124 KB
実行使用メモリ 14,676 KB
最終ジャッジ日時 2025-05-06 07:06:45
合計ジャッジ時間 21,010 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = (ll)4e18;

struct Node {
    ll sum;        // 区間の和
    ll minv;       // 区間の最小値
    ll second_min; // 区間内で 2 番目に小さい値
    int cnt_min;   // 区間内で最小値と等しい要素の個数
};

int N, K, Q;
vector<ll> A;
vector<tuple<int,int,ll>> updates;
vector<int> ql, qr;
vector<ll> qx;
vector<int> L, R;       // 並列二分探索用左右端
vector<Node> seg;

// ノード v を子にプッシュダウン
void pushdown(int v) {
    for(int c : {v<<1, v<<1|1}) {
        if (seg[c].minv < seg[v].minv) {
            // 葉でないなら，子の最小値を seg[v].minv に引き上げ
            ll delta = seg[v].minv - seg[c].minv;
            seg[c].sum += delta * seg[c].cnt_min;
            seg[c].minv = seg[v].minv;
        }
    }
}

// 子から情報を引き上げ
void pull(int v) {
    const Node &L = seg[v<<1], &R = seg[v<<1|1];
    Node &U = seg[v];
    U.sum = L.sum + R.sum;
    if (L.minv < R.minv) {
        U.minv = L.minv;
        U.cnt_min = L.cnt_min;
        U.second_min = min(L.second_min, R.minv);
    } else if (L.minv > R.minv) {
        U.minv = R.minv;
        U.cnt_min = R.cnt_min;
        U.second_min = min(L.minv, R.second_min);
    } else {
        U.minv = L.minv;
        U.cnt_min = L.cnt_min + R.cnt_min;
        U.second_min = min(L.second_min, R.second_min);
    }
}

// 区間 [l..r] を走査し，A[i] = max(A[i], x) を行う
void range_chmax(int v, int l, int r, int ql, int qr, ll x) {
    if (r < ql || qr < l || seg[v].minv >= x) return;
    if (ql <= l && r <= qr && seg[v].second_min > x) {
        // この区間中、最小値以外はすでに x 以上
        ll delta = x - seg[v].minv;
        seg[v].sum += delta * seg[v].cnt_min;
        seg[v].minv = x;
        return;
    }
    pushdown(v);
    int m = (l + r) >> 1;
    range_chmax(v<<1,   l,   m, ql, qr, x);
    range_chmax(v<<1|1, m+1, r, ql, qr, x);
    pull(v);
}

// 区間和を返す
ll query_sum(int v, int l, int r, int ql, int qr) {
    if (r < ql || qr < l) return 0;
    if (ql <= l && r <= qr) return seg[v].sum;
    pushdown(v);
    int m = (l + r) >> 1;
    return query_sum(v<<1,   l,   m, ql, qr)
         + query_sum(v<<1|1, m+1, r, ql, qr);
}

// 初期木を構築
void build(int v, int l, int r) {
    if (l == r) {
        seg[v].sum        = A[l];
        seg[v].minv       = A[l];
        seg[v].second_min = INF;
        seg[v].cnt_min    = 1;
        return;
    }
    int m = (l + r) >> 1;
    build(v<<1,   l,   m);
    build(v<<1|1, m+1, r);
    pull(v);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K >> Q;
    A.resize(N);
    for(int i = 0; i < N; i++) cin >> A[i];

    updates.resize(K);
    for(int i = 0; i < K; i++){
        int l, r;
        ll x;
        cin >> l >> r >> x;
        --l; --r;
        updates[i] = make_tuple(l, r, x);
    }

    ql.resize(Q);
    qr.resize(Q);
    qx.resize(Q);
    for(int i = 0; i < Q; i++){
        cin >> ql[i] >> qr[i] >> qx[i];
        --ql[i]; --qr[i];
    }

    // 並列二分探索の左右端を初期化
    L.assign(Q, 0);
    R.assign(Q, K+1);

    // 初期の A で条件を満たすクエリは r=0 にする
    vector<ll> pref(N+1, 0);
    for(int i = 0; i < N; i++) pref[i+1] = pref[i] + A[i];
    for(int i = 0; i < Q; i++){
        ll s = pref[qr[i]+1] - pref[ql[i]];
        if (s >= qx[i]) {
            R[i] = 0;
        }
    }

    seg.assign(4*N+4, Node());

    // 並列二分探索 main loop
    vector<vector<int>> bucket(K+2);
    while (true) {
        bool any = false;
        for(int i = 1; i <= K; i++) bucket[i].clear();
        for(int i = 0; i < Q; i++){
            if (L[i] + 1 < R[i]){
                int mid = (L[i] + R[i]) >> 1;
                bucket[mid].push_back(i);
                any = true;
            }
        }
        if (!any) break;

        // 木を構築
        build(1, 0, N-1);

        // updates を 1..K 順に適用しながら、bucket を処理
        for(int i = 1; i <= K; i++){
            auto [l, r, x] = updates[i-1];
            range_chmax(1, 0, N-1, l, r, x);
            for(int qi : bucket[i]){
                ll s = query_sum(1, 0, N-1, ql[qi], qr[qi]);
                if (s >= qx[qi]) R[qi] = i;
                else            L[qi] = i;
            }
        }
    }

    // 結果出力
    // R[i] == 0 → 0 回目 (初めから)
    // R[i] == K+1 → -1 (最後まで満たさない)
    // それ以外 → R[i]
    for(int i = 0; i < Q; i++){
        if      (R[i] == 0)    cout << 0 << "\n";
        else if (R[i] == K+1)  cout << -1 << "\n";
        else                   cout << R[i] << "\n";
    }
    return 0;
}
0