みんみんみん [PG BATTLE 2019 せんべい D]

https://products.sint.co.jp/hubfs/resource/topsic/pgb/2-4.pdf

前提知識

• 平面走査
• 座標圧縮
• 区間minセグメントツリー

解説

入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください

公式解説

ライブラリ力があれば、セグメントツリーにセグメントツリーを乗せるテクで2Dセグツリーをして、z軸で平面走査すれば一瞬で解ける。
想定解では無いだろうから他をあたってみる。

他をあたってみるが、平面走査をすれば軸を1つ減らせそう。
あと、大小関係のみが重要なので、座標圧縮はできそう。
問題文から弱点を引き出してみると、判定してくださいというyes/no問題になっている部分である。

あるx座標を見ているとき、x座標がそれより小さい頂点での(y座標,z座標)について考えたとき、
今のy座標よりも小さいy座標の中で最もz座標が小さい頂点を取ってくれば、最適な比較ができる。
これは区間minのセグメントツリーにて実現できる。
平面走査・座標圧縮・セグメントツリーと要求知識が多い問題。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
#define def inf
template<class V, int NV> struct SegTree { //[l,r)
    V comp(V& l, V& r) { return min(l, r); };

    vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
    V get(int x, int y, int l = 0, int r = NV, int k = 1) {
        if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
        auto a = get(x, y, l, (l + r) / 2, k * 2); 
        auto b = get(x, y, (l + r) / 2, r, k * 2 + 1);
        return comp(a, b);
    }
    void update(int i, V v) {
        i += NV; val[i] = v;
        while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
    }
    void add(int i, V v) { update(i, val[i + NV] + v); }
    V operator[](int x) { return get(x, x + 1); }
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/

int N, X[101010], Y[101010], Z[101010];
SegTree<int, 1 << 17> st;
string ans[101010];
//---------------------------------------------------------------------------------------------------
vector<int> compress1(int *v, int n) {
    vector<int> dic;
    rep(i, 0, n) dic.push_back(v[i]);
    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());
    rep(i, 0, n) v[i] = lower_bound(all(dic), v[i]) - dic.begin();
    return dic;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i] >> Y[i] >> Z[i];

    compress1(X, N);
    compress1(Y, N);
    compress1(Z, N);

    map<int, vector<int>> ord;
    rep(i, 0, N) ord[X[i]].push_back(i);

    fore(p, ord) {
        auto &v = p.second;

        fore(i, v) {
            int min_z = st.get(0, Y[i]);
            if (min_z < Z[i]) ans[i] = "Yes";
            else ans[i] = "No";
        }

        fore(i, v) st.update(Y[i], min(st[Y[i]], Z[i]));
    }

    rep(i, 0, N) printf("%s\n", ans[i].c_str());
}