#1175596 (C++23) No.3614 Breaking door keys（LITTLE BREAK ver.）

• 問題: No.3614 Breaking door keys（LITTLE BREAK ver.）
• ユーザー: あるふぁ
• 提出日時: 2026-08-07 10:35:27
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 410 ms / 2,000 ms
• コード長: 4,367 bytes
• コンパイル時間: 2,165 ms
• コンパイル使用メモリ: 342,008 KB
• 実行使用メモリ: 23,808 KB
• 最終ジャッジ日時: 2026-08-07 10:35:40
• 合計ジャッジ時間: 12,331 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

サブタスク	配点	結果
サンプル	0 %	AC * 3
小課題1	10 %	AC * 7
小課題2	20 %	AC * 7
小課題3	30 %	AC * 7
小課題4	30 %	AC * 14
小課題5	10 %	AC * 38
合計	2.5 * 100% = 250 点

ソースコード

#include <bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pob pop_back
#define eb emplace_back
#define nall(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define yesno(a) cout<<(a?"Yes\n":"No\n")
#define accu accumulate
#define lb lower_bound
#define ub lower_bound
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template<class T> using vec = vector<T>;
template<class T> using vv = vector<vector<T>>;
template<class T> using vvv = vector<vv<T>>;
template<class T> using vvvv = vector<vvv<T>>;
template<class T> using vvvvv = vector<vvvv<T>>;

template<class T> class segtree{
private:
    int n, size;
    vector<T> seg;
    T e;
    function<T(T, T)> op;
public:
    segtree(const vector<T>& A, function<T(T, T)> op, T id) : e(id), op(op){
        n = A.size();
        size = 1;
        while (size < n) size <<= 1;
        seg.assign(2*size, e);
        for (int i = 0; i < n; i++) seg[size+i] = A[i];
        for (int i = size-1; i > 0; i--) seg[i] = op(seg[i<<1], seg[i<<1|1]);
    }

    segtree(int sz, function<T(T, T)> op, T id) : e(id), op(op){
        n = sz;
        size = 1;
        while (size < n) size <<= 1;
        seg.assign(2*size, e);
        for (int i = 0; i < n; i++) seg[size+i] = e;
        for (int i = size-1; i > 0; i--) seg[i] = op(seg[i<<1], seg[i<<1|1]);
    }

    void set(int i, T val){
        i += size;
        seg[i] = val;
        while (i >>= 1) seg[i] = op(seg[i<<1], seg[i<<1|1]);
    }

    T all_prod() const{
        return seg[1];
    }

    T prod(int l, int r) const{
        T L = e, R = e;
        for (l += size, r += size; l < r; l >>= 1, r >>= 1){
            if (l&1) L = op(L, seg[l++]);
            if (r&1) R = op(seg[--r], R);
        }
        return op(L, R);
    }

    T get(int i) const{
        return seg[size+i];
    }

    const T& operator [] (int i) const{
        return seg[size+i];
    }

    void add(int i, T val){
        set(i, get(i)+val);
    }

    template<class F> int max_right(int l, F f) const{
        if (l == n) return n;
        l += size;
        T sm = e;
        do{
            while ((l & 1) == 0) l >>= 1;
            if (!f(op(sm, seg[l]))){
                while (l < size){
                    l <<= 1;
                    if (f(op(sm, seg[l]))){
                        sm = op(sm, seg[l]);
                        l++;
                    }
                }
                return l-size;
            }
            sm = op(sm, seg[l]);
            l++;
        }while((l&-l) != l);
        return n;
    }

    template<class F> int min_left(int r, F f) const{
        if (r == 0) return 0;
        r += size;
        T sm = e;
        do{
            r--;
            while (r > 1 && (r&1)) r >>= 1;
            if (!f(op(seg[r], sm))){
                while (r < size){
                    r = r<<1|1;
                    if (f(op(seg[r], sm))){
                        sm = op(seg[r], sm);
                        r--;
                    }
                }
                return r+1-size;
            }
            sm = op(seg[r], sm);
        }while((r&-r) != r);
        return 0;
    }
};

void solve();
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    unsigned T = 1;
    // cin >> T;
    cout << fixed << setprecision(20);
    while (T--) solve();
    return 0;
}

void solve(){
    using S = array<ll, 10>;
    auto op = [](S l, S r){
        array<ll, 20> a;
        rep(i, 10) a[i] = l[i];
        rep(i, 10) a[i+10] = r[i];
        sort(nall(a));
        S res;
        rep(i, 10) res[i] = a[i];
        return res;
    };
    auto e = [](){
        return S{
            INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX,
            INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX
        };
    };

    int N, Q;
    cin >> N >> Q;
    segtree<S> seg(N, op, e());
    rep(i, N){
        S x = e();
        cin >> x[0];
        seg.set(i, x);
    }

    while (Q--){
        int l, r, k;
        cin >> l >> r >> k;
        S res = seg.prod(l-1, r);
        cout << accumulate(res.begin(), res.begin()+k, 0ll) << endl;
    }
}