結果

問題 No.3801 Split Pairs
コンテスト
ユーザー 👑 qand
提出日時 2026-11-10 06:51:52
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 99 ms / 2,000 ms
+ 253µs
コード長 10,417 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,217 ms
コンパイル使用メモリ 346,740 KB
実行使用メモリ 16,128 KB
最終ジャッジ日時 2026-11-13 22:06:30
合計ジャッジ時間 6,248 ms
ジャッジサーバーID
(参考情報)
judge3_0 / judge2_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#line 1 "a.cpp"
// https://qandori.github.io/cp-library/
// #include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using std::cin, std::cout, std::cerr;
#define vec vector
typedef long double ld;
#if LONG_MAX == 2147483647L
#undef long
#define long long long
#endif
#define uint unsigned int
#define ulong unsigned long
#define overload3(a, b, c, name, ...) name
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define rep2(i, n) rep3(i, 0, n)
#define rep1(n) rep2(__i__, n)
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define per2(i, n) per3(i, 0, n)
#define per1(n) per2(__i__, n)
#define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)
#define CP_ALL_SELECT(first, ...) first
#define CP_ALL_RANGE(a) std::begin(a), std::end(a)
#define all(...) CP_ALL_SELECT(__VA_OPT__(CP_ALL_RANGE, ) all)(__VA_ARGS__)
#define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end()), a.shrink_to_fit()
#define sz(a) static_cast<int>(a.size())
#ifndef DEBUG
#define cerr \
	if (false) cerr
#undef endl
#define endl '\n'
#endif
inline auto operator^=(vector<bool>::reference a, bool b) noexcept {
	if (b) a.flip();
	return a;
}
inline auto operator&=(vector<bool>::reference a, bool b) noexcept {
	if (!b) a = false;
	return a;
}
inline auto operator|=(vector<bool>::reference a, bool b) noexcept {
	if (b) a = true;
	return a;
}
inline ostream &operator<<(ostream &os, __int128_t value) {
	ostream::sentry s(os);
	if (s) {
		__uint128_t tmp = value;
		if (value < 0) tmp = -tmp;
		char buffer[128];
		char *d = std::end(buffer);
		do {
			--d;
			*d = "0123456789"[tmp % 10];
			tmp /= 10;
		} while (tmp != 0);
		if (value < 0) --d, *d = '-';
		const int len = std::end(buffer) - d;
		if (os.rdbuf()->sputn(d, len) != len) os.setstate(std::ios_base::badbit);
	}
	return os;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> a) {
	return os << a.first << ' ' << a.second;
};
template <typename T>
ostream &operator<<(ostream &os, vector<T> a) {
	const int n = a.size();
	rep(i, n) {
		os << a[i];
		if (i + 1 != n) os << " ";
	}
	return os;
}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &a) {
	return is >> a.first >> a.second;
}
template <typename T, size_t n>
ostream &operator<<(ostream &os, array<T, n> a) {
	rep(i, n) {
		os << a[i];
		if (i + 1 != n) os << " ";
	}
	return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &a) {
	for (T &i : a) is >> i;
	return is;
}
template <typename T, typename S>
bool chmin(T &x, S y) {
	if ((T)y < x) {
		x = (T)y;
		return true;
	}
	return false;
}
template <typename T, typename S>
bool chmax(T &x, S y) {
	if (x < (T)y) {
		x = (T)y;
		return true;
	}
	return false;
}
template <typename T>
void operator++(vector<T> &a) {
	for (T &i : a) ++i;
}
template <typename T>
void operator--(vector<T> &a) {
	for (T &i : a) --i;
}
template <typename T>
void operator++(vector<T> &a, int) {
	for (T &i : a) i++;
}
template <typename T>
void operator--(vector<T> &a, int) {
	for (T &i : a) i--;
}
void init(), solve();
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	cerr << fixed << setprecision(20);
	init();
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
// #define COMB_MAX 1e6
// #include "lib/math/comb.hpp"
// #include "lib/fps/fps.hpp"
// #include "lib/math/mint.hpp"
void init() {}
#line 1 "lib/data_structure/interval_set.hpp"



#line 8 "lib/data_structure/interval_set.hpp"
#include <initializer_list>
#line 12 "lib/data_structure/interval_set.hpp"
#include <optional>
#include <type_traits>
#line 16 "lib/data_structure/interval_set.hpp"

template<class T = std::int64_t, class Size = std::conditional_t<
	std::is_integral_v<T> && sizeof(T) <= 8, std::uint64_t,
	std::conditional_t<std::is_same_v<T, __int128_t>, __uint128_t, T>>>
class IntervalSet {
	static_assert(std::numeric_limits<T>::is_integer && !std::is_same_v<T, bool>);
	static_assert(std::numeric_limits<Size>::is_integer && !std::is_same_v<Size, bool>);
	std::map<T, T> ranges;
	Size total = 0;
	static Size length(const T &l, const T &r) {
		return static_cast<Size>(r) - static_cast<Size>(l);
	}

public:
	using coordinate_type = T;
	using size_type = Size;
	using interval_type = std::pair<T, T>;
	using const_iterator = typename std::map<T, T>::const_iterator;
	using const_reverse_iterator = typename std::map<T, T>::const_reverse_iterator;

	IntervalSet() = default;
	explicit IntervalSet(std::vector<interval_type> intervals) { assign(std::move(intervals)); }
	IntervalSet(std::initializer_list<interval_type> intervals) { assign(intervals); }
	IntervalSet(const IntervalSet &) = default;
	IntervalSet(IntervalSet &&other) noexcept(std::is_nothrow_constructible_v<Size, int> && std::is_nothrow_swappable_v<Size>) { swap(other); }
	IntervalSet &operator=(IntervalSet other) noexcept(std::is_nothrow_swappable_v<Size>) { swap(other); return *this; }

	void assign(std::vector<interval_type> intervals) {
		std::sort(intervals.begin(), intervals.end());
		IntervalSet result;
		auto last = result.ranges.end();
		for (auto [l, r] : intervals) {
			assert(l <= r);
			if (l == r) continue;
			if (last != result.ranges.end() && l <= last->second) {
				if (last->second < r) {
					result.total += length(last->second, r);
					last->second = r;
				}
			} else {
				last = result.ranges.emplace_hint(result.ranges.end(), l, r);
				result.total += length(l, r);
			}
		}
		swap(result);
	}

	size_type insert(T l, T r) {
		assert(l <= r);
		if (l == r) return 0;
		auto it = ranges.upper_bound(l);
		if (it != ranges.begin() && std::prev(it)->second >= l) --it;
		if (it == ranges.end() || it->first > r) {
			ranges.emplace_hint(it, l, r);
			auto added = length(l, r);
			total += added;
			return added;
		}
		if (it->first <= l && r <= it->second) return 0;
		T left = (std::min)(l, it->first), right = (std::max)(r, it->second);
		auto removed = length(it->first, it->second);
		auto next_it = std::next(it);
		while (next_it != ranges.end() && next_it->first <= right) {
			right = (std::max)(right, next_it->second);
			removed += length(next_it->first, next_it->second);
			next_it = ranges.erase(next_it);
		}
		if (left == it->first) it->second = right;
		else {
			auto node = ranges.extract(it);
			node.key() = left;
			node.mapped() = right;
			ranges.insert(next_it, std::move(node));
		}
		size_type added = length(left, right) - removed;
		total += added;
		return added;
	}

	size_type insert(T x) {
		if constexpr (std::numeric_limits<T>::is_bounded) assert(x < (std::numeric_limits<T>::max)());
		return insert(x, static_cast<T>(x + 1));
	}

	size_type erase(T l, T r) {
		assert(l <= r);
		if (l == r) return 0;
		auto it = ranges.upper_bound(l);
		if (it != ranges.begin() && std::prev(it)->second > l) --it;
		size_type removed = 0;
		if (it != ranges.end() && it->first < l) {
			T right = it->second;
			if (r < right) {
				ranges.emplace_hint(std::next(it), r, right);
				it->second = l;
				removed = length(l, r);
				total -= removed;
				return removed;
			}
			removed = length(l, right);
			it->second = l;
			++it;
		}
		while (it != ranges.end() && it->first < r) {
			if (r < it->second) {
				removed += length(it->first, r);
				auto hint = std::next(it);
				auto node = ranges.extract(it);
				node.key() = r;
				ranges.insert(hint, std::move(node));
				break;
			}
			removed += length(it->first, it->second);
			it = ranges.erase(it);
		}
		total -= removed;
		return removed;
	}

	size_type erase(T x) {
		if constexpr (std::numeric_limits<T>::is_bounded)
			if (x == (std::numeric_limits<T>::max)()) return 0;
		return erase(x, static_cast<T>(x + 1));
	}

	const_iterator find(T x) const {
		auto it = ranges.upper_bound(x);
		if (it == ranges.begin()) return ranges.end();
		--it;
		return x < it->second ? it : ranges.end();
	}
	const_iterator lower_bound(T x) const {
		auto it = ranges.upper_bound(x);
		if (it != ranges.begin() && x < std::prev(it)->second) --it;
		return it;
	}
	bool contains(T x) const { return find(x) != end(); }
	bool contains(T l, T r) const {
		assert(l <= r);
		if (l == r) return true;
		auto it = find(l);
		return it != end() && r <= it->second;
	}
	bool intersects(T l, T r) const {
		assert(l <= r);
		if (l == r) return false;
		auto it = lower_bound(l);
		return it != end() && it->first < r;
	}
	size_type count(T l, T r) const {
		assert(l <= r);
		if (l == r) return 0;
		size_type result = 0;
		for (auto it = lower_bound(l); it != end() && it->first < r; ++it)
			result += length((std::max)(l, it->first), (std::min)(r, it->second));
		return result;
	}
	std::optional<T> next(T x) const {
		auto it = lower_bound(x);
		if (it == end()) return std::nullopt;
		return (std::max)(x, it->first);
	}
	std::optional<T> prev(T x) const {
		auto it = ranges.upper_bound(x);
		if (it == ranges.begin()) return std::nullopt;
		--it;
		return (std::min)(x, static_cast<T>(it->second - 1));
	}
	T mex(T x = 0) const {
		auto it = find(x);
		return it == end() ? x : it->second;
	}
	std::optional<T> min() const {
		if (empty()) return std::nullopt;
		return begin()->first;
	}
	std::optional<T> max() const {
		if (empty()) return std::nullopt;
		return static_cast<T>(ranges.rbegin()->second - 1);
	}
	size_type size() const { return total; }
	std::size_t interval_count() const { return ranges.size(); }
	bool empty() const { return ranges.empty(); }
	const_iterator begin() const { return ranges.begin(); }
	const_iterator end() const { return ranges.end(); }
	const_reverse_iterator rbegin() const { return ranges.rbegin(); }
	const_reverse_iterator rend() const { return ranges.rend(); }
	void clear() { ranges.clear(); total = 0; }
	void swap(IntervalSet &other) noexcept(std::is_nothrow_swappable_v<Size>) {
		ranges.swap(other.ranges);
		using std::swap;
		swap(total, other.total);
	}
	friend void swap(IntervalSet &a, IntervalSet &b) noexcept(noexcept(a.swap(b))) { a.swap(b); }
};


#line 143 "a.cpp"
void solve() {
	int n;
	cin >> n;
	IntervalSet<long> s;
	long ans = 0;
	rep(i, n) {
		long x;
		cin >> x;
		if (!s.contains(x)) {
			s.insert(x);
			continue;
		}
		auto [l, r] = *s.lower_bound(x);
		r--;
		const long ll = x - l, rr = r - x;
		ans += (ll + 1) * (rr + 1);
		s.insert(l - 1), s.insert(r + 1);
		s.erase(x + rr - ll);
	}
	cout << ans << endl;
}
0