結果

問題 No.3017 交互浴
コンテスト
ユーザー nabefuta220
提出日時 2025-12-31 00:11:14
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 143 ms / 2,000 ms
コード長 12,515 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,135 ms
コンパイル使用メモリ 285,988 KB
実行使用メモリ 7,940 KB
最終ジャッジ日時 2025-12-31 00:11:32
合計ジャッジ時間 17,759 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <limits>

#ifndef __DEBUG_HPP__

#define __DEBUG_HPP__
#ifndef __TOOLS_HPP__
#define __TOOLS_HPP__
#include <bits/stdc++.h>
using namespace std;

//
#ifndef __IO_HPP__
#define __IO_HPP__
// 入出力関連
#ifndef __MACRO_HPP__
#define __MACRO_HPP__
using ll = long long;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (int)(n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define repi(i, x) \
	for (auto i = (x).begin(), i##_fin = (x).end(); i != i##_fin; ++i)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
using Vi  = vector<int>;
using VVi = vector<Vi>;
using Pi  = pair<int, int>;
using VPi = vector<Pi>;
using V   = vector<long long>;
using VV  = vector<V>;
using P   = pair<long long, long long>;
using VP  = vector<P>;
using Vb  = vector<bool>;

// decler and input
#define ini(...)     \
	int __VA_ARGS__; \
	input(__VA_ARGS__);
#define inl(...)           \
	long long __VA_ARGS__; \
	input(__VA_ARGS__);
#define ind(...)        \
	double __VA_ARGS__; \
	input(__VA_ARGS__);
#define ins(...)        \
	string __VA_ARGS__; \
	input(__VA_ARGS__);
#define inv1(s) rep(i, (s).size()) input(s[i]);
#define inv2(s, t) rep(i, (s).size()) input(s[i], t[i]);
#define inv3(s, t, u) rep(i, (s).size()) input(s[i], t[i], u[i]);
#define inv4(s, t, u, v) rep(i, (s).size()) input(s[i], t[i], u[i], v[i]);
#endif  //__MACRO_HPP__
// pair
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os << "(" << p.first << " " << p.second << ")";
	return os;
}

template <class T, class U>
istream& operator>>(istream& is, pair<T, U>& p) {
	is >> p.first >> p.second;
	return is;
}
// vector
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	rep(i, v.size()) {
		if (i) os << " ";
		os << v[i];
	}
	return os;
}
template <class T>
istream& operator>>(istream& is, vector<T>& v) {
	rep(i, v.size()) { is >> v[i]; }
	return is;
}

// multi-variable
void input() {}
template <typename T, class... U>
void input(T& t, U&... u) {
	cin >> t;
	input(u...);
}

void output() { cout << '\n'; }
template <typename T, class... U, char seperate = ' '>
void output(const T& t, const U&... u) {
	cout << t;
	if (sizeof...(u)) cout << seperate;
	output(u...);
}

// setup
struct IoSetuper {
	IoSetuper() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(15);
		cerr << fixed << setprecision(7);
	}
} iosetuper;
#endif  //__IO_HPP__
#ifndef __CONSTANCE_HPP__
#define __CONSTANCE_HPP__
template <typename T>
static constexpr T safe_max() noexcept {
	return numeric_limits<T>::max() / (T)2 - (T)1;
};

constexpr long long INFLL = safe_max<long long>();
constexpr int INF         = safe_max<int>();
const double PI           = acos(-1);

#endif  // __CONSTANCE_HPP__
#ifndef __TRANSIENT_HPP__
#define __TRANSIENT_HPP__

template <class T>
inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return 1;
	}
	return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return 1;
	}
	return 0;
}

#endif  // __TRANSIENT_HPP__
/*
#ifdef LOCAL
#define dbg(x) cerr << #x << ": " << (x) << '\n'
#define say(x) cerr << (x) << '\n'
#else
#define dbg(x)
#define say(x)
#endif
*/
string solve(bool a) { return ((a) ? "Yes" : "No"); }

#endif  // __TOOLS_HPP__
//
template <typename U, typename = void>
struct is_specialize : false_type {};
template <typename U>
struct is_specialize<
    U, typename conditional<false, typename U::iterator, void>::type>
    : true_type {};
template <typename U>
struct is_specialize<
    U, typename conditional<false, decltype(U::first), void>::type>
    : true_type {};
template <typename U>
struct is_specialize<U, enable_if_t<is_integral<U>::value, void>> : true_type {
};

#ifdef LOCAL

void dump(const int& t) { cerr << t; }
void dump(const char& t) { cerr << t; }

void dump(const string& t) { cerr << t; }

void dump(const bool& t) { cerr << (t ? "true" : "false"); }

template <typename U,
          enable_if_t<!is_specialize<U>::value, nullptr_t> = nullptr>
void dump(const U& t) {
	cerr << t;
}

template <typename T>
void dump(const T& t, enable_if_t<is_integral<T>::value>* = nullptr) {
	string res;
	if (t == INF) res = "inf";
	if constexpr (is_signed<T>::value) {
		if (t == -INF) res = "-inf";
	}
	if constexpr (sizeof(T) == 8) {
		if (t == INFLL) res = "inf";
		if constexpr (is_signed<T>::value) {
			if (t == INFLL) res = "-inf";
		}
	}
	if (res.empty()) res = to_string(t);
	cerr << res;
}

template <typename T, typename U>
void dump(const pair<T, U>&);
template <typename T>
void dump(const pair<T*, int>&);

template <typename T>
void dump(const T& t,
          enable_if_t<!is_void<typename T::iterator>::value>* = nullptr) {
	cerr << "[ ";
	for (auto it = t.begin(); it != t.end();) {
		dump(*it);
		cerr << (++it == t.end() ? "" : ", ");
	}
	cerr << " ]";
}

template <typename T, typename U>
void dump(const pair<T, U>& t) {
	cerr << "( ";
	dump(t.first);
	cerr << ", ";
	dump(t.second);
	cerr << " )";
}

template <typename T>
void dump(const pair<T*, int>& t) {
	cerr << "[ ";
	for (int i = 0; i < t.second; i++) {
		dump(t.first[i]);
		cerr << (i == t.second - 1 ? "" : ", ");
	}
	cerr << " ]";
}

void trace() { cerr << endl; }
template <typename Head, typename... Tail>
void trace(Head&& head, Tail&&... tail) {
	cerr << " ";
	dump(head);
	if (sizeof...(tail) != 0) cerr << ",";
	trace(forward<Tail>(tail)...);
}
#else

void dump(const int& t) { }
void dump(const char& t) {}
void dump(const string& t) {}
void dump(const bool& t) {}

template <typename U,
          enable_if_t<!is_specialize<U>::value, nullptr_t> = nullptr>
void dump(const U& t) {}

template <typename T>
void dump(const T& t, enable_if_t<is_integral<T>::value>* = nullptr) {}

template <typename T, typename U>
void dump(const pair<T, U>&);
template <typename T>
void dump(const pair<T*, int>&);

template <typename T>
void dump(const T& t,
          enable_if_t<!is_void<typename T::iterator>::value>* = nullptr) {}

template <typename T, typename U>
void dump(const pair<T, U>& t) {}

template <typename T>
void dump(const pair<T*, int>& t) {}

void trace() {}
template <typename Head, typename... Tail>
void trace(Head&& head, Tail&&... tail) {}
#endif  //__LOCAL__
#endif  // __DEBUG_HPP__
using namespace std;
template <class T, class VAL = long long>
struct IntervalSet {
	struct Node {
		T left;
		T right;
		VAL value;

		Node(const T& l, const T& r, const VAL& v)
		    : left(l), right(r), value(v) {}
		bool operator<(const Node& rhs) const {
			if (left != rhs.left) return left < rhs.left;  // 左端で比較
			return right < rhs.right;  // 左端が同じならば右端で比較
		};
		friend ostream& operator<<(ostream& os, const Node& node) {
			os << "[" << node.left << ", " << node.right << "): " << node.value;
			return os;
		}
	};
	set<Node> nodes;

	IntervalSet() : nodes() {}
	constexpr typename set<Node>::iterator begin() { return nodes.begin(); }
	constexpr typename set<Node>::iterator end() { return nodes.end(); }
	constexpr typename set<Node>::iterator get_range(const T& x) {
		// xが含まれる区間を返す。含まれない場合はendを返す
		auto itr = nodes.upper_bound(Node(x, numeric_limits<T>::max(), 0));
		if (itr != nodes.begin()) {
			itr = prev(itr);
			trace("get_range:", *itr);
			if (itr->left <= x && x < itr->right) {
				// xが区間に含まれる
				trace("found range");
				return itr;
			}
		}
		return nodes.end();
	}
	constexpr T get_mex(const T& x) {
		// x以上かつ現在の区間に登録されていない最小値を返す
		auto itr = nodes.upper_bound(Node(x, numeric_limits<T>::max(), 0));
		if (itr != nodes.begin()) {
			itr = prev(itr);
			if (itr->left <= x && x < itr->right) {
				// xが区間に含まれる
				return itr->right;
			}
		}
		return x;
	}
	VAL insert(T left, T right, VAL value) {
		// 区間 [left, right)に値valueを挿入
		VAL res       = 0;
		T to_add_left = left;
		;
		T to_add_right = right;
		trace("insert [", left, right, ")");
		auto itr = nodes.lower_bound(Node(left, 0, 0));
		if (itr != nodes.end()) {
			trace("insert before:", *itr);
		} else {
			trace("insert before: end");
		}
		// 領域右側でかぶるかの確認を行う
		while (itr != nodes.end() and itr->left <= right) {
			// 領域が完全にかぶる場合
			if (left <= itr->left and itr->right <= right) {
				trace("case 1(full overlap)", *itr);
				res -= (itr->right - itr->left) * itr->value;
				itr = nodes.erase(itr);

			} else if (left <= itr->left and itr->left <= right and
			           right < itr->right) {
				// 領域の左側が一部でもかぶる場合
				trace("case 2(left partial overlap)", *itr);
				T r   = itr->right;
				VAL v = itr->value;
				res -= (itr->right - itr->left) * itr->value;
				itr          = nodes.erase(itr);
				to_add_right = r;
				break;
			} else {
				break;
			}
		}
		trace("back to begin");
		// 領域の左側でかぶるかの確認を行う
		if (itr != nodes.begin()) {
			itr = prev(itr);
			// 領域に重ならない
			if (itr->right < left) {
				trace("no overlap", *itr);
			} else if (itr->left <= left && left <= itr->right &&
			           itr->right <= right) {
				// 領域の右側にかぶる
				trace("case 3(right partial overlap)", *itr);
				T l   = itr->left;
				VAL v = itr->value;
				res -= (itr->right - itr->left) * itr->value;
				itr         = nodes.erase(itr);
				to_add_left = l;
			} else if ( itr->left<= left &&right <= itr->right  ) {
				// 領域が完全にかぶる
				trace("case 4(full overlap)", *itr);
				return 0;
			}
		}

		nodes.insert(Node(to_add_left, to_add_right, value));
		return res + (to_add_right - to_add_left) * value;
	}
	VAL remove(T left, T right) {
		VAL res = 0;
		// 区間 [left, right)を削除

		// [   ](     )  [ ]
		// [   ]  ([ ])  [ ]
		// [  (]  [   )    ];
		trace("current intrvals:");
		this->dump();
		trace("end of intervals");
		auto itr = nodes.lower_bound(Node(left, 0, 0));

		while (itr != nodes.end() && itr->left <= right) {
			// ２番目以降の区間を担当する

			if (left <= itr->left && itr->right <= right) {
				// 完全に囲んでいる: [ )   [[  [  )   )) [ )
				trace("case 1(range all erase)", *itr);
				res -= (itr->right - itr->left) * itr->value;
				itr = nodes.erase(itr);
				continue;
			}

			else if (itr->left < right && right <= itr->right) {
				// 左側が削除領域にかぶっている
				trace("case 2(range left erase)", *itr);
				T r   = itr->right;
				VAL v = itr->value;
				res -= (itr->right - itr->left) * itr->value;
				itr = nodes.erase(itr);
				res += insert(right, r, v);
				itr = nodes.lower_bound(Node(left, 0, 0));
				break;
			} else {
				break;
			}
		}
		trace("back to begin");
		// 先頭の区間を担当する
		if (itr != nodes.begin()) {
			itr = prev(itr);
			// 領域に重ならない
			if (itr->right <= left) {
				trace("no overlap", *itr);

			} else if (itr->left <= left && right <= itr->right) {
				// 領域の一部が削除領域にかぶっている
				trace("case 3 (range partial erase)", *itr);
				T l   = itr->left;
				T r   = itr->right;
				VAL v = itr->value;
				res -= (itr->right - itr->left) * itr->value;
				itr = nodes.erase(itr);
				res += insert(l, left, v);
				res += insert(right, r, v);
			} else if (itr->left <= left && itr->right < right) {
				// 右側が削除領域にかぶっている
				trace("case 4(range right erase)", *itr);
				T l   = itr->left;
				VAL v = itr->value;
				res -= (itr->right - itr->left) * itr->value;
				itr = nodes.erase(itr);
				res += insert(l, left, v);
			}
		}
		return res;
	}
	void dump() { trace(this->nodes); }
};
// https://yukicoder.me/problems/no/3017

struct Input {
	vector<ll> hights;
	static Input read() {
		ini(n);
		vector<ll> hights(n);
		inv1(hights);
		return Input{hights};
	}
};

void solve(const Input& input, IntervalSet<ll, int>& is) {
	long long cray_length = 0LL;
	for(int i = 0; i < input.hights.size(); i++) {
		if (i % 2 == 0) {
			cray_length+=is.insert(0, input.hights[i] , 1);
		} else {
			cray_length+=is.remove(0, input.hights[i] );
		}
	output(cray_length);
	}

}
int main() {
	auto input = Input::read();
	IntervalSet<long long, int> is;
	solve(input, is);
	return 0;
}
0