#325068 (C++11) No.801 エレベーター

• 問題: No.801 エレベーター
• ユーザー: kcvlex
• 提出日時: 2019-03-17 22:34:45
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 416 ms / 2,000 ms
• コード長: 8,133 bytes
• コンパイル時間: 1,417 ms
• コンパイル使用メモリ: 166,920 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-08 00:40:09
• 合計ジャッジ時間: 8,152 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	4 ms; 5,376 KB
testcase_04	AC	4 ms; 5,376 KB
testcase_05	AC	4 ms; 5,376 KB
testcase_06	AC	4 ms; 5,376 KB
testcase_07	AC	4 ms; 5,376 KB
testcase_08	AC	4 ms; 5,376 KB
testcase_09	AC	4 ms; 5,376 KB
testcase_10	AC	4 ms; 5,376 KB
testcase_11	AC	4 ms; 5,376 KB
testcase_12	AC	4 ms; 5,376 KB
testcase_13	AC	399 ms; 5,376 KB
testcase_14	AC	394 ms; 5,376 KB
testcase_15	AC	397 ms; 5,376 KB
testcase_16	AC	395 ms; 5,376 KB
testcase_17	AC	416 ms; 5,376 KB
testcase_18	AC	395 ms; 5,376 KB
testcase_19	AC	403 ms; 5,376 KB
testcase_20	AC	399 ms; 5,376 KB
testcase_21	AC	398 ms; 5,376 KB
testcase_22	AC	408 ms; 5,376 KB
testcase_23	AC	367 ms; 5,376 KB
testcase_24	AC	371 ms; 5,376 KB
testcase_25	AC	373 ms; 5,376 KB
testcase_26	AC	366 ms; 5,376 KB
testcase_27	AC	371 ms; 5,376 KB
testcase_28	AC	270 ms; 5,376 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;
//#define DEBUG_MODE
#define endl '\n'
#ifdef DEBUG_MODE
#define DEBUG(X) debug_func(X, #X)
#define DEBUG_ENDL endl << flush
#define DEBUG_SEPARATOR_LINE cout<<"=================\n"
#else
#define DEBUG(X) 0
#define DEBUG_ENDL 0
#define DEBUG_SEPARATOR_LINE 0
#endif
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
#define DEBUG_ENDL_S(S) ((S).size() ? "\n" : "") << flush;
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename Head, typename... Tail> const Head& var_min(const Head &head, const Tail&... tail) { return min(head, var_min(tail...)); }
template <typename Head, typename... Tail> const Head& var_max(const Head &head, const Tail&... tail) { return max(head, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
void debug_func_preffix(const string &s) { if(s.size()) cout << s << " = "; }
template <typename T>
void debug_func(const T &t, const string &s = "") {
    debug_func_preffix(s);
    cout << t << DEBUG_ENDL_S(s);
}
template <typename T, typename U>
void debug_func(const P<T, U> &p, const string &s = "") {
    debug_func_preffix(s);
    cout << "(";
    debug_func(p.first);
    cout << ", ";
    debug_func(p.second);
    cout << ")" << DEBUG_ENDL_S(s);
}
template <typename T>
void debug_func(const V<T> &v, const string &s = "") {
    for(ll i = 0; i < v.size(); i++) {
        string t = s + "[" + to_string(i) + "]";
        debug_func(v[i], t);
    }
}

void init_io() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(30);
}


template <typename T, typename L>
class LazySegmentTree{
private:
    ll N;
    T init_node;
    L init_lazy;
    vector<T> node;
    vector<L> lazy;
    vector<bool> lazy_flag;
    function<T (T, T)> merge_node;
    function<T (T, L)> apply_lazy_value;
    function<L (L, L)> update_lazy_value;
    function<L (ll, ll, L)> create_lazy_value;
    
public:
    LazySegmentTree(const vector<T> &v, 
                    const T &init_node,
                    const L &init_lazy, 
                    const decltype(merge_node)        &merge_node,
                    const decltype(apply_lazy_value)  &apply_lazy_value,
                    const decltype(update_lazy_value) &update_lazy_value,
                    const decltype(create_lazy_value) &create_lazy_value) 
        : init_node(init_node),
          init_lazy(init_lazy),
          merge_node(merge_node),
          apply_lazy_value(apply_lazy_value),
          update_lazy_value(update_lazy_value),
          create_lazy_value(create_lazy_value)
    {
        ll tmp = 1;
        while(tmp < v.size()) tmp *= 2;
        N = tmp;
        node.resize(2 * N - 1, init_node);
        lazy.resize(2 * N - 1, init_lazy);
        lazy_flag.resize(2 * N - 1, false);
        for(ll i = 0; i < v.size(); i++) {
            node[i + N - 1] = v[i];
        }
        for(ll i = N - 2; 0 <= i; i--) {
            node[i] = merge_node(node[i * 2 + 1], node[i * 2 + 2]);
        }
    }

    /*
     * node[pos] -> [left, right)
     */
    void lazy_eval(ll pos, ll left, ll right) {
        if(!lazy_flag[pos]) {
            return;
        }

        node[pos] = apply_lazy_value(node[pos], lazy[pos]);
        lazy_flag[pos] = false;

        /* 
         * whether the node is the bottom of tree or not.
         */
        if(right - left > 1) {
            for(ll idx : {2 * pos + 1, 2 * pos + 2}) {
                lazy[idx] = update_lazy_value(lazy[idx], lazy[pos]);
                lazy_flag[idx] = true;
            }
        }

        lazy[pos] = init_lazy;
    }

    /*
     * If you want to call this func from out of class, in many cases you don't have to change the args pos, node_left, node_right.
     * Be careful that the range is half-open interval.
     * [left, right), [node_left, node_right)
     * @param left:         lower limit of interval of query
     * @param right:        upper limit of interval of query
     * @param val:          the value gave from query
     * @param node_left:    lower limit of interval of the node points.
     * @param node_right:   upper limit of interval of the node points.
     */
    void update_query(ll left, ll right, ll val, ll pos = 0, ll node_left = 0, ll node_right = -1) {
        if(node_right < 0) {
            node_right = N;
        }

        /*
         * Execute lazy evaluation.
         */
        lazy_eval(pos, node_left, node_right);

        /*
         * If the node is out of inrerval, return.
         */
        if(right <= node_left || node_right <= left) {
            return;
        }


        /*
         * If the node cover the interval complety, update this->lazy and execute lazy_eval.
         * Else recursion.
         */
        if(left <= node_left && node_right <= right) {
            lazy[pos] = create_lazy_value(node_left, node_right, val);
            lazy_flag[pos] = true;
            lazy_eval(pos, node_left, node_right);
        }else{

            /*
             * recursion
             */
            update_query(left, right, val, 2 * pos + 1, node_left, (node_left + node_right) / 2);
            update_query(left, right, val, 2 * pos + 2, (node_left + node_right) / 2, node_right);

            node[pos] = merge_node(node[2 * pos + 1], node[2 * pos + 2]);
        }
    }

    T get_query(ll left, ll right, ll pos = 0, ll node_left = 0, ll node_right = -1) {
        if(node_right < 0) {
            node_right = N;
        }

        /*
         * Evaluate the node[pos]
         */
        lazy_eval(pos, node_left, node_right);

        if(node_right <= left || right <= node_left) {
            return init_node;
        }
        if(left <= node_left && node_right <= right) {
            return node[pos];
        }

        ll split = (node_left + node_right) / 2;
        return merge_node(get_query(left, right, 2 * pos + 1, node_left, split),
                          get_query(left, right, 2 * pos + 2, split, node_right));
    }
};

const ll MOD = 1e9 + 7;

template <typename T>
class Bit {
private:
    V<T> data;
    T identity_ele;

public:
    Bit(ll size, T identity_ele) : identity_ele(identity_ele) {
        ll newsize = 1;
        while(newsize < size) {
            newsize = newsize << 1;
        }
        data = V<T>(newsize + 1, identity_ele);
    }

    /*
     * 0-origin
     * sum of [0, pos)
     */
    T sum(ll pos) {
        T ret = identity_ele;
        while(pos > 0) {
            (ret += data[pos]) %= MOD;
            pos -= pos & -pos;
        }
        return ret;
    }

    /*
     * 0-origin
     * sum of [l, r)
     */
    T sum(ll l, ll r) {
        return (sum(r) - sum(l) + MOD) % MOD;
    }

    /*
     * 0-origin
     */
    void add(ll pos, T delta) {
        pos++;
        while(pos <= data.size()) {
            data[pos] = data[pos] + delta;
            pos += pos & -pos;
        }
    }
};

int main() {
    init_io();
    ll N, M, K;
    cin >> N >> M >> K;
    Bit<ll> bt(N + 10, 0);
    bt.add(0, 1);
    V<PLL> elev;
    for(ll i = 0; i < M; i++) {
        ll l, r;
        cin >> l >> r;
        l--;
        elev.emplace_back(l, r);
    }
    for(ll i = 0; i < K; i++) {
        V<ll> imos(N + 10, 0);
        for(const auto &ele : elev) {
            ll l, r;
            tie(l, r) = ele;
            auto tmp = bt.sum(l, r);
            DEBUG(tmp);
            imos[l] += tmp;
            imos[r] -= tmp;
        }
        for(ll i = 0; i < N; i++) (imos[i + 1] += imos[i]) %= MOD;
        Bit<ll> bts(N + 10, 0);
        for(ll i = 0; i < N; i++) bts.add(i, imos[i]);
        bt = move(bts);
    }
    cout << bt.sum(N - 1, N) << endl;
    return 0;
}