結果
| 問題 | No.3801 Split Pairs |
| コンテスト | |
| ユーザー |
👑 |
| 提出日時 | 2026-11-10 06:51:52 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 99 ms / 2,000 ms |
| + 253µs | |
| コード長 | 10,417 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
#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;
}