提出 #61199591

---

ソースコード 拡げる

#ifndef ATCODER // AtCoder 環境でない場合はデバッグモードを有効にする. コンパイルにすごく時間がかかる！
#define _GLIBCXX_DEBUG // out of rangeを検出してくれる。#include<bits/stdc++.h>の前に記述する必要あり
#endif
#include<bits/stdc++.h>
using namespace std;
struct IOSetup {
    IOSetup() {
        // 実行が高速化するコード
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        // 小数点以下10桁まで(四捨五入)
        cout << fixed << setprecision(10);
    }
} iosetup;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep2(i, a, b) for (int i = a; i < b; i++)
#define rrep2(i, b, a) for (int i = b; i > a; i--)
#define rep3(i, a, b, d) for (int i = a; i < b; i+=d)
#define rrep3(i, b, a, d) for (int i = b; i > a; i-=d)
#define between(x, a, b) (((a) <= (x)) && ((x) < (b)))

/*
セグメントツリーは、配列の区間に対するクエリ処理や更新を効率的に行うためのデータ構造です。
特に、区間の和や積、最小値や最大値といった集約情報を迅速に取得する際に便利です。
*/
#include <bits/stdc++.h> // 必要なヘッダファイルをインクルード
using namespace std;

// セグメント木の定義
template<class Monoid> // template<typename Monoid> と書いても同様に機能します。歴史的にclassが使われている。
struct SegmentTree {
    // function<double(int, int)> int 型の引数を2つ取って double 型の値を返す関数
    using Func = function<Monoid(Monoid, Monoid)>; // 二項演算子の型を定義
    // functionは関数を変数として扱う型
    

    // ここはpublic.
    // コアメンバー
    int N; // 配列のサイズ
    Func OP; // 操作を定義する関数
    Monoid IDENTITY; // 単位元

    // 内部データ
    int log, offset; // log は木の高さ、offset は葉の始まりを示す
    vector<Monoid> data; // セグメント木のデータを格納する配列

    // コンストラクタ
    SegmentTree() {} // デフォルトコンストラクタ
    SegmentTree(int n, const Func &op, const Monoid &identity) { // サイズn、操作op、単位元identityで初期化
        init(n, op, identity);
    }
    SegmentTree(const vector<Monoid> &v, const Func &op, const Monoid &identity) { // ベクタから初期化
        init(v, op, identity);
    }
    
    // 初期化関数
    void init(int n, const Func &op, const Monoid &identity) {
        N = n; // サイズを設定
        OP = op; // 操作を設定
        IDENTITY = identity; // 単位元を設定
        log = 0, offset = 1; // log と offset を初期化
        while (offset < N) { // n以上の最小の2の冪乗を返す. 
            ++log; // 木の深さを計算.
            offset <<= 1; // 葉の数を計算(2のべき乗).
            // N = 6 なら log = 3, offset = 8; N = 8 なら log = 3, offset = 8, N = 9 なら log = 4, offset = 16;
        }
        data.assign(offset * 2, IDENTITY); // offset * 2 で葉ノードと内部ノードの領域を確保、完全2分木構造を作成.
        // 葉ノードは、配列の下半分（通常 offset から 2 * offset の範囲）に配置されます。offset は葉ノードの開始インデックスを表します。
        // 内部ノードは、葉ノードよりも上の部分に格納され、offset - 1 より小さいインデックスに配置されます.
        // data[1] が根ノード
        // 5個の要素を10で初期化
        // vec.assign(5, 10); → 10, 10, 10, 10, 10;
        // vector<int> data(16)なら、
        // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
        // - |     内部ノード     |       　葉ノード　　　　　　 |
    }
    
    // ベクタからの初期化
    void init(const vector<Monoid> &v, const Func &op, const Monoid &identity) {
        init((int)v.size(), op, identity); // サイズを取得して初期化
        build(v); // ベクタを使って木を構築
    }
    
    // ノードの値を親ノードに統合. 下から上に更新していくイメージ.
    void pull_update(int k) {
        data[k] = OP(data[k * 2], data[k * 2 + 1]); // 子ノードの値を使って親ノードの値を更新(1 - based indexed)
        // 葉ノードは、配列の下半分（通常 offset から 2 * offset の範囲）に配置されます.
        // 内部ノードは、葉ノードよりも上の部分に格納され、offset - 1 より小さいインデックスに配置されます.
    }
    
    // ベクタを使って木を構築
    void build(const vector<Monoid> &v) {
        assert(N == (int)v.size()); // サイズが一致することを確認. assert(False)だと、プログラムが強制終了.
        for (int i = 0; i < N; ++i) data[i + offset] = v[i]; // 葉に値を設定
        // 葉ノードは、配列の下半分（通常 offset から 2 * offset の範囲）に配置されます.
        for (int k = offset - 1; k > 0; --k) pull_update(k); // 親ノードを更新
    }
    
    // 木のサイズを返す
    int size() const {
        return N; // サイズを返す
    }
    
    // i番目の要素を取得
    Monoid operator [] (int i) const {
        return data[i + offset]; // オフセットを考慮して要素を返す
    }
    
    // A[i]をxにupdateする. iは0-indexed, O(log N)
    void update(int i, const Monoid &v) {
        assert(0 <= i && i < N); // インデックスの範囲を確認
        // オフセットを加算(0-indexed → 1-indexed)
        int k = i + offset;
        data[k] = v; // 値を更新
        while (k >>= 1) {
            pull_update(k); // 親ノードを更新
        }
        // k の値を2で割りながら親ノードに移動.
        // つまり k = 0は使わない！
    }
    
    // 区間 [l, r) のqueryを取得. lとrは0-indexed, O(log N)
    Monoid query(int l, int r) {
        assert(0 <= l && l <= r && r <= N); // 引数の範囲を確認
        Monoid val_left = IDENTITY, val_right = IDENTITY; // 左右の合計を初期化
        l += offset, r += offset; // オフセットを加算
        for (; l < r; l >>= 1, r >>= 1) { // lがr未満の間ループ. l と r を同時に2で割っていき、重なったら終了.
            if (l & 1) val_left = OP(val_left, data[l++]); // lが奇数のとき、左側の値を更新
            if (r & 1) val_right = OP(data[--r], val_right); // rが奇数のとき、右側の値を更新. 開区間のため、--rしている。
            // 例えば葉が11-14の時、11をそのまま2で割っていってしまうと、8, 9, 10の情報も交じってしまう。
            // それは望ましくないのでl++して二分木において右に移動することで回避する。
        }
        return OP(val_left, val_right); // 左右の合計を統合して返す
    }

    // 区間 [0, r) のqueryを取得. 引数いらない. 0とrは0-indexed, O(log N)
    Monoid all_query() {
        return data[1]; // 根ノードの値を返す（全体の合計）
    }
    
    // A[i]の値をgetする. iは0-indexed, O(log N)
    Monoid get(int i) {
        assert(0 <= i && i < N); // インデックスの範囲を確認
        return data[i + offset];
    }
    
    // A[i]の値を全てprintする. iは0-indexed, O(log N)
    void print_leaf_node() {
        for (int i = 0; i < N; i++) {
            cout << data[i + offset] << " ";
        }
        cout << endl;
    }
    
    // segment_treeの値(構造)をprintする. iは0-indexed, O(log N)
    void print_tree_node() {
        int next_endl = 2;
        for (int i = 1; i < data.size(); i++) {
            cout << data[i] << " ";
            if (i == next_endl - 1) {
                next_endl <<= 1;
                cout << endl;
            }
        }
        cout << endl;
    }
    
    // A[i]にxを加算する. iは0-indexed, O(log N)
    void add(int i, const Monoid &v) {
        assert(0 <= i && i < N); // インデックスの範囲を確認
        long long k = i + offset; // オフセットを加算
        data[k] = v + get(i); // 現在の値にvを加算
        while (k >>= 1) pull_update(k); // 親ノードを更新
    }
    // x = seg.prod(L, r) として、f(x) = True となる最大の r を求める
    // int res = seg.max_right([&](int x) -> bool { return V > x; }, L);
    int max_right_index(const function<bool(Monoid)> f, int l = 0) {
        if (l == N) return N; // lが範囲外の場合はNを返す
        l += offset; // lにオフセットを加算
        Monoid SUM = IDENTITY; // 合計を初期化
        do {
            while (l % 2 == 0) l >>= 1; // lが偶数の場合、親ノードに移動
            if (!f(OP(SUM, data[l]))) { // 条件を満たさない場合
                while (l < offset) {
                    l = l * 2; // 左の子ノードに移動
                    if (f(OP(SUM, data[l]))) { // 条件を満たす場合
                        SUM = OP(SUM, data[l]); // 合計を更新
                        ++l; // lを次の位置に移動
                    }
                }
                return l - offset; // 結果を返す
            }
            SUM = OP(SUM, data[l]); // 合計を更新
            ++l; // lを次に進める
        } while ((l & -l) != l);  // lが2のべき乗になるまでループ
        return N; // Nを返す
    }

    // get min l that f(get(l, r)) = True (0-indexed), O(log N)
    // f(IDENTITY) need to be True
    int min_left_index(const function<bool(Monoid)> f, int r = -1) {
        if (r == 0) return 0; // rが0の場合、0を返す
        if (r == -1) r = N; // rが-1の場合、全体のサイズを設定
        r += offset; // rにオフセットを加算
        Monoid SUM = IDENTITY; // 合計を初期化
        do {
            --r; // rを1減らす
            while (r > 1 && (r % 2)) r >>= 1; // rが奇数の間は親ノードに移動
            if (!f(OP(data[r], SUM))) { // 条件を満たさない場合
                while (r < offset) {
                    r = r * 2 + 1; // 右の子ノードに移動
                    if (f(OP(data[r], SUM))) { // 条件を満たす場合
                        SUM = OP(data[r], SUM); // 合計を更新
                        --r; // rを1減らす
                    }
                }
                return r + 1 - offset; // 結果を返す
            }
            SUM = OP(data[r], SUM); // 合計を更新
        } while ((r & -r) != r); // rが2のべき乗になるまでループ
        return 0; // 0を返す
    }
    
    // デバッグ用出力
    friend ostream& operator << (ostream &s, const SegmentTree &seg) {
        for (int i = 0; i < (int)seg.size(); ++i) { // サイズ分ループ
            s << seg[i]; // 各要素を出力
            if (i != (int)seg.size() - 1) s << " "; // 最後の要素でない場合、空白を追加
        }
        return s; // ストリームを返す
    }
};

/*
セグメントツリーの具体的な操作例と単位元:
操作:         query_func        単位元: ide_ele, 足し算でいう0, 掛け算でいう1.
最小値:       min(x, y)         単位元: float('inf')
最大値:       max(x, y)         単位元: -float('inf')
区間和:       x + y             単位元: 0
区間積:       x * y             単位元: 1
最大公約数:    gcd(x, y)        単位元: 0
最小公倍数:    lcm(x, y)        単位元: 1
*/

// main関数
int main() {
    // n: セグメント木のサイズ
    int n, m;
    cin >> n >> m;
    set<int> st;
    vector<tuple<int, int, char>> query;
    rep(i, m) {
        int x, y; char c;
        cin >> x >> y >> c;
        query.push_back({x, y, c});
    }
    for (auto& [x, y, c] : query) {
        st.insert(x);
    }
    map<int, int> d;
    int ind = 0;
    for (auto& i : st) {
        d[i] = ind;
        ind++;
    }

    m = st.size();
    vector<int> vec(m + 1);
    auto query_func = [&](int a, int b) { // やりたい操作を計算する関数
        return max(a, b); // やりたい操作を記述
    };
    int ide_ele = -(1 << 30);
    for (auto& [x, y, c] : query) {
        if (c == 'W') continue;
        ind = d[x];
        vec[ind] = max(y, vec[ind]);
    }
    SegmentTree<int> seg(vec, query_func, ide_ele); // セグメント木を初期化
    for (auto& [x, y, c] : query) {
        if (c == 'B') continue;
        ind = d[x];
        if ((seg.query(ind, m)) >= y) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    // x = seg.prod(L, r) として、f(x) = True となる最大の r を求める
    // int res = seg.max_right([&](int x) -> bool { return V > x; }, L);
}

提出情報

ジャッジ結果