Submission #61178676

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define INF LONG_LONG_MAX

struct segtreemin {
    int n;
    vector<int> tree;

    segtreemin(int size) : n(size), tree(4 * size, INF) {}

    void build(const vector<int>& a, int v, int tl, int tr) {
        if (tl == tr) {
            tree[v] = a[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(a, 2 * v + 1, tl, tm);
            build(a, 2 * v + 2, tm + 1, tr);
            tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
        }
    }

    int query(int v, int tl, int tr, int l, int r) {
        if (l > r) return INF;
        if (l == tl && r == tr) return tree[v];
        int tm = (tl + tr) / 2;
        return min(query(2 * v + 1, tl, tm, l, min(r, tm)),
               query(2 * v + 2, tm + 1, tr, max(l, tm + 1), r));
    }

    void update(int v, int tl, int tr, int pos, int new_val) {
        if (tl == tr) {
            tree[v] = new_val;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) update(2 * v + 1, tl, tm, pos, new_val);
            else update(2 * v + 2, tm + 1, tr, pos, new_val);
            tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
        }
    }

    void build(const vector<int>& a) {
        build(a, 0, 0, n - 1);
    }

    int query(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }

    void update(int pos, int new_val) {
        update(0, 0, n - 1, pos, new_val);
    }
};

struct segtree {
    int n;
    vector<int> tree;

    segtree(int size) : n(size), tree(4 * size) {}

    void build(const vector<int>& a, int v, int tl, int tr) {
        if (tl == tr) {
            tree[v] = a[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(a, 2 * v + 1, tl, tm);
            build(a, 2 * v + 2, tm + 1, tr);
            tree[v] = max(tree[2 * v + 1], tree[2 * v + 2]);
        }
    }

    int query(int v, int tl, int tr, int l, int r) {
        if (l > r) return 0;
        if (l == tl && r == tr) return tree[v];
        int tm = (tl + tr) / 2;
        return max(query(2 * v + 1, tl, tm, l, min(r, tm)),
               query(2 * v + 2, tm + 1, tr, max(l, tm + 1), r));
    }

    void update(int v, int tl, int tr, int pos, int new_val) {
        if (tl == tr) {
            tree[v] = new_val;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) update(2 * v + 1, tl, tm, pos, new_val);
            else update(2 * v + 2, tm + 1, tr, pos, new_val);
            tree[v] = max(tree[2 * v + 1], tree[2 * v + 2]);
        }
    }

    void build(const vector<int>& a) {
        build(a, 0, 0, n - 1);
    }

    int query(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }

    void update(int pos, int new_val) {
        update(0, 0, n - 1, pos, new_val);
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    set<int> a, b;
    vector<tuple<int, int, char>> v;
    while (m--) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        a.insert(x);
        b.insert(y);
        v.emplace_back(x, y, c);
    }
    vector<int> A, B;
    for (int i : a) A.emplace_back(i);
    for (int i : b) B.emplace_back(i);
    segtreemin ox(A.size()), oy(B.size());
    segtree qx(A.size()), qy(B.size());
    for (auto [x, y, c] : v) {
        int l = lower_bound(all(A), x) - A.begin(), r = lower_bound(all(B), y) - B.begin();
        if (c == 'W') {
            if (qx.query(l, A.size() - 1) > y || qy.query(r, B.size() - 1) > x) return cout << "No", 0;
            int Y = ox.query(l, l), X = oy.query(r, r);
            if (Y > y) ox.update(l, y);
            if (X > x) oy.update(r, x);
        }
        else {
            if (ox.query(0, l) < y || oy.query(0, r) < x) return cout << "No", 0;
            int Y = qx.query(l, l), X = qy.query(r, r);
            if (Y < y) qx.update(l, y);
            if (X < x) qy.update(r, x);
        }
    }
    cout << "Yes";
    return 0;
}

Submission Info

Judge Result