#406146 (C++17) No.945 YKC饅頭

提出ソース
結果

問題	No.945 YKC饅頭
コンテスト
ユーザー	btk
提出日時	2019-12-08 00:35:18
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	413 ms / 2,000 ms
コード長	15,892 bytes
コンパイル時間	2,309 ms
コンパイル使用メモリ	213,140 KB
最終ジャッジ日時	2025-01-08 09:40:42
ジャッジサーバーID （参考情報）	judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 74
権限があれば一括ダウンロードができます
ソースコード

raw source code
// https://yukicoder.me/problems/no/945
#define CIN_ONLY
#define DECIMAL_DIGITS 10
#define STATIC_MOD 1e9 + 7

#ifdef BTK
/*<head>*/
#    include "Template.hpp"
/*</head>*/
#else
/*<body>*/
/* #region auto includes */
/* #region stl */
/*<stl>*/
#    include <bits/stdc++.h>
#    include <sys/types.h>
#    include <unistd.h>
using namespace std;
/*</stl>*/
/* #endregion */
/* #region template/IncludeSTL.hpp*/
/**
 * @file IncludeSTL.hpp
 * @author btk
 * @brief 標準ライブラリをincludeするだけ
 * @version 0.1
 * @date 2019-07-21
 * @todo 何故か2回includeされる（展開scriptに
 * @copyright Copyright (c) 2019
 *
 */


/* #endregion */
/* #region template/Macro.hpp*/
/**
 * @file Macro.hpp
 * @author btk
 * @brief マクロとか，LLとか
 * @version 0.1
 * @date 2019-07-13
 *
 * @copyright Copyright (c) 2019
 *
 */


//! LL
using LL = long long;

/**
 * @def DEBUG
 * @brief デバッグ用のif文 提出時はif(0)で実行されない
 */

/*</head>*/
#    ifdef BTK
#        define DEBUG if (1)
#    else
#        ifdef CIN_ONLY
#            define FAST_IO
#        endif
#        define DEBUG if (0)
#    endif
/**
 * @def ALL(v)
 * @brief
 * ALLマクロ
 */
#    define ALL(v) (v).begin(), (v).end()

/**
 * @def REC(ret, ...)
 * @brief
 * 再帰ラムダをするためのマクロ
 */
#    define REC(ret, ...) std::function<ret(__VA_ARGS__)>

/**
 * @def VAR_NAME(var)
 * @brief 変数名を取得する
 */
#    define VAR_NAME(var) #    var

/**
 * @brief
 * rangeで生まれる使わない変数を消す用（警告消し）
 */
template <typename T>
inline T &unused_var(T &v) {
    return v;
}
/* #endregion */
/* #region template/IO.hpp*/
/**
 * @file IO.hpp
 * @author btk
 * @brief cin高速化とか，出力の小数桁固定とか
 * @version 0.1
 * @date 2019-07-13
 *
 * @copyright Copyright (c) 2019
 */


/**
 * @brief 入出力の設定を行うための構造体
 */
struct cww {
    /**
     * @brief Construct a new cww::cww object
     * @details
     * CIN_ONLYを定義すると，submit時にcinとscanfの同期を切る設定が走る
     * DECIMAL_DIGITSを定義すると，doubleの出力時指定した桁数分小数部を吐くようになる
     */
    cww() {
#    ifdef FAST_IO
        ios::sync_with_stdio(false);
        cin.tie(0);
#    endif
#    ifdef DECIMAL_DIGITS
        cout << fixed;
        cout << setprecision(DECIMAL_DIGITS);
#    endif
    }
};

//! 入出力設定構造体を実体化
cww star;

/**
 * @brief
 * vectorに直接cin流すためのやつ
 * @tparam T
 * @param is
 * @param v
 * @return istream&
 */
template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (auto &it : v) is >> it;
    return is;
}
/* #endregion */
/* #region template/Loop.hpp*/
/**
 * @file Loop.hpp
 * @author btk
 * @brief rangeとかループ系のクラス
 * @version 0.1
 * @date 2019-07-13
 *
 * @copyright Copyright (c) 2019
 *
 */


/**
 * @brief
 * rangeを逆向きに操作したいとき用
 * @details
 * ループの範囲は[bg,ed)なので注意
 * @see range
 */
class reverse_range {
  private:
    struct I {
        int x;
        int operator*() { return x - 1; }
        bool operator!=(I &lhs) { return x > lhs.x; }
        void operator++() { --x; }
    };
    I i, n;

  public:
    /**
     * @brief Construct a new reverse range object
     *
     * @param n
     */
    reverse_range(int n) : i({0}), n({n}) {}
    /**
     * @brief Construct a new reverse range object
     *
     * @param i
     * @param n
     */
    reverse_range(int i, int n) : i({i}), n({n}) {}
    /**
     * @brief
     * begin iterator
     * @return I&
     */
    I &begin() { return n; }
    /**
     * @brief
     * end iterator
     * @return I&
     */
    I &end() { return i; }
};
/**
 * @brief
 * python みたいな range-based for を実現
 * @details
 * ループの範囲は[bg,ed)なので注意
 * !つけると逆向きにループが回る (reverse_range)
 * 空間計算量はO(1)
 * 使わない変数ができて警告が出がちなので，unused_varとかを使って警告消しするとよい
 */
class range {
  private:
    struct I {
        int x;
        int operator*() { return x; }
        bool operator!=(I &lhs) { return x < lhs.x; }
        void operator++() { ++x; }
    };
    I i, n;

  public:
    /**
     * @brief Construct a new range object
     *
     * @param n
     */
    range(int n) : i({0}), n({n}) {}
    /**
     * @brief Construct a new range object
     *
     * @param i
     * @param n
     */
    range(int i, int n) : i({i}), n({n}) {}
    /**
     * @brief
     * begin iterator
     * @return I&
     */
    I &begin() { return i; }
    /**
     * @brief
     * end iterator
     * @return I&
     */
    I &end() { return n; }
    /**
     * @brief
     * 逆向きに参照するrange(reverse_rangeを取得できるs)
     * @return reverse_range
     */
    reverse_range operator!() { return reverse_range(*i, *n); }
};
/* #endregion */
/* #region template/MinMaxOperation.hpp*/
/**
 * @file MinMaxOperation.hpp
 * @author btk
 * @brief 最大値とか最小値を求める
 * @version 0.1
 * @date 2019-07-04
 *
 * @copyright Copyright (c) 2019
 *
 */

/**
 * @brief 2項の最小値求める
 *
 * @tparam T
 */
template <typename T>
struct min_op {
    /**
     * @brief 本体
     *
     * @param l
     * @param r
     * @return T
     */
    static T exec(const T l, const T r) { return l < r ? l : r; }
};

/**
 * @brief 2項の最大値求める
 *
 * @tparam T
 */
template <typename T>
struct max_op {
    /**
     * @brief 本体
     *
     * @param l
     * @param r
     * @return T
     */
    static T exec(const T l, const T r) { return l > r ? l : r; }
};

/**
 * @brief テンプレート再帰の末尾
 *
 * @tparam F 二項演算
 * @tparam T
 * @param v
 * @return T
 */
template <typename F, typename T>
inline T multi_op(T &&v) {
    return v;
}

/**
 * @brief 複数項における演算の結果を返す
 *
 * @tparam F
 * @tparam T
 * @tparam Ts
 * @param head
 * @param tail
 * @return T
 */
template <typename F, typename T, typename... Ts>
inline T multi_op(const T head, Ts &&... tail) {
    return F::exec(head, multi_op<F>(tail...));
}

/**
 * @brief 複数項の最小値
 * @see multi_op
 * @tparam T
 * @tparam Ts
 * @param head
 * @param tail
 * @return T
 */
template <typename T, typename... Ts>
inline T multi_min(T &&head, Ts &&... tail) {
    return multi_op<min_op<T>>(head, tail...);
}

/**
 * @brief 複数項の最大値
 * @see multi_op
 * @tparam T
 * @tparam Ts
 * @param head
 * @param tail
 * @return T
 */
template <typename T, typename... Ts>
inline T multi_max(T &&head, Ts &&... tail) {
    return multi_op<max_op<T>>(head, tail...);
}

/**
 * @brief
 * 先頭の値をFで参照する関数に基づいて変更できたらする
 * @tparam F
 * @tparam T
 * @tparam Ts
 * @param target
 * @param candidates
 * @return true
 * @return false
 */
template <typename F, typename T, typename... Ts>
inline bool ch_op(T &target, Ts &&... candidates) {
    const T old = target;
    target      = multi_op<F>(target, candidates...);
    return old != target;
}

/**
 * @brief change min
 * @tparam T 型
 * @param target 変更する値
 * @param candidates
 * @return 更新があればtrue
 */
template <typename T, typename... Ts>
inline bool chmin(T &target, Ts &&... candidates) {
    return ch_op<min_op<T>>(target, candidates...);
}

/**
 * @brief chminのmax版
 * @see chmin
 *  @tparam T 型
 * @param target 変更する値
 * @param candidates
 * @return 更新があればtrue
 */
template <typename T, typename... Ts>
inline bool chmax(T &target, Ts &&... candidates) {
    return ch_op<max_op<T>>(target, candidates...);
}
/* #endregion */
/* #region template/Random.hpp*/
/**
 * @file Random.hpp
 * @author btk
 * @brief 乱数生成系
 * @version 0.1
 * @date 2019-07-13
 * @copyright Copyright (c) 2019
 */


//! 乱数のシード値をプロセスIDとして取得
const pid_t pid = getpid();

/**
 * @brief XorShift32の実装
 */
class XorShift32 {
  private:
    //! XorShiftの現在の値
    unsigned value;

    /**
     * @brief XorShift32のアルゴリズムに基づいて value を更新
     */
    inline void update() {
        value = value ^ (value << 13);
        value = value ^ (value >> 17);
        value = value ^ (value << 5);
    }

    /**
     * @brief 値を更新し，更新前の値を返却
     * @return unsigned 呼び出し時の value を用いる
     */
    inline unsigned get() {
        unsigned v = value;
        update();
        return v;
    }

  public:
    /**
     * @brief [0, 2^bit) の範囲の乱数値を取り出す
     * @tparam デフォルトは31
     * @return int
     */
    template <int bit = 31>
    inline int next_int() {
        return (int)(get() >> (32 - bit));
    }

    /**
     * @brief [-2^bit,2^bit)の範囲の乱数値を取り出す
     * @tparam デフォルトは31
     * @return int
     */
    template <int bit = 31>
    inline int next_signed() {
        unsigned v = get();
        return (int)((v >> (31 - bit)) - (1 << (bit)));
    }

    /**
     * @brief next_int呼び出し時の最大値を取得
     * @tparam 31
     * @return int
     */
    template <int bit = 31>
    inline int range_max() {
        return (int)((1u << bit) - 1);
    };

    /**
     * @brief Construct a new XorShift32 object
     * @param seed
     * @details 初期シードをvalueとするXorShift32のインスタンスを生成
     */
    XorShift32(const unsigned seed) {
        value = seed;
        update();
    }

    /**
     * @brief Construct a new XorShift 32 object
     * @details 初期シードをプロセスIDとするXorShift32のインスタンスを生成
     */
    XorShift32() : XorShift32(pid) {}
};
/* #endregion */
/* #region Template.hpp*/
/**
 * @file Template.hpp
 * @brief 競技プログラミング用テンプレート
 * @author btk15049
 * @date 2019/05/02
 */


/* #endregion */
/* #endregion */
/*</body>*/
#endif


/*
default:: range minimum query
- update(element) : chmin (weak update), set (force update)
- get   (segment) : min(l,r)
*/

constexpr int INF = 1e7;
template <typename SEG>
using SetInitialLeaf = function<void(SEG &, int)>;
template <typename SEG>
using SetInitialSegment = function<void(SEG &, const int, const int)>;
template <typename RET, typename SEG>
using GetSingleSegment = function<RET(SEG &, const int, const int)>;
template <typename RET>
using GetMergedSegment = function<RET(RET, RET)>;
template <typename SEG, typename Q>
using UpdateSingleSegment = function<void(SEG &, Q)>;
template <typename SEG>
using LazyUpdate = function<void(SEG &, SEG &, SEG &)>;

struct node {
    int ret;
    bool all;
};


SetInitialLeaf<node> set_leaf = [](node &v, const int id) {
    v.ret = 0;
    v.all = false;
};

SetInitialSegment<node> set_segment = [](node &v, const int l, const int r) {
    v.all = false;
};

GetSingleSegment<int, node> segment_sum = [](node &v, const int l,
                                             const int r) {
    if (v.all) {
        return r - l;
    }
    else {
        return v.ret;
    }
};

GetMergedSegment<int> merge_segment = [](int l, int r) { return l + r; };

UpdateSingleSegment<node, int> update = [](node &v, int l) { v.all = true; };

LazyUpdate<node> lazy = [](node &v, node &l, node &r) {
    l.all |= v.all;
    r.all |= v.all;
};

#ifndef NDBUF
#    define NDBUF
template <typename T>
struct BufferManager {
    T *mem;
    int ptr;
    BufferManager(T *mem) {
        ptr       = 0;
        this->mem = mem;
    }
    T *get(int m) {
        ptr += m;
        return mem + ptr - m;
    }
    void reset() { ptr = 0; }
};

namespace NodeBuffer {
    constexpr int BufferSize = 812345;
    using NodeType           = node;
    NodeType mem[BufferSize];
    BufferManager<NodeType> buffer(mem);
} // namespace NodeBuffer
#endif

template <typename Node, typename RET>
struct SegmentTree {
    int size;
    Node *seg;
    GetSingleSegment<RET, Node> get_single_segment;
    GetMergedSegment<RET> get_merged_segment;
    LazyUpdate<Node> lazy_update;
    void init(int l, int r, SetInitialSegment<Node> &init_segment,
              SetInitialLeaf<Node> &init_leaf, int k = 0) {
        auto &v = seg[k];
        init_segment(v, l, r);
        if (r - l == 1) {
            //葉の時の処理
            init_leaf(v, l);
        }
        else if (r - l > 1) {
            int m = (l + r) / 2;
            init(l, m, init_segment, init_leaf, k * 2 + 1);
            init(m, r, init_segment, init_leaf, k * 2 + 2);
            v.ret =
                get_merged_segment(get_single_segment(seg[k * 2 + 1], l, m),
                                   get_single_segment(seg[k * 2 + 2], m, r));
        }
    }
    SegmentTree(int n, GetSingleSegment<RET, Node> gss,
                GetMergedSegment<RET> gms, SetInitialSegment<Node> sis,
                SetInitialLeaf<Node> sil,
                LazyUpdate<Node> lu      = [](Node &v, Node &l, Node &r) {},
                BufferManager<Node> &buf = NodeBuffer::buffer)
        : get_single_segment(gss), get_merged_segment(gms), lazy_update(lu) {
        size = 1;
        while (size < n) size *= 2;
        seg = buf.get(size * 2 + 10);
        init(0, size, sis, sil);
    }
#define LQ a, b, k * 2 + 1, l, m
#define RQ a, b, k * 2 + 2, m, r
    RET get(int a, int b, int k, int l, int r) {
        if (a <= l && r <= b) return get_single_segment(seg[k], l, r);
        if (r - l > 1) lazy_update(seg[k], seg[2 * k + 1], seg[2 * k + 2]);
        int m   = (l + r) / 2;
        bool ll = !(m <= a || b <= l);
        bool rr = !(r <= a || b <= m);
        RET ret;
        if (ll && rr)
            ret = get_merged_segment(get(LQ), get(RQ));
        else if (ll)
            ret = get(LQ);
        else
            ret = get(RQ);
        seg[k].ret =
            get_merged_segment(get_single_segment(seg[k * 2 + 1], l, m),
                               get_single_segment(seg[k * 2 + 2], m, r));
        return ret;
    }
    RET get(int a, int b) { return get(a, b, 0, 0, size); }
    template <typename Q>
    void update(int a, int b, int k, int l, int r,
                UpdateSingleSegment<Node, Q> &update_segment, Q value) {
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            update_segment(seg[k], value);
        }
        else {
            if (r - l > 1) lazy_update(seg[k], seg[2 * k + 1], seg[2 * k + 2]);
            int m = (l + r) / 2;
            update(LQ, update_segment, value);
            update(RQ, update_segment, value);
            seg[k].ret =
                get_merged_segment(get_single_segment(seg[k * 2 + 1], l, m),
                                   get_single_segment(seg[k * 2 + 2], m, r));
        }
    }
    template <typename Q>
    void update_segment(int a, int b,
                        UpdateSingleSegment<Node, Q> &update_segment, Q value) {
        update(a, b, 0, 0, size, update_segment, value);
    }

    template <typename Q>
    void update_element(int a, UpdateSingleSegment<Node, Q> &update_segment,
                        Q value) {
        update(a, a + 1, 0, 0, size, update_segment, value);
    }
};


int main() {
    /* write here */
    int N, M;
    cin >> N >> M;
    map<string, int> ret;
    SegmentTree<node, int> tree(N + 10, segment_sum, merge_segment, set_segment,
                                set_leaf, lazy);
    for (int i : range(M)) {
        int l, r;
        string s;
        cin >> l >> r >> s;
        l--;
        int add_val = (r - l) - tree.get(l, r);
        ret[s] += add_val;
        //cerr << add_val << endl;
        tree.update_segment(l, r, update, 1);
    }
    cout << ret["Y"] << " ";
    cout << ret["K"] << " ";
    cout << ret["C"] << endl;

    return 0;
}