test/datastructure/interval_set/yuki_3017.test.cpp

• View this file on GitHub
• Last update: 2025-12-10 01:15:18+09:00
• Problem: https://yukicoder.me/problems/no/3017

Depends on

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

Code

// verification-helper: PROBLEM https://yukicoder.me/problems/no/3017

#include "src/datastructure/interval_set.hpp"

#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;

	int ans = 0;
	IntervalSet<int> is;
	for (int i = 0; i < n; ++i) {
		int h;
		cin >> h;

		if (i % 2 == 0) ans += is.insert(1, h);
		else ans -= is.erase(1, h);

		cout << ans << endl;
	}

	return 0;
}

#line 1 "test/datastructure/interval_set/yuki_3017.test.cpp"
// verification-helper: PROBLEM https://yukicoder.me/problems/no/3017

#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/yuki_3017.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;

	int ans = 0;
	IntervalSet<int> is;
	for (int i = 0; i < n; ++i) {
		int h;
		cin >> h;

		if (i % 2 == 0) ans += is.insert(1, h);
		else ans -= is.erase(1, h);

		cout << ans << endl;
	}

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	01_sample_01.txt	AC	11 ms	18 MB
g++	02_random_01.txt	AC	477 ms	32 MB
g++	02_random_02.txt	AC	455 ms	32 MB
g++	02_random_03.txt	AC	456 ms	32 MB
g++	02_random_04.txt	AC	452 ms	32 MB
g++	02_random_05.txt	AC	459 ms	32 MB
g++	02_random_06.txt	AC	486 ms	32 MB
g++	02_random_07.txt	AC	512 ms	32 MB
g++	02_random_08.txt	AC	483 ms	32 MB
g++	02_random_09.txt	AC	461 ms	32 MB
g++	02_random_10.txt	AC	454 ms	32 MB
g++	02_random_11.txt	AC	462 ms	32 MB
g++	02_random_12.txt	AC	501 ms	32 MB
g++	02_random_13.txt	AC	467 ms	32 MB
g++	02_random_14.txt	AC	596 ms	32 MB
g++	02_random_15.txt	AC	482 ms	32 MB
g++	02_random_16.txt	AC	465 ms	32 MB
g++	02_random_17.txt	AC	488 ms	32 MB
g++	02_random_18.txt	AC	488 ms	32 MB
g++	02_random_19.txt	AC	499 ms	32 MB
g++	02_random_20.txt	AC	500 ms	32 MB
g++	02_random_21.txt	AC	494 ms	32 MB
g++	02_random_22.txt	AC	459 ms	32 MB
g++	02_random_23.txt	AC	466 ms	32 MB
g++	02_random_24.txt	AC	455 ms	32 MB
g++	02_random_25.txt	AC	483 ms	32 MB
g++	02_random_26.txt	AC	503 ms	32 MB
g++	02_random_27.txt	AC	458 ms	32 MB
g++	02_random_28.txt	AC	516 ms	32 MB
g++	02_random_29.txt	AC	460 ms	32 MB
g++	02_random_30.txt	AC	510 ms	32 MB
g++	02_random_31.txt	AC	78 ms	21 MB
g++	02_random_32.txt	AC	321 ms	28 MB
g++	02_random_33.txt	AC	505 ms	31 MB
g++	02_random_34.txt	AC	337 ms	27 MB
g++	02_random_35.txt	AC	311 ms	27 MB
g++	02_random_36.txt	AC	75 ms	21 MB
g++	02_random_37.txt	AC	304 ms	26 MB
g++	02_random_38.txt	AC	408 ms	29 MB
g++	02_random_39.txt	AC	55 ms	20 MB
g++	02_random_40.txt	AC	449 ms	31 MB
g++	03_hand_1.txt	AC	12 ms	16 MB
g++	03_hand_10.txt	AC	404 ms	27 MB
g++	03_hand_11.txt	AC	588 ms	33 MB
g++	03_hand_12.txt	AC	435 ms	27 MB
g++	03_hand_13.txt	AC	642 ms	33 MB
g++	03_hand_14.txt	AC	422 ms	27 MB
g++	03_hand_15.txt	AC	571 ms	33 MB
g++	03_hand_2.txt	AC	12 ms	16 MB
g++	03_hand_3.txt	AC	12 ms	18 MB
g++	03_hand_4.txt	AC	400 ms	27 MB
g++	03_hand_5.txt	AC	414 ms	27 MB
g++	03_hand_6.txt	AC	422 ms	27 MB
g++	03_hand_7.txt	AC	547 ms	32 MB
g++	03_hand_8.txt	AC	447 ms	27 MB
g++	03_hand_9.txt	AC	543 ms	31 MB
clang++	01_sample_01.txt	AC	11 ms	18 MB
clang++	02_random_01.txt	AC	372 ms	25 MB
clang++	02_random_02.txt	AC	363 ms	25 MB
clang++	02_random_03.txt	AC	360 ms	25 MB
clang++	02_random_04.txt	AC	394 ms	27 MB
clang++	02_random_05.txt	AC	391 ms	27 MB
clang++	02_random_06.txt	AC	361 ms	29 MB
clang++	02_random_07.txt	AC	396 ms	27 MB
clang++	02_random_08.txt	AC	366 ms	29 MB
clang++	02_random_09.txt	AC	373 ms	31 MB
clang++	02_random_10.txt	AC	382 ms	27 MB
clang++	02_random_11.txt	AC	365 ms	27 MB
clang++	02_random_12.txt	AC	354 ms	27 MB
clang++	02_random_13.txt	AC	384 ms	25 MB
clang++	02_random_14.txt	AC	362 ms	27 MB
clang++	02_random_15.txt	AC	417 ms	31 MB
clang++	02_random_16.txt	AC	362 ms	31 MB
clang++	02_random_17.txt	AC	432 ms	27 MB
clang++	02_random_18.txt	AC	366 ms	25 MB
clang++	02_random_19.txt	AC	361 ms	27 MB
clang++	02_random_20.txt	AC	434 ms	29 MB
clang++	02_random_21.txt	AC	403 ms	27 MB
clang++	02_random_22.txt	AC	390 ms	27 MB
clang++	02_random_23.txt	AC	393 ms	29 MB
clang++	02_random_24.txt	AC	364 ms	31 MB
clang++	02_random_25.txt	AC	430 ms	29 MB
clang++	02_random_26.txt	AC	376 ms	27 MB
clang++	02_random_27.txt	AC	363 ms	29 MB
clang++	02_random_28.txt	AC	407 ms	27 MB
clang++	02_random_29.txt	AC	362 ms	29 MB
clang++	02_random_30.txt	AC	369 ms	29 MB
clang++	02_random_31.txt	AC	74 ms	15 MB
clang++	02_random_32.txt	AC	296 ms	23 MB
clang++	02_random_33.txt	AC	357 ms	26 MB
clang++	02_random_34.txt	AC	281 ms	22 MB
clang++	02_random_35.txt	AC	236 ms	22 MB
clang++	02_random_36.txt	AC	60 ms	18 MB
clang++	02_random_37.txt	AC	197 ms	21 MB
clang++	02_random_38.txt	AC	286 ms	24 MB
clang++	02_random_39.txt	AC	44 ms	17 MB
clang++	02_random_40.txt	AC	332 ms	28 MB
clang++	03_hand_1.txt	AC	11 ms	12 MB
clang++	03_hand_10.txt	AC	345 ms	22 MB
clang++	03_hand_11.txt	AC	426 ms	29 MB
clang++	03_hand_12.txt	AC	342 ms	22 MB
clang++	03_hand_13.txt	AC	514 ms	27 MB
clang++	03_hand_14.txt	AC	339 ms	22 MB
clang++	03_hand_15.txt	AC	428 ms	32 MB
clang++	03_hand_2.txt	AC	11 ms	15 MB
clang++	03_hand_3.txt	AC	11 ms	18 MB
clang++	03_hand_4.txt	AC	304 ms	24 MB
clang++	03_hand_5.txt	AC	334 ms	22 MB
clang++	03_hand_6.txt	AC	324 ms	21 MB
clang++	03_hand_7.txt	AC	436 ms	29 MB
clang++	03_hand_8.txt	AC	336 ms	23 MB
clang++	03_hand_9.txt	AC	435 ms	24 MB

Back to top page