【PGBATTLE2019_せんべい4】みんみんみん

[Q] https://products.sint.co.jp/q_list

1. xでsort
2. y以下の中からzの最小値を出す。zminがクエリのzを下回るならok。
3. マッピング。seg[y] = zを記録しておく。
座標圧縮+セグ木でした。

・xが同じ値の場合の処理に注意。
1 1 1
1 2 3
があったとして、1 1 1を判定し、1 1 1をマッピングすると、1 2 3の判定でokが出てしまう。

対策：yを反転させてsort
1 -1 1
1 -2 3
走査時に復元し 1 2 3 -> 1 1 1 の処理をすると、妨害を防げる。

Q. tuple<ll, ll, ll, ll> をどうとりだすの？
A. c++17構造体束縛を利用できる。

・init
 vector<tuple<ll, ll, ll, ll>> T(N);
 rep(i, N){
   ll x, y, z;
   cin >> x >> y >> z;
   T[i] = {x, -y, z, i};
 }

 sort(all(T));
 map<ll, ll> mp;


・取り出し
 rep(i, N){
   auto&[a, b, c, d] = T[i];
   mp[-b] = 0;
   mp[c] = 0;
 }

実装

class RangeMin{
public:
 ll size_ = 1;
 vector<ll> dat;
 void init(ll sz){
   while (size_ <= sz) size_ *= 2;
   dat.resize(size_ * 2, oo);
 }
 void update(ll pos, ll x){
   pos += size_;
   if (!chmin(dat[pos], x))
     return ;
   while (pos >= 2){
     pos >>= 1;
     dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
   }
 }
 
 ll query_(ll l, ll r, ll k, ll a, ll b){
   if (r <= a || b <= l) return oo;
   if (l <= a && b <= r) return dat[k];
   ll v1 = query_(l, r, k*2, a, (a+b)>>1);
   ll v2 = query_(l, r, k*2+1, (a+b)>>1, b);
   return min(v1, v2);
 }
 
 ll query(ll l, ll r){
   return query_(l, r, 1, 0, size_);
 }
 
 ll getval(ll id){
   id += size_;
   return (dat[id]);
 }
};

int main(){
 cincout();

 ll N;
 cin >> N;
 vector<tuple<ll, ll, ll, ll>> T(N);
 rep(i, N){
   ll x, y, z;
   cin >> x >> y >> z;
   T[i] = {x, -y, z, i};
 }
 sort(all(T));
 map<ll, ll> mp;
 rep(i, N){
   auto&[a, b, c, d] = T[i];
   mp[-b] = 0;
   mp[c] = 0;
 }
 ll id=0;
 for(auto m:mp)mp[m.first] = ++id;
 rep(i, N){
   auto&[a, b, c, d] = T[i];
   b = mp[-b];
   c = mp[c];
 }

 bool ans[N] = {};
 RangeMin Z;
 Z.init(N*2+10);
 ll &pre = get<0>(T[0]);
 queue<pair<ll, ll>> Q;
 rep(i, N){
   auto&[a, b, c, id] = T[i];
   ll high = Z.query(0, b);
   if (high < c) ans[id] = true;
   Z.update(b, c); // id, val
 }
 rep(i, N){
   if (ans[i]) cout << "Yes" << endl;
   else cout << "No" << endl;
 }
}