verify/Datastructure_rangeset.test.cpp

View this file on GitHub
Last update: 2025-04-03 05:20:23+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/2880

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2880"
#include "../Utility/template.hpp"
#include "../Datastructure/rangeset.hpp"

int main() {
    ll n, m, q;
    cin >> n >> m >> q;
    using P = array<ll, 4>;

    rangeset<ll, false> rs;
    vec<P> es;
    rep(i, 0, m) {
        ll d, a, b;
        cin >> d >> a >> b;
        a--;
        es.push_back(P{d, 1, a, b});
    }

    rep(i, 0, q) {
        ll e, s, t;
        cin >> e >> s >> t;
        s--;
        es.push_back(P{e, -i, s, t});
    }

    sort(all(es));
    vec<ll> ans(q);
    for (auto [d, type, a, b] : es) {
        if (type != 1) {
            ll id = -type;
            if(a >= b - 1) ans[id] = true;
            else ans[id] = rs.same(a, b - 1);
        } else {
            rs.insert(a, b);
        }
    }

    rep(i, 0, q) {
        if (ans[i]) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

#line 1 "verify/Datastructure_rangeset.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2880"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/rangeset.hpp"
template <typename T, bool merge_adju> struct rangeset : public std::map<T, T> {
    rangeset() {}
    auto get(T p) const {
        auto it = (*this).upper_bound(p);
        if (it == (*this).begin() || (--it)->second <= p) return (*this).end();
        return it;
    }

    //[l, r)
    pair<T, T> insert(T l, T r) {
        if (l == r) return make_pair(l, r);
        assert(l <= r);
        auto itl = (*this).upper_bound(l),
             itr = (*this).lower_bound(r + merge_adju);
        if (itl != (*this).begin() && (--itl)->second + merge_adju <= l) {
            ++itl;
        }

        if (itl != itr) {
            if (itl->first < l) l = itl->first;
            if (prev(itr)->second > r) r = prev(itr)->second;
            map<T, T>::erase(itl, itr);
        }
        (*this)[l] = r;
        return make_pair(l, r);
    }

    pair<T, T> insert(T p) { return insert(p, p + 1); }

    //[l, r)
    void erase(T l, T r) {
        if (l == r) return;
        assert(l <= r);
        auto itl = (*this).upper_bound(l), itr = (*this).lower_bound(r);
        if (itl != (*this).begin() && (--itl)->second <= l) {
            ++itl;
        }
        if (itl == itr) return;
        T tl = l, tr = r;
        if (itl->first < l) tl = itl->first;
        if (prev(itr)->second > r) tr = prev(itr)->second;
        map<T, T>::erase(itl, itr);
        if (tl < l) (*this)[tl] = l;
        if (tr > r) (*this)[r] = tr;
    }

    void erase(T p) { erase(p, p + 1); }

    // pを含む区間があるか
    bool contains(T p) const { return get(p) != (*this).end(); }

    //[l, r)のうち1要素でも含まれているか
    bool contains(T l, T r) const {
        auto itl = (*this).upper_bound(l), itr = (*this).lower_bound(r);
        if (itl != (*this).begin() && (--itl)->second <= l) {
            ++itl;
        }
        if (itl == itr)
            return false;
        else
            return true;
    }

    // aとbを共に含む区間があるか
    bool same(T a, T b) const {
        if (a > b) swap(a, b);

        auto it = get(a);
        if (it == (*this).end()) return false;
        return b < it->second;
    }

    T mex(T x = 0) const {
        auto it = get(x);
        if (it == (*this).end())
            return x;
        else
            return it->second;
    }

    template <typename TYPE, bool ME>
    friend ostream &operator<<(ostream &os, rangeset<TYPE, ME> const &rhs) {
        for (auto [l, r] : rhs) os << "[" << l << ", " << r << ")";
        return os;
    }
};
#line 4 "verify/Datastructure_rangeset.test.cpp"

int main() {
    ll n, m, q;
    cin >> n >> m >> q;
    using P = array<ll, 4>;

    rangeset<ll, false> rs;
    vec<P> es;
    rep(i, 0, m) {
        ll d, a, b;
        cin >> d >> a >> b;
        a--;
        es.push_back(P{d, 1, a, b});
    }

    rep(i, 0, q) {
        ll e, s, t;
        cin >> e >> s >> t;
        s--;
        es.push_back(P{e, -i, s, t});
    }

    sort(all(es));
    vec<ll> ans(q);
    for (auto [d, type, a, b] : es) {
        if (type != 1) {
            ll id = -type;
            if(a >= b - 1) ans[id] = true;
            else ans[id] = rs.same(a, b - 1);
        } else {
            rs.insert(a, b);
        }
    }

    rep(i, 0, q) {
        if (ans[i]) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}