test/datastructure/interval_set/aoj_2880.test.cpp

• View this file on GitHub
• Last update: 2025-12-10 01:15:18+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2880

Depends on

• Interval Set (src/datastructure/interval_set.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2880

#include "src/datastructure/interval_set.hpp"

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

int main() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<tuple<int, int, int>> dab(m);
	for (auto &[d, a, b] : dab) cin >> d >> a >> b;
	sort(dab.begin(), dab.end());
	vector<tuple<int, int, int, int>> esti(q);
	for (int i = 0; i < q; ++i) {
		auto &[e, s, t, index] = esti[i];
		cin >> e >> s >> t;
		index = i;
	}
	sort(esti.begin(), esti.end());

	vector<bool> ans(q);
	IntervalSet<int> is(false);
	auto it = dab.begin();
	for (auto const &[e, s, t, i] : esti) {
		while (it != dab.end() && get<0>(*it) < e) {
			auto [_, a, b] = *it;
			is.insert(a, b);
			++it;
		}

		ans[i] = s >= t || is.covered(s, t);
	}

	for (auto const &f : ans) cout << (f ? "Yes" : "No") << endl;

	return 0;
}

#line 1 "test/datastructure/interval_set/aoj_2880.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2880

#line 1 "src/datastructure/interval_set.hpp"



#include <cassert>
#include <cstdint>
#include <iterator>
#include <limits>
#include <numeric>
#include <set>
#include <utility>

template<typename T>
class IntervalSet {
private:
	static constexpr T MIN = std::numeric_limits<T>::min();
	static constexpr T MAX = std::numeric_limits<T>::max();

	std::set<std::pair<T, T>> intervals;
	T adjacent_offset;

public:
	using iterator = typename std::set<std::pair<T, T>>::iterator;

	IntervalSet(bool enable_merge_adjacent = true) :
		intervals{
			{MIN, MIN},
            {MAX, MAX}
    },
		adjacent_offset(enable_merge_adjacent ? 1 : 0) {}

	iterator begin() const { return std::next(intervals.begin()); }

	iterator end() const { return std::prev(intervals.end()); }

	[[nodiscard]] iterator find(T x) const {
		auto it = std::prev(intervals.upper_bound({x, MAX}));
		return it->first <= x && x <= it->second ? it : end();
	}

	std::uint64_t insert(T x) { return insert(x, x); }

	std::uint64_t insert(T l, T r) { // [l, r]
		assert(l <= r);

		auto left_it = intervals.upper_bound({l, MAX});
		auto right_it = intervals.upper_bound({r + adjacent_offset, MAX});
		if (left_it != intervals.begin() &&
			l - adjacent_offset <= std::prev(left_it)->second)
			--left_it;

		std::uint64_t count =
			r - l + 1 -
			std::accumulate(left_it, right_it, std::uint64_t{0}, [](auto acc, auto x) {
				return acc + x.second - x.first + 1;
			});

		T ll = left_it->first;
		T rr = std::prev(right_it)->second;
		intervals.erase(left_it, right_it);
		if (ll < l) {
			count += l - ll;
			l = ll;
		}
		if (r < rr) {
			count += rr - r;
			r = rr;
		}

		intervals.emplace(l, r);
		return count;
	}

	std::uint64_t erase(T x) { return erase(x, x); }

	std::uint64_t erase(T l, T r) { // [l, r]
		assert(l <= r);

		auto left_it = intervals.upper_bound({l, MAX});
		auto right_it = intervals.upper_bound({r, MAX});
		if (left_it != intervals.begin() && l <= std::prev(left_it)->second) --left_it;
		if (left_it == right_it) return 0;

		std::uint64_t count =
			std::accumulate(left_it, right_it, std::uint64_t{0}, [](auto acc, auto x) {
				return acc + x.second - x.first + 1;
			});

		T ll = left_it->first;
		T rr = std::prev(right_it)->second;
		intervals.erase(left_it, right_it);
		if (ll < l) {
			count -= l - ll;
			intervals.emplace(ll, l - 1);
		}
		if (r < rr) {
			count -= rr - r;
			intervals.emplace(r + 1, rr);
		}

		return count;
	}

	[[nodiscard]] bool covered(T x) const { return covered(x, x); }

	[[nodiscard]] bool covered(T l, T r) const { // [l, r]
		assert(l <= r);
		auto it = std::prev(intervals.upper_bound({r, MAX}));
		return it->first <= l && r <= it->second;
	}

	[[nodiscard]] T mex(T x = 0) const {
		auto it = find(x);
		return it == end() ? x : it->second + 1;
	}
};


#line 4 "test/datastructure/interval_set/aoj_2880.test.cpp"

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

int main() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<tuple<int, int, int>> dab(m);
	for (auto &[d, a, b] : dab) cin >> d >> a >> b;
	sort(dab.begin(), dab.end());
	vector<tuple<int, int, int, int>> esti(q);
	for (int i = 0; i < q; ++i) {
		auto &[e, s, t, index] = esti[i];
		cin >> e >> s >> t;
		index = i;
	}
	sort(esti.begin(), esti.end());

	vector<bool> ans(q);
	IntervalSet<int> is(false);
	auto it = dab.begin();
	for (auto const &[e, s, t, i] : esti) {
		while (it != dab.end() && get<0>(*it) < e) {
			auto [_, a, b] = *it;
			is.insert(a, b);
			++it;
		}

		ans[i] = s >= t || is.covered(s, t);
	}

	for (auto const &f : ans) cout << (f ? "Yes" : "No") << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	63 ms	19 MB
g++	00_sample_01.in	AC	13 ms	19 MB
g++	10_handmade_00.in	AC	13 ms	20 MB
g++	10_handmade_01.in	AC	13 ms	20 MB
g++	10_handmade_02.in	AC	12 ms	20 MB
g++	10_handmade_03.in	AC	12 ms	20 MB
g++	50_random_small_00.in	AC	13 ms	19 MB
g++	50_random_small_01.in	AC	13 ms	20 MB
g++	50_random_small_02.in	AC	13 ms	19 MB
g++	50_random_small_03.in	AC	12 ms	20 MB
g++	50_random_small_04.in	AC	13 ms	19 MB
g++	50_random_small_05.in	AC	13 ms	19 MB
g++	50_random_small_06.in	AC	12 ms	20 MB
g++	50_random_small_07.in	AC	12 ms	19 MB
g++	50_random_small_08.in	AC	12 ms	20 MB
g++	50_random_small_09.in	AC	11 ms	20 MB
g++	51_random_large_00.in	AC	248 ms	24 MB
g++	51_random_large_01.in	AC	205 ms	23 MB
g++	51_random_large_02.in	AC	205 ms	25 MB
g++	51_random_large_03.in	AC	302 ms	32 MB
g++	51_random_large_04.in	AC	240 ms	31 MB
g++	51_random_large_05.in	AC	351 ms	29 MB
g++	51_random_large_06.in	AC	197 ms	25 MB
g++	51_random_large_07.in	AC	196 ms	28 MB
g++	51_random_large_08.in	AC	247 ms	29 MB
g++	51_random_large_09.in	AC	215 ms	22 MB
g++	52_MIN_00.in	AC	13 ms	20 MB
g++	53_MAX_00.in	AC	425 ms	31 MB
g++	53_MAX_01.in	AC	405 ms	31 MB
g++	53_MAX_02.in	AC	404 ms	31 MB
g++	53_MAX_03.in	AC	411 ms	31 MB
g++	53_MAX_04.in	AC	413 ms	31 MB
g++	53_MAX_05.in	AC	412 ms	33 MB
g++	53_MAX_06.in	AC	407 ms	31 MB
g++	53_MAX_07.in	AC	413 ms	31 MB
g++	53_MAX_08.in	AC	407 ms	31 MB
g++	53_MAX_09.in	AC	410 ms	33 MB
g++	54_Nsmall_00.in	AC	257 ms	29 MB
g++	54_Nsmall_01.in	AC	210 ms	22 MB
g++	54_Nsmall_02.in	AC	288 ms	30 MB
g++	54_Nsmall_03.in	AC	121 ms	23 MB
g++	54_Nsmall_04.in	AC	278 ms	26 MB
g++	54_Nsmall_05.in	AC	59 ms	21 MB
g++	54_Nsmall_06.in	AC	121 ms	22 MB
g++	54_Nsmall_07.in	AC	169 ms	24 MB
g++	54_Nsmall_08.in	AC	263 ms	25 MB
g++	54_Nsmall_09.in	AC	240 ms	26 MB
g++	55_Msmall_00.in	AC	39 ms	20 MB
g++	55_Msmall_01.in	AC	147 ms	21 MB
g++	55_Msmall_02.in	AC	36 ms	20 MB
g++	55_Msmall_03.in	AC	81 ms	21 MB
g++	55_Msmall_04.in	AC	67 ms	20 MB
g++	55_Msmall_05.in	AC	99 ms	20 MB
g++	55_Msmall_06.in	AC	106 ms	21 MB
g++	55_Msmall_07.in	AC	73 ms	20 MB
g++	55_Msmall_08.in	AC	121 ms	21 MB
g++	55_Msmall_09.in	AC	99 ms	21 MB
g++	56_DEsmall_00.in	AC	233 ms	24 MB
g++	56_DEsmall_01.in	AC	357 ms	32 MB
g++	56_DEsmall_02.in	AC	278 ms	29 MB
g++	56_DEsmall_03.in	AC	210 ms	27 MB
g++	56_DEsmall_04.in	AC	168 ms	22 MB
g++	56_DEsmall_05.in	AC	170 ms	27 MB
g++	56_DEsmall_06.in	AC	202 ms	28 MB
g++	56_DEsmall_07.in	AC	198 ms	26 MB
g++	56_DEsmall_08.in	AC	61 ms	21 MB
g++	56_DEsmall_09.in	AC	149 ms	26 MB
g++	60_challenge_00.in	AC	377 ms	31 MB
g++	60_challenge_01.in	AC	351 ms	26 MB
clang++	00_sample_00.in	AC	12 ms	14 MB
clang++	00_sample_01.in	AC	13 ms	18 MB
clang++	10_handmade_00.in	AC	12 ms	14 MB
clang++	10_handmade_01.in	AC	13 ms	16 MB
clang++	10_handmade_02.in	AC	13 ms	16 MB
clang++	10_handmade_03.in	AC	11 ms	16 MB
clang++	50_random_small_00.in	AC	11 ms	16 MB
clang++	50_random_small_01.in	AC	14 ms	16 MB
clang++	50_random_small_02.in	AC	13 ms	14 MB
clang++	50_random_small_03.in	AC	15 ms	18 MB
clang++	50_random_small_04.in	AC	14 ms	14 MB
clang++	50_random_small_05.in	AC	15 ms	16 MB
clang++	50_random_small_06.in	AC	13 ms	16 MB
clang++	50_random_small_07.in	AC	11 ms	12 MB
clang++	50_random_small_08.in	AC	11 ms	16 MB
clang++	50_random_small_09.in	AC	11 ms	18 MB
clang++	51_random_large_00.in	AC	180 ms	20 MB
clang++	51_random_large_01.in	AC	144 ms	17 MB
clang++	51_random_large_02.in	AC	148 ms	20 MB
clang++	51_random_large_03.in	AC	208 ms	24 MB
clang++	51_random_large_04.in	AC	161 ms	23 MB
clang++	51_random_large_05.in	AC	242 ms	27 MB
clang++	51_random_large_06.in	AC	139 ms	19 MB
clang++	51_random_large_07.in	AC	128 ms	24 MB
clang++	51_random_large_08.in	AC	164 ms	26 MB
clang++	51_random_large_09.in	AC	163 ms	20 MB
clang++	52_MIN_00.in	AC	13 ms	18 MB
clang++	53_MAX_00.in	AC	281 ms	30 MB
clang++	53_MAX_01.in	AC	293 ms	23 MB
clang++	53_MAX_02.in	AC	284 ms	23 MB
clang++	53_MAX_03.in	AC	287 ms	25 MB
clang++	53_MAX_04.in	AC	289 ms	25 MB
clang++	53_MAX_05.in	AC	290 ms	25 MB
clang++	53_MAX_06.in	AC	283 ms	23 MB
clang++	53_MAX_07.in	AC	282 ms	26 MB
clang++	53_MAX_08.in	AC	285 ms	23 MB
clang++	53_MAX_09.in	AC	281 ms	28 MB
clang++	54_Nsmall_00.in	AC	163 ms	25 MB
clang++	54_Nsmall_01.in	AC	148 ms	18 MB
clang++	54_Nsmall_02.in	AC	191 ms	24 MB
clang++	54_Nsmall_03.in	AC	94 ms	19 MB
clang++	54_Nsmall_04.in	AC	196 ms	23 MB
clang++	54_Nsmall_05.in	AC	43 ms	17 MB
clang++	54_Nsmall_06.in	AC	88 ms	18 MB
clang++	54_Nsmall_07.in	AC	124 ms	18 MB
clang++	54_Nsmall_08.in	AC	183 ms	18 MB
clang++	54_Nsmall_09.in	AC	162 ms	23 MB
clang++	55_Msmall_00.in	AC	33 ms	16 MB
clang++	55_Msmall_01.in	AC	104 ms	15 MB
clang++	55_Msmall_02.in	AC	32 ms	16 MB
clang++	55_Msmall_03.in	AC	70 ms	14 MB
clang++	55_Msmall_04.in	AC	57 ms	16 MB
clang++	55_Msmall_05.in	AC	81 ms	17 MB
clang++	55_Msmall_06.in	AC	85 ms	17 MB
clang++	55_Msmall_07.in	AC	61 ms	14 MB
clang++	55_Msmall_08.in	AC	100 ms	17 MB
clang++	55_Msmall_09.in	AC	74 ms	18 MB
clang++	56_DEsmall_00.in	AC	158 ms	22 MB
clang++	56_DEsmall_01.in	AC	230 ms	26 MB
clang++	56_DEsmall_02.in	AC	180 ms	22 MB
clang++	56_DEsmall_03.in	AC	133 ms	22 MB
clang++	56_DEsmall_04.in	AC	116 ms	16 MB
clang++	56_DEsmall_05.in	AC	105 ms	21 MB
clang++	56_DEsmall_06.in	AC	127 ms	25 MB
clang++	56_DEsmall_07.in	AC	131 ms	21 MB
clang++	56_DEsmall_08.in	AC	45 ms	15 MB
clang++	56_DEsmall_09.in	AC	91 ms	22 MB
clang++	60_challenge_00.in	AC	255 ms	27 MB
clang++	60_challenge_01.in	AC	252 ms	24 MB

Back to top page