2020 Petrozavodsk Winter Camp, Jagiellonian U Contest E問題 Contamination

問題ページ

概要

個の円(中心がで半径) が存在
個のクエリが与えられる
2点を以下の条件を満たしつつ行き来できるか？

• 円の内部を通らない
• となる範囲のみ

円は重ならない

解法

と仮定しても一般性を失わない。クエリが'NO'となる条件は「 かつ となる円が存在する」ことである。

この判定は平面走査でできる。 のときに を含む円の上端 となるようにセグ木を保持して管理する。 を小さい方から動かしていく。このときセグ木を更新するタイミングは以下の3パターンである。

• 円の下端
  と更新
• 円の上端
  と更新
• に達したタイミング
  区間 の であれば'NO'

したがって で解けた。

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
constexpr ll INF = 1LL<<60;  
  
// 根が1  
template<typename Monoid>  
struct segtree {  
    using T = typename Monoid::T;  
    int n;  
    vector<T> dat;  
  
    segtree(int n_) {  
        n = 1;  
        while(n < n_) n <<= 1;  
        dat.assign(n*2, Monoid::id());  
    }  
    void build(vector<T> v) {  
        REP(i, v.size()) dat[i+n] = v[i];  
        for(int i=n-1; i>0; --i) dat[i] = Monoid::op(dat[i*2], dat[i*2+1]);  
    }  
  
    T query(int a, int b) {  
        if(a >= b) return Monoid::id();  
        T l = Monoid::id(), r = Monoid::id();  
        for(a+=n, b+=n; a<b; a>>=1, b>>=1) {  
            if(a&1) l = Monoid::op(l, dat[a++]);  
            if(b&1) r = Monoid::op(dat[--b], r);  
        }  
        return Monoid::op(l, r);  
    }  
    void update(int i, T v) {  
        i += n;  
        dat[i] = v;  
        while(i >>= 1) {  
            dat[i] = Monoid::op(dat[i*2], dat[i*2+1]);  
        }  
    }  
  
    friend ostream &operator <<(ostream& out,const segtree<Monoid>& seg){  
        out << "---------------------" << endl;  
        int cnt = 1;  
        for(int i=1; i<=seg.n; i*=2) {  
            REP(j, i) {  
                out << seg.dat[cnt] << " ";  
                cnt++;  
            }  
            out << endl;  
        }  
        out << "---------------------" << endl;  
        return out;  
    }  
};  
  
template<typename Tp>  
struct max_monoid {  
    using T = Tp;  
    static constexpr Tp id() { return -INF; }  
    static Tp op(const Tp &a, const Tp &b) { return max(a, b); }  
};  
  
int main() {  
    ll n, q;  
    cin >> n >> q;  
    vector<PII> ord(q+2*n);  
    vector<ll> cx(n), cy(n), r(n);  
    REP(i, n) {  
        cin >> cx[i] >> cy[i] >> r[i];  
        ord[2*i] = {i, 0};  
        ord[2*i+1] = {i, 2};  
    }  
    vector<ll> px(q), py(q), qx(q), qy(q), ymin(q), ymax(q);  
    REP(i, q) {  
        cin >> px[i] >> py[i] >> qx[i] >> qy[i] >> ymin[i] >> ymax[i];  
        if(px[i] > qx[i]) swap(px[i], qx[i]), swap(py[i], qy[i]);  
        ord[2*n + i] = {i, 1};  
    }  
    sort(ALL(ord), [&](PII a, PII b){  
        ll vl, vr;  
        if(a.second == 1) vl = ymin[a.first];  
        else if(a.second == 0) vl = cy[a.first] - r[a.first];  
        else if(a.second == 2) vl = cy[a.first] + r[a.first];  
        if(b.second == 1) vr = ymin[b.first];  
        else if(b.second == 0) vr = cy[b.first] - r[b.first];  
        else if(b.second == 2) vr = cy[b.first] + r[b.first];  
        return PII(vl, a.second) < PII(vr, b.second);  
    });  
  
    vector<ll> vs(2*q+n);  
    REP(i, q) vs[2*i] = px[i], vs[2*i+1] = qx[i];  
    REP(i, n) vs[2*q+i] = cx[i];  
    sort(ALL(vs));  
    vs.erase(unique(ALL(vs)), vs.end());  
    REP(i, q) {  
        px[i] = lower_bound(ALL(vs), px[i]) - vs.begin();  
        qx[i] = lower_bound(ALL(vs), qx[i]) - vs.begin();   
    }  
    REP(i, n) cx[i] = lower_bound(ALL(vs), cx[i]) - vs.begin();  
  
    vector<bool> ans(q, true);  
    segtree<max_monoid<ll>> seg(vs.size());  
    seg.build(vector<ll>(vs.size(), -INF));  
    for(auto [i, type]: ord) {  
        if(type == 1) {  
            if(ymax[i] <= seg.query(px[i], qx[i]+1)) ans[i] = false;  
        } else if(type == 0) {  
            seg.update(cx[i], cy[i]+r[i]);  
        } else if(type == 2) {  
            seg.update(cx[i], -INF);  
        }  
    }  
  
    REP(i, q) cout << (ans[i] ? "YES" : "NO") << "\n";  
  
    return 0;  
}