結果

問題 No.3314 Library Rearrangement
コンテスト
ユーザー 👑 ArcAki
提出日時 2025-02-27 01:24:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,344 bytes
コンパイル時間 3,841 ms
コンパイル使用メモリ 294,840 KB
実行使用メモリ 23,748 KB
最終ジャッジ日時 2025-05-06 07:06:27
合計ジャッジ時間 12,476 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

// GPT-o3-mini-highによる生成コード


#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
// セグメントツリー用グローバル配列（各ラウンドごとに再構築します）
vector<ll> seg, segMin, segMax, lazy;
vector<bool> lazyFlag;
 
// セグメントツリーを構築する関数
// idx: 現在のノード、[l, r] がその区間、A が初期配列
void buildTree(int idx, int l, int r, const vector<ll>& A) {
    if(l == r) {
        seg[idx] = A[l];
        segMin[idx] = A[l];
        segMax[idx] = A[l];
        lazy[idx] = 0; // lazyFlag が false のときは値は使わない
        lazyFlag[idx] = false;
        return;
    }
    int mid = (l + r) / 2;
    buildTree(idx*2, l, mid, A);
    buildTree(idx*2+1, mid+1, r, A);
    seg[idx] = seg[idx*2] + seg[idx*2+1];
    segMin[idx] = min(segMin[idx*2], segMin[idx*2+1]);
    segMax[idx] = max(segMax[idx*2], segMax[idx*2+1]);
    lazy[idx] = 0;
    lazyFlag[idx] = false;
}
 
// lazy 情報を子ノードへ伝搬
void pushDown(int idx, int l, int r) {
    if(lazyFlag[idx]) {
        int mid = (l + r) / 2;
        int left = idx*2, right = idx*2+1;
        // 左の子
        seg[left] = lazy[idx] * (mid - l + 1);
        segMin[left] = lazy[idx];
        segMax[left] = lazy[idx];
        lazy[left] = lazy[idx];
        lazyFlag[left] = true;
        // 右の子
        seg[right] = lazy[idx] * (r - mid);
        segMin[right] = lazy[idx];
        segMax[right] = lazy[idx];
        lazy[right] = lazy[idx];
        lazyFlag[right] = true;
 
        lazyFlag[idx] = false;
    }
}
 
// 区間 [ql,qr] に対して A[j] = max(A[j], X) を適用する
void updateRange(int idx, int l, int r, int ql, int qr, ll X) {
    if(qr < l || r < ql) return;
    if(ql <= l && r <= qr) {
        // すでにすべての値が X 以上なら何もしない
        if(segMin[idx] >= X) return;
        // 全部 X 未満なら一括更新
        if(segMax[idx] < X) {
            seg[idx] = X * (r - l + 1);
            segMin[idx] = X;
            segMax[idx] = X;
            lazy[idx] = X;
            lazyFlag[idx] = true;
            return;
        }
    }
    pushDown(idx, l, r);
    int mid = (l + r) / 2;
    updateRange(idx*2, l, mid, ql, qr, X);
    updateRange(idx*2+1, mid+1, r, ql, qr, X);
    seg[idx] = seg[idx*2] + seg[idx*2+1];
    segMin[idx] = min(segMin[idx*2], segMin[idx*2+1]);
    segMax[idx] = max(segMax[idx*2], segMax[idx*2+1]);
}
 
// 区間 [ql,qr] の総和を返す
ll queryRange(int idx, int l, int r, int ql, int qr) {
    if(qr < l || r < ql) return 0;
    if(ql <= l && r <= qr) return seg[idx];
    pushDown(idx, l, r);
    int mid = (l + r) / 2;
    return queryRange(idx*2, l, mid, ql, qr) + queryRange(idx*2+1, mid+1, r, ql, qr);
}
 
// 更新クエリの構造体
struct UpdateQuery {
    int L, R;
    ll X;
};
 
// 質問クエリ：区間 [L,R] の総和が初めて X 以上となる「更新回数」を求める
struct Query {
    int L, R, id;
    ll X;
    int lo, hi; // 二分探索の区間。lo:未成立、hi:成立する候補（最小更新番号）
};
 
// メイン
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, K, Q;
    cin >> N >> K >> Q;
    vector<ll> A(N);
    for (int i = 0; i < N; i++){
        cin >> A[i];
    }
    vector<UpdateQuery> updates(K);
    for (int i = 0; i < K; i++){
        int L, R; ll X;
        cin >> L >> R >> X;
        // 入力は 1-indexed なので 0-indexed に変換
        updates[i].L = L - 1;
        updates[i].R = R - 1;
        updates[i].X = X;
    }
 
    // 初期状態の累積和を作成（質問クエリで初期状態で条件を満たすかチェック）
    vector<ll> prefix(N+1, 0);
    for (int i = 0; i < N; i++){
        prefix[i+1] = prefix[i] + A[i];
    }
 
    vector<ll> ans(Q, 0);
    vector<Query> active;
    for (int i = 0; i < Q; i++){
        int L, R; ll X;
        cin >> L >> R >> X;
        L--; R--;
        ll initSum = prefix[R+1] - prefix[L];
        if(initSum >= X) {
            ans[i] = 0;  // 条件を初期状態で満たす
        } else {
            Query qu;
            qu.L = L; qu.R = R; qu.X = X; qu.id = i;
            qu.lo = 1;
            qu.hi = K + 1; // もし全更新後でも条件未達なら hi = K+1 として -1 と出力
            active.push_back(qu);
        }
    }
 
    // セグメントツリー用配列のサイズを確保
    int size = 4 * N + 10;
    seg.assign(size, 0);
    segMin.assign(size, 0);
    segMax.assign(size, 0);
    lazy.assign(size, 0);
    lazyFlag.assign(size, false);
 
    // 並列二分探索 (Parallel Binary Search)
    while(!active.empty()){
        // 各質問について candidate = (lo+hi)/2 を求める
        vector<pair<int,int>> cand; // (candidate update数, active内でのインデックス)
        for (int i = 0; i < (int)active.size(); i++){
            int mid = (active[i].lo + active[i].hi) / 2;
            cand.push_back({mid, i});
        }
        sort(cand.begin(), cand.end());
 
        // セグメントツリーを初期配列 A から構築
        buildTree(1, 0, N-1, A);
        int cur = 0;
        // candidate の昇順に「更新クエリ」を適用しながら各質問の区間和を取得
        for(auto &p : cand){
            int target = p.first; // これだけ更新を適用した状態でチェック
            int qi = p.second;
            while(cur < target && cur < K) {
                UpdateQuery &up = updates[cur];
                updateRange(1, 0, N-1, up.L, up.R, up.X);
                cur++;
            }
            ll s = queryRange(1, 0, N-1, active[qi].L, active[qi].R);
            if(s >= active[qi].X)
                active[qi].hi = target;
            else
                active[qi].lo = target + 1;
        }
 
        // 更新済みの質問で探索区間が収束したものは答えを確定する
        vector<Query> nextActive;
        for(auto &qu : active){
            if(qu.lo == qu.hi){
                if(qu.lo > K) ans[qu.id] = -1;
                else ans[qu.id] = qu.lo;
            } else {
                nextActive.push_back(qu);
            }
        }
        active.swap(nextActive);
    }
 
    for (int i = 0; i < Q; i++){
        cout << ans[i] << "\n";
    }
    return 0;
}
0