結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    long long sum;  // 区間和
    int mn, mx;     // 区間の最小・最大値
    bool uniform;   // 区間が一様なら true
    int lch, rch;   // 左右の子（uniform なら -1）
};
 
static vector<Node> seg;
 
// 新規ノード作成
int newNode(const Node &node) {
    seg.push_back(node);
    return seg.size()-1;
}
 
// [L,R]（1-indexed）の初期配列 A を元にセグ木構築
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);
    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);
}
 
// 2つの子（それぞれ [L,mid]，[mid+1,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] をカバー）を元に，新たな根のノード番号を返す
int updateTree(int node, int L, int R, int ql, int qr, int X){
    if(R < ql || L > qr) return node; // 完全に非交差
    // 完全被覆の場合
    if(ql <= L && R <= qr){
        if(seg[node].uniform){
            if(seg[node].mn >= X) return node; // すでに更新不要
            if(seg[node].mx < X) return newUniform(L, R, X); // 一括更新可能
        } else {
            if(seg[node].mn >= X) return node;
            if(seg[node].mx < X) return newUniform(L, R, X);
        }
        // ここに来るのは，本来 uniform なら起こらないはず
    }
    int mid = (L+R)/2;
    // 更新区間が片側に完全に収まるなら，全体を無理に分割せず該当子のみ更新
    if(qr <= mid){
        int newLeft;
        if(seg[node].uniform)
            newLeft = updateTree(newUniform(L, mid, seg[node].mn), L, mid, ql, qr, X);
        else
            newLeft = updateTree(seg[node].lch, L, mid, ql, qr, X);
        int newRight;
        if(seg[node].uniform)
            newRight = newUniform(mid+1, R, seg[node].mn);
        else
            newRight = seg[node].rch;
        return combineNode(newLeft, newRight, L, R);
    } else if(ql > mid){
        int newRight;
        if(seg[node].uniform)
            newRight = updateTree(newUniform(mid+1, R, seg[node].mn), mid+1, R, ql, qr, X);
        else
            newRight = updateTree(seg[node].rch, mid+1, R, ql, qr, X);
        int newLeft;
        if(seg[node].uniform)
            newLeft = newUniform(L, mid, seg[node].mn);
        else
            newLeft = seg[node].lch;
        return combineNode(newLeft, newRight, L, R);
    } else {
        // 更新区間が左右にまたがる場合
        int newLeft, newRight;
        if(seg[node].uniform){
            newLeft = updateTree(newUniform(L, mid, seg[node].mn), L, mid, ql, qr, X);
            newRight = updateTree(newUniform(mid+1, R, seg[node].mn), mid+1, R, ql, qr, X);
        } else {
            newLeft = updateTree(seg[node].lch, L, mid, ql, qr, X);
            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), 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;
};
 
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};
    }
 
    // 必要な分だけメモリ確保（ワーストケース対策）
    seg.reserve((N * 4) + (K * 50));
 
    int root0 = buildTree(1, N, A);
    vector<int> version(K+1);
    version[0] = root0;
    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;
    }
 
    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