結果

問題 No.3314 Library Rearrangement
コンテスト
ユーザー 👑 ArcAki
提出日時 2025-02-25 12:49:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,951 bytes
コンパイル時間 3,420 ms
コンパイル使用メモリ 283,608 KB
実行使用メモリ 355,004 KB
最終ジャッジ日時 2025-05-06 07:06:23
合計ジャッジ時間 22,997 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other AC * 2 RE * 17 TLE * 2 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#include <bits/stdc++.h>
using namespace std;
 
// Persistent segment tree node
struct Node {
    long long sum;  // 区間の和
    int mn, mx;     // 区間の最小値，最大値
    bool uniform;   // 区間内すべてが同じ値なら true
    int lch, rch;   // 左右の子（uniformなら使わない）
};
 
// グローバルに全ノードを管理する配列
static vector<Node> seg;
 
// 新規ノードを作成して seg に追加．返り値はそのノードのインデックス
int newNode(const Node &node) {
    seg.push_back(node);
    return seg.size()-1;
}
 
// 1-indexed の配列 A を元に，区間 [L,R] 用のセグ木を構築
int buildTree(int L, int R, const vector<int>& A) {
    if(L == R){
        Node nd;
        nd.sum = A[L];
        nd.mn = A[L];
        nd.mx = A[L];
        nd.uniform = true;
        nd.lch = nd.rch = -1;
        return newNode(nd);
    }
    int mid = (L + R) / 2;
    int leftChild = buildTree(L, mid, A);
    int rightChild = buildTree(mid+1, R, A);
    Node nd;
    nd.sum = seg[leftChild].sum + seg[rightChild].sum;
    nd.mn = min(seg[leftChild].mn, seg[rightChild].mn);
    nd.mx = max(seg[leftChild].mx, seg[rightChild].mx);
    // 両子が uniform かつ値が同じならこの区間も uniform
    if(seg[leftChild].uniform && seg[rightChild].uniform && seg[leftChild].mn == seg[rightChild].mn){
        nd.uniform = true;
        nd.lch = nd.rch = -1;
    } else {
        nd.uniform = false;
        nd.lch = leftChild;
        nd.rch = rightChild;
    }
    return newNode(nd);
}
 
// 区間 [L,R] 全体が定数 X の節点を作る
int newUniform(int L, int R, int X){
    Node nd;
    int len = R - L + 1;
    nd.sum = (long long) len * X;
    nd.mn = X;
    nd.mx = X;
    nd.uniform = true;
    nd.lch = nd.rch = -1;
    return newNode(nd);
}
 
// 左子(leftChild)と右子(rightChild)を結合して，区間 [L,R] の節点を作る
int combineNode(int leftChild, int rightChild, int L, int R){
    Node nd;
    nd.sum = seg[leftChild].sum + seg[rightChild].sum;
    nd.mn = min(seg[leftChild].mn, seg[rightChild].mn);
    nd.mx = max(seg[leftChild].mx, seg[rightChild].mx);
    if(seg[leftChild].uniform && seg[rightChild].uniform && seg[leftChild].mn == seg[rightChild].mn){
        nd.uniform = true;
        nd.lch = nd.rch = -1;
    } else {
        nd.uniform = false;
        nd.lch = leftChild;
        nd.rch = rightChild;
    }
    return newNode(nd);
}
 
// persistent update：区間 [ql,qr] について，A[j] = max(A[j], X) を適用する．
// 現在の区間 [L,R] をカバーするノード node を元に，新たな根のインデックスを返す．
int updateTree(int node, int L, int R, int ql, int qr, int X){
    // 完全に重ならない場合
    if(R < ql || L > qr)
        return node;
    // 区間 [L,R] が [ql,qr] に完全含まれる場合
    if(ql <= L && R <= qr){
        // もしこの節点が uniform なら
        if(seg[node].uniform){
            // 既に値が X 以上なら更新不要
            if(seg[node].mn >= X)
                return node;
            // すべての値が X 未満なら，一括更新可能
            if(seg[node].mx < X){
                return newUniform(L, R, X);
            }
            // uniform なら mn==mx なのでここに来ることはない
        } else {
            // uniform でなくても，区間内すべての値が X 未満なら
            if(seg[node].mx < X){
                return newUniform(L, R, X);
            }
            // すでに全て X 以上なら何もせず
            if(seg[node].mn >= X)
                return node;
        }
        // それ以外は部分的に更新が必要
    }
    // 部分更新の場合．もしノードが uniform なら分割してから再帰的に更新
    if(seg[node].uniform){
        int mid = (L+R)/2;
        int leftChild = newUniform(L, mid, seg[node].mn);
        int rightChild = newUniform(mid+1, R, seg[node].mn);
        node = combineNode(leftChild, rightChild, L, R);
    }
    int mid = (L+R)/2;
    int newLeft = updateTree(seg[node].lch, L, mid, ql, qr, X);
    int newRight = updateTree(seg[node].rch, mid+1, R, ql, qr, X);
    return combineNode(newLeft, newRight, L, R);
}
 
// 区間 [ql,qr] の和を求めるクエリ
long long queryTree(int node, int L, int R, int ql, int qr){
    if(R < ql || L > qr)
        return 0;
    if(ql <= L && R <= qr)
        return seg[node].sum;
    if(seg[node].uniform){
        int lbound = max(L, ql);
        int rbound = min(R, qr);
        int len = rbound - lbound + 1;
        return (long long) len * seg[node].mn;
    }
    int mid = (L+R)/2;
    return queryTree(seg[node].lch, L, mid, ql, qr) +
           queryTree(seg[node].rch, mid+1, R, ql, qr);
}
 
// 更新クエリ用の構造体
struct Upd {
    int L, R, X;
};
 
// 質問クエリ用の構造体
struct Query {
    int L, R;
    long long T;
    int idx;
};
 
// main
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, K, Q;
    cin >> N >> K >> Q;
    vector<int> A(N+1);
    for (int i = 1; i <= N; i++){
        cin >> A[i];
    }
 
    vector<Upd> updates(K+1);
    for (int i = 1; i <= K; i++){
        int L, R, X;
        cin >> L >> R >> X;
        updates[i] = {L, R, X};
    }
 
    vector<Query> queries(Q);
    for (int i = 0; i < Q; i++){
        int L, R; long long T;
        cin >> L >> R >> T;
        queries[i] = {L, R, T, i};
    }
 
    // セグ木ノードのメモリをある程度確保（worst-case対策）
    seg.reserve((N * 4) + (K * 50));
 
    // 初期状態（version 0）の構築
    int root0 = buildTree(1, N, A);
    vector<int> version(K+1);
    version[0] = root0;
 
    // 更新クエリを順に適用し，persistent version を作る
    for (int i = 1; i <= K; i++){
        int newRoot = updateTree(version[i-1], 1, N, updates[i].L, updates[i].R, updates[i].X);
        version[i] = newRoot;
    }
 
    // 各質問について，バイナリサーチで「初めて sum >= T となる更新番号」を求める
    // ※初期状態で条件を満たすなら 0，すべての更新後でも条件未達なら -1
    vector<int> ans(Q, -1);
    for(auto &qu : queries){
        long long s0 = queryTree(version[0], 1, N, qu.L, qu.R);
        if(s0 >= qu.T){
            ans[qu.idx] = 0;
            continue;
        }
        long long sK = queryTree(version[K], 1, N, qu.L, qu.R);
        if(sK < qu.T){
            ans[qu.idx] = -1;
            continue;
        }
        int lo = 0, hi = K;
        while(lo + 1 < hi){
            int mid = (lo + hi) / 2;
            long long s = queryTree(version[mid], 1, N, qu.L, qu.R);
            if(s >= qu.T) hi = mid;
            else lo = mid;
        }
        ans[qu.idx] = hi;
    }
 
    for (int i = 0; i < Q; i++){
        cout << ans[i] << "\n";
    }
    return 0;
}
0