734D - Anton and Chess - CodeForces Solution

/* Author: Pieck */
 
#include<bits/stdc++.h>
using namespace std;
using namespace chrono;
 
#pragma GCC optimize("-O2")
 
typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<ll> vl;
typedef pair<ll, ll> pl;
typedef vector<vector<ll>> matrix;
 
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
    for ( \
        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second; \
        debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
    )
#define F                         first
#define S                         second
#define PB                        push_back
#define PPB                       pop_back
#define MP                        make_pair
#define all(c)                    c.begin(), c.end()
#define f(i,a,b)                  for(ll i=a; i<b; i++)
#define rep(i,n)                  f(i,0,n)
#define fd(i, b, a)               for(ll i=b; i>=a; i--)
#define repr(i,n)                 fd(i, n-1, 0)
#define tr(c,i)                   for(typeof(c).begin() i = c.begin(); i != c.end(); i++)
#define present(c,x)              (c.find(x) != c.end())    //for set and map
#define cpresent(c,x)             (find(all(c),x) != c.end())    //for vectors
#define ps(num, places)           fixed<<setprecision(places)<<num //use as cout<<ps(x, y)<<"\n";
#define sz(x)                     (ll)(x).size()
 
void setIO() { 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout); 
}
 
void usaco(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}
 
template <typename T> void amax(T &a, T b) { a = max(a, b); }
template <typename T> void amin(T &a, T b) { a = min(a, b); }
 
const lld epsilon = 1e-9;
const ll MOD = 1e9+7;
const ll INF = 1e9;
 
bool comp(ll a, ll b) {
    return (a > b);
}
 
ll POW(ll a, ll b) {
    ll res = 1;
    while(b>0) {
        if(b&1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
 
ll binpow(ll a, ll b, ll p=MOD) {
    ll res = 1;
    a %= p;
    while(b>0) {
        if(b&1) (res *= a)%=p;
        (a *= a)%=p;
        b >>= 1;
        a %= p;
        res %= p;
    }
    return res;
}
 
void runcase() {
    ll n, x, y;
    cin >> n >> x >> y;
    map<ll, vl> rows, cols, diag1, diag2;
 
    auto push_elem = [&](ll u, ll v) {
        rows[u].PB(v);
        cols[v].PB(u);
        ll d1 = u+v, d2 = v-u;
        diag1[d1].PB(d2);
        diag2[d2].PB(d1);
    };
 
    vector<pair<char, pl>> pieces(n);
    rep(i, n) {
        char c;
        ll u, v;
        cin >> c >> u >> v;
        pieces[i] = {c, {u, v}};
        push_elem(u, v);
    }
 
    for(auto &x:rows) sort(all(x.S));
    for(auto &x:cols) sort(all(x.S));
    for(auto &x:diag1) sort(all(x.S));
    for(auto &x:diag2) sort(all(x.S));
 
    auto rook = [&](ll x, ll y, ll u, ll v) {
        bool inLine = ((x==u) || (y==v));
        if(!inLine) return 0;
 
        if(x==u) {
            ll pos = lower_bound(all(rows[u]), min(v, y)+1) - rows[u].begin();
            if(pos<sz(rows[u]) && rows[u][pos]<max(v, y)) return 0;
            return 1;
        }else {
            ll pos = lower_bound(all(cols[v]), min(u, x)+1) - cols[v].begin();
            if(pos<sz(cols[v]) && cols[v][pos]<max(u, x)) return 0;
            return 1;
        }
    };
 
    auto bishop = [&](ll x, ll y, ll u, ll v) {
        ll d1 = x+y, d2 = y-x;
        ll h1 = u+v, h2 = v-u;
        bool inLine = (d1==h1 || d2==h2);
        if(!inLine) return 0;
 
        if(d1==h1) {
            ll pos = lower_bound(all(diag1[h1]), min(d2, h2)+1) - diag1[h1].begin();
            if(pos<sz(diag1[h1]) && diag1[h1][pos]<max(d2, h2)) return 0;
            return 1;
        }else {
            ll pos = lower_bound(all(diag2[h2]), min(d1, h1)+1) - diag2[h2].begin();
            if(pos<sz(diag2[h2]) && diag2[h2][pos]<max(d1, h1)) return 0;
            return 1;
        }
    };
 
    bool isInCheck = 0;
    rep(i, n) {
        char c = pieces[i].F;
        ll u = pieces[i].S.F, v = pieces[i].S.S;
        if(c=='R' || c=='Q') isInCheck |= rook(x, y, u, v);
        if(c=='B' || c=='Q') isInCheck |= bishop(x, y, u, v);
    }
    cout<<(isInCheck?"YES":"NO")<<"\n";
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.precision(10);
    #ifndef ONLINE_JUDGE
        setIO();
        // usaco("");
    #endif
    time__("Main") {
        ll tests = 1;
        // cin >> tests;
        while(tests--) {
            runcase();
        }
    }
    return 0;
}