#1128840 (C++17) No.3314 Library Rearrangement

• 問題: No.3314 Library Rearrangement
• ユーザー: Rubikun
• 提出日時: 2025-10-24 22:10:19
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,202 ms / 3,000 ms
• コード長: 20,334 bytes
• コンパイル時間: 1,752 ms
• コンパイル使用メモリ: 152,308 KB
• 実行使用メモリ: 65,012 KB
• 最終ジャッジ日時: 2025-10-24 22:10:55
• 合計ジャッジ時間: 30,449 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 2
other	AC * 39

ソースコード

// https://judge.yosupo.jp/submission/232217



#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator << (std::ostream &dest, const std::pair<F, S> &p) {
    dest << p.first << ' ' << p.second;
    return dest;
}

template<typename A, typename B>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t);
    return dest;
}

template<typename A, typename B, typename C>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t);
    return dest;
}

template<typename A, typename B, typename C, typename D>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C, D> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t);
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<std::vector<T>> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz; i++) {
        int m = v[i].size();
        for (int j = 0; j < m; j++) dest << v[i][j] << (i != sz - 1 && j == m - 1 ? '\n' : ' ');
    }
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<T> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T, size_t sz>
std::ostream &operator << (std::ostream &dest, const std::array<T, sz> &v) {
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::set<T> &v) {
    for (auto itr = v.begin(); itr != v.end();) {
        dest << *itr;
        itr++;
        if (itr != v.end()) dest << ' ';
    }
    return dest;
}

template<typename T, typename E>
std::ostream &operator << (std::ostream &dest, const std::map<T, E> &v) {
    for (auto itr = v.begin(); itr != v.end(); ) {
        dest << '(' << itr->first << ", " << itr->second << ')';
        itr++;
        if (itr != v.end()) dest << '\n';
    }
    return dest;
}

template<typename T>
vector<T> make_vec(size_t sz, T val) { return std::vector<T>(sz, val); }

template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail) {
    return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}

template<typename T>
vector<T> read_vec(size_t sz) {
    std::vector<T> v(sz);
    for (int i = 0; i < (int)sz; i++) std::cin >> v[i];
    return v;
}

template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail) {
    auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
    for (int i = 0; i < (int)sz; i++) v[i] = read_vec<T>(tail...);
    return v;
}

long long max(long long a, int b) { return std::max(a, (long long)b); }
long long max(int a, long long b) { return std::max((long long)a, b); }
long long min(long long a, int b) { return std::min(a, (long long)b); }
long long min(int a, long long b) { return std::min((long long)a, b); }
long long modulo(long long a, long long m) { a %= m; return a < 0 ? a + m : a; }

// x / y以上の最小の整数
ll ceil_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? y - 1 : 0)) / y;
}

// x / y以下の最大の整数
ll floor_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? 0 : -y + 1)) / y;
}

void io_init() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
}



#include <unistd.h>

// サイズは空白や改行も含めた文字数
template<int size_in = 1 << 25, int size_out = 1 << 25>
struct fast_io {
    char ibuf[size_in], obuf[size_out];
    char *ip, *op;
    
    fast_io() : ip(ibuf), op(obuf) {
        int t = 0, k = 0;
        while ((k = read(STDIN_FILENO, ibuf + t, sizeof(ibuf) - t)) > 0) {
            t += k;
        }
    }
    
    ~fast_io() {
        int t = 0, k = 0;
        while ((k = write(STDOUT_FILENO, obuf + t, op - obuf - t)) > 0) {
            t += k;
        }
    }
    
    long long in() {
        long long x = 0;
        bool neg = false;
        for (; *ip < '+'; ip++) ;
        if (*ip == '-'){ neg = true; ip++;}
        else if (*ip == '+') ip++;
        for (; *ip >= '0'; ip++) x = 10 * x + *ip - '0';
        if (neg) x = -x;
        return x;
    }
    
    unsigned long long inu64() {
        unsigned long long x = 0;
        for (; *ip < '+'; ip++) ;
        if (*ip == '+') ip++;
        for (; *ip >= '0'; ip++) x = 10 * x + *ip - '0';
        return x;
    }
    
    char in_char() {
        for (; *ip < '!'; ip++) ;
        return *ip++;
    }
    
    void out(long long x, char c = 0) {
        static char tmp[20];
        if (!x) {
            *op++ = '0';
        } else {
            int i;
            if (x < 0) {
                *op++ = '-';
                x = -x;
            }
            for (i = 0; x; i++) {
                tmp[i] = x % 10;
                x /= 10;
            }
            for (i--; i >= 0; i--) *op++ = tmp[i] + '0';
        }
        if (c) *op++ = c;
    }
    
    void outu64(unsigned long long x, char c = 0) {
        static char tmp[20];
        if (!x) {
            *op++ = '0';
        } else {
            int i;
            for (i = 0; x; i++) {
                tmp[i] = x % 10;
                x /= 10;
            }
            for (i--; i >= 0; i--) *op++ = tmp[i] + '0';
        }
        if (c) *op++ = c;
    }
    
    void out_char(char x, char c = 0){
        *op++ = x;
        if (c) *op++ = c;
    }
    
    long long memory_size() {
        return (long long)(size_in + size_out) * sizeof(char);
    }
};







constexpr unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

constexpr int bit_ceil_log(unsigned int n) {
    int x = 0;
    while ((1 << x) < (unsigned int)(n)) x++;
    return x;
}


template <typename T, typename Tsum>
struct beats {
private:
    struct S{
        T min, second_min, max, second_max;
        Tsum sum;
        int min_cnt, max_cnt;
        S(): min(inf), second_min(inf), max(minf), second_max(minf), sum(0), min_cnt(0), max_cnt(0){}
        S(T x): min(x), second_min(inf), max(x), second_max(minf), sum(x), min_cnt(1), max_cnt(1){}
    };
    
    struct F{
        T add, lower, upper;
        F(): add(0), lower(minf), upper(inf){}
        F(T a, T b, T c): add(a), lower(b), upper(c){}
        void reset(){
            add = 0;
            lower = minf;
            upper = inf;
        }
    };
    
public:
    static constexpr T inf = std::numeric_limits<T>::max();
    static constexpr T minf = std::numeric_limits<T>::min();
    
    beats() : beats(0) {}
    // n要素の0で初期化
    explicit beats(int n) : beats(std::vector<T>(n, T(0))) {}
    explicit beats(const std::vector<T>& v) : _n(int(v.size())) {
        size = (int)bit_ceil((unsigned int)(_n));
        log = bit_ceil_log((unsigned int)size);
        d = std::vector<S>(2 * size, S());
        lz = std::vector<F>(2 * size, F());
        que = std::vector<int>(2 * size);
        for (int i = 0; i < _n; i++) d[size + i] = S(v[i]);
        for (int i = size - 1; i >= 1; i--) update(i);
    }
    
    void set(int p, T x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    
    T get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }
    
    T prod_min(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return inf;
        
        l += size;
        r += size;
        
        T sml = inf, smr = inf;
        int i = 1, l2 = l, r2 = r;
        for (; l < r; i++, l >>= 1, r >>= 1) {
            if (l & 1) sml = std::min(sml, d[l++].min);
            if (r & 1) smr = std::min(d[--r].min, smr);
            if (sml != inf) sml = std::min(lz[l2 >> i].upper, sml + lz[l2 >> i].add);
            if (smr != inf) smr = std::min(lz[(r2 - 1) >> i].upper, smr + lz[(r2 - 1) >> i].add);
        }
        for (; i <= log; i++) {
            if (sml != inf) sml = std::min(lz[l2 >> i].upper, sml + lz[l2 >> i].add);
            if (smr != inf) smr = std::min(lz[(r2 - 1) >> i].upper, smr + lz[(r2 - 1) >> i].add);
        }
        return std::min(sml, smr);
    }
    
    T prod_max(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return minf;
        
        l += size;
        r += size;
        
        T sml = minf, smr = minf;
        int i = 1, l2 = l, r2 = r;
        for (; l < r; i++, l >>= 1, r >>= 1) {
            if (l & 1) sml = std::max(sml, d[l++].max);
            if (r & 1) smr = std::max(d[--r].max, smr);
            if (sml != minf) sml = std::max(lz[l2 >> i].lower, sml + lz[l2 >> i].add);
            if (smr != minf) smr = std::max(lz[(r2 - 1) >> i].lower, smr + lz[(r2 - 1) >> i].add);
        }
        for (; i <= log; i++) {
            if (sml != minf) sml = std::max(lz[l2 >> i].lower, sml + lz[l2 >> i].add);
            if (smr != minf) smr = std::max(lz[(r2 - 1) >> i].lower, smr + lz[(r2 - 1) >> i].add);
        }
        return std::max(sml, smr);
    }
    
    Tsum prod_sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return 0;
        
        l += size;
        r += size;
        
        S sml, smr;
        int llen = 0, rlen = 0;
        int i = 1, l2 = l, r2 = r;
        for (; l < r; i++, l >>= 1, r >>= 1) {
            if (l & 1) update_prod_sum(sml, d[l++]), llen += 1 << (i - 1);
            if (r & 1) update_prod_sum(smr, d[--r]), rlen += 1 << (i - 1);
            if (llen) propagate_prod_sum(sml, llen, lz[l2 >> i]);
            if (rlen) propagate_prod_sum(smr, rlen, lz[(r2 - 1) >> i]);
        }
        for (; i <= log; i++) {
            if (llen) propagate_prod_sum(sml, llen, lz[l2 >> i]);
            if (rlen) propagate_prod_sum(smr, rlen, lz[(r2 - 1) >> i]);
        }
        return sml.sum + smr.sum;
    }
    
    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    
    void apply_min(int l, int r, T f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;
        
        l += size;
        r += size;
        
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply_min(l++, f);
                if (r & 1) all_apply_min(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }
        
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
    
    void apply_max(int l, int r, T f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;
        
        l += size;
        r += size;
        
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply_max(l++, f);
                if (r & 1) all_apply_max(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }
        
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
    
    void apply_add(int l, int r, T f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;
        
        l += size;
        r += size;
        
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply_add(l++, f);
                if (r & 1) all_apply_add(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }
        
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
    
private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;
    std::vector<int> que;
    
    // v, lにfを作用
    void propagate(S &v, int len, F &l, const F &f) {
        if(f.add) {
            l.add += f.add;
            if (l.lower != minf) l.lower += f.add;
            if (l.upper != inf) l.upper += f.add;
            v.min += f.add;
            if (v.second_min != inf) v.second_min += f.add;
            v.max += f.add;
            if (v.second_max != minf) v.second_max += f.add;
            v.sum += (Tsum)f.add * len;
        }
        if(v.min < f.lower) {
            l.lower = f.lower;
            if (v.max < f.lower) l.upper = f.lower;
            v.sum += (Tsum)(f.lower - v.min) * v.min_cnt;
            if (v.second_max == v.min) v.second_max = f.lower;
            else if (v.max == v.min) v.max = f.lower, v.second_max = minf;
            v.min = f.lower;
        }
        if(f.upper < v.max) {
            l.upper = f.upper;
            if (f.upper < v.min) l.lower = f.upper;
            v.sum -= (Tsum)(v.max - f.upper) * v.max_cnt;
            if (v.second_min == v.max) v.second_min = f.upper;
            else if (v.min == v.max) v.min = f.upper, v.second_min = inf;
            v.max = f.upper;
        }
    }
    
    void update_inplace(S &v, const S &l, const S &r) {
        v.sum = l.sum + r.sum;
        if(l.max == r.max) {
            v.max = l.max;
            v.max_cnt = l.max_cnt + r.max_cnt;
            v.second_max = std::max(l.second_max, r.second_max);
        } else if(l.max > r.max) {
            v.max = l.max;
            v.max_cnt = l.max_cnt;
            v.second_max = std::max(l.second_max, r.max);
        } else {
            v.max = r.max;
            v.max_cnt = r.max_cnt;
            v.second_max = std::max(l.max, r.second_max);
        }
        if(l.min == r.min) {
            v.min = l.min;
            v.min_cnt = l.min_cnt + r.min_cnt;
            v.second_min = std::min(l.second_min, r.second_min);
        } else if(l.min < r.min) {
            v.min = l.min;
            v.min_cnt = l.min_cnt;
            v.second_min = std::min(l.second_min, r.min);
        } else {
            v.min = r.min;
            v.min_cnt = r.min_cnt;
            v.second_min = std::min(l.min, r.second_min);
        }
    }
    // prod sumで使う
    void propagate_prod_sum(S &v, int len, const F &f) {
        if(f.add) {
            v.min += f.add;
            v.max += f.add;
            v.sum += (Tsum)f.add * len;
        }
        if(v.min < f.lower) {
            v.sum += (Tsum)(f.lower - v.min) * v.min_cnt;
            if (v.max == v.min) v.max = f.lower;
            v.min = f.lower;
        }
        if(f.upper < v.max) {
            v.sum -= (Tsum)(v.max - f.upper) * v.max_cnt;
            if (v.min == v.max) v.min = f.upper;
            v.max = f.upper;
        }
    }
    
    // prod sumで使う
    void update_prod_sum(S &v, const S &u) {
        v.sum += u.sum;
        if (v.max <= u.max) {
            v.max_cnt = u.max_cnt + (v.max == u.max ? v.max_cnt : 0);
            v.max = u.max;
        }
        if (v.min >= u.min) {
            v.min_cnt = u.min_cnt + (v.min == u.min ? v.min_cnt : 0);
            v.min = u.min;
        }
    }
    void update(int k) { update_inplace(d[k], d[2 * k], d[2 * k + 1]); }
    
    void all_apply(int k, const F &f) {
        propagate(d[k], 1 << (log - 31 + __builtin_clz(k)), lz[k], f);
    }
    
    void all_apply_min(int k, T f) {
        int pos = 0;
        que[pos] = k;
        while(pos >= 0) {
            int idx = que[pos--];
            if (idx < 0) {
                update(-idx);
            } else if (d[idx].max <= f) {
            } else if(d[idx].second_max < f) {
                propagate(d[idx], 0, lz[idx], F(0, minf, f));
            } else {
                push(idx);
                que[++pos] = -idx;
                que[++pos] = idx * 2;
                que[++pos] = idx * 2 + 1;
            }
        }
    }
    
    void all_apply_max(int k, T f) {
        int pos = 0;
        que[pos] = k;
        while(pos >= 0) {
            int idx = que[pos--];
            if (idx < 0) {
                update(-idx);
            } else if (f <= d[idx].min) {
            } else if(f < d[idx].second_min) {
                propagate(d[idx], 0, lz[idx], F(0, f, inf));
            } else {
                push(idx);
                que[++pos] = -idx;
                que[++pos] = idx * 2;
                que[++pos] = idx * 2 + 1;
            }
        }
    }
    
    void all_apply_add(int k, T f) {
        propagate(d[k], 1 << (log - 31 + __builtin_clz(k)), lz[k], F(f, minf, inf));
    }
    
    void push(int k) {
        if (lz[k].add == 0 && lz[k].lower == minf && lz[k].upper == inf) return;
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k].reset();
    }
};


int main() {
    fast_io<1 << 25, 1 << 24> io;
    int n, K, q;
    n = io.in();
    K = io.in();
    q = io.in();
    std::vector<long long> a(n);
    for (int i = 0; i < n; i++) a[i] = io.in();
    vector<array<ll,3>> E(K),que(q);
    for (int i = 0; i < K; i++){
        long long x, y, z;
        x = io.in();
        y = io.in();
        z = io.in();
        x--;
        E[i]={x,y,z};
    }
    for (int i = 0; i < q; i++){
        long long x, y, z, v;
        x = io.in();
        y = io.in();
        z = io.in();
        x--;
        que[i]={x,y,z};
    }
    vector<int> L(q,-1),R(q,K+1);
    while(1){
        bool upd=false;
        
        vector<vector<int>> wh(K+1);
        for(int i=0;i<q;i++){
            if(R[i]-L[i]>1){
                wh[(L[i]+R[i])/2].push_back(i);
                upd=true;
            }
        }
        if(!upd) break;
        
        beats<ll, ll> seg(a);
        
        for(int i=0;i<=K;i++){
            for(int s:wh[i]){
                ll res=seg.prod_sum(que[s][0],que[s][1]);
                if(res>=que[s][2]) R[s]=i;
                else L[s]=i;
            }
            
            if(i<K){
                seg.apply_max(E[i][0],E[i][1],E[i][2]);
            }
        }
    }
    
    for(int i=0;i<q;i++){
        if(R[i]==K+1) io.out(-1, '\n');
        else io.out(R[i], '\n');
    }
}