結果

問題 No.704 ゴミ拾い Medium
ユーザー ats5515ats5515
提出日時 2018-06-15 23:37:15
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,255 bytes
コンパイル時間 626 ms
コンパイル使用メモリ 80,520 KB
最終ジャッジ日時 2024-06-30 15:33:14
合計ジャッジ時間 2,176 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In static member function ‘static constexpr T min_monoid<T>::id()’:
main.cpp:76:47: error: ‘numeric_limits’ is not a member of ‘std’
   76 |         static constexpr T id() { return std::numeric_limits<T>::max(); }
      |                                               ^~~~~~~~~~~~~~
main.cpp:76:63: error: expected primary-expression before ‘>’ token
   76 |         static constexpr T id() { return std::numeric_limits<T>::max(); }
      |                                                               ^
main.cpp:76:69: error: no matching function for call to ‘max()’
   76 |         static constexpr T id() { return std::numeric_limits<T>::max(); }
      |                                                                ~~~~~^~
In file included from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from main.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: ‘template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)’
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
main.cpp:76:69: note:   candidate expects 2 arguments, 0 provided
   76 |         static constexpr T id() { return std::numeric_limits<T>::max(); }
      |                                                                ~~~~~^~
In file included from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from main.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: ‘template<class _Tp, class _Compare> const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  300 |     max(const _Tp& __a, co

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <functional>
#include <utility>
using namespace std;
#define int long long
int MOD = 1000000007;
template <typename monoid>
struct segment_tree {
	using M = monoid;
	using T = typename M::value_type;

	std::size_t sz;
	std::vector<T> x;

	segment_tree(std::size_t n = 0) {
		sz = 1;
		while (sz < n) sz *= 2;
		x.assign(sz * 2, M::id());
		initialize();
	}

	template <typename iterator>
	segment_tree(iterator first, iterator last) {
		sz = 1;
		std::size_t n = std::distance(first, last);
		while (sz < n) sz *= 2;
		x.assign(sz * 2, M::id());
		std::copy(first, last, x.begin() + sz);
		initialize();
	}

	void fill(const T &val) {
		std::fill(x.begin() + sz, x.end(), val);
		initialize();
	}

	void initialize() {
		for (int i = (int)sz - 1; i >= 1; --i) {
			x[i] = M::op(x[i * 2 + 0], x[i * 2 + 1]);
		}
	}

	T accumulate(std::size_t l, std::size_t r) const {
		T al = M::id(), ar = M::id();
		for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
			if (l & 1) al = M::op(al, x[l++]);
			if (r & 1) ar = M::op(x[--r], ar);
		}
		return M::op(al, ar);
	}

	void update(std::size_t i, const T &val) {
		x[i += sz] = val;
		while (i > 1) {
			x[i / 2] = M::op(x[i], x[i ^ 1]);
			i /= 2;
		}
	}

	T operator[](std::size_t i) const { return x[sz + i]; }
};

template <typename T>
struct min_monoid {
	using value_type = T;
	static constexpr T id() { return std::numeric_limits<T>::max(); }
	static T op(const T &a, const T &b) { return std::min(a, b); }
};

template <typename T>
struct max_monoid {
	using value_type = T;
	static constexpr value_type id() { return std::numeric_limits<value_type>::min(); }
	static value_type op(const value_type &a, const value_type &b) { return std::max(a, b); }
};

template <typename T>
struct sum_monoid {
	using value_type = T;
	static constexpr value_type id() { return 0; }
	static value_type op(const value_type &a, const value_type &b) { return a + b; }
};

template <typename value_type>
using rmq = segment_tree<min_monoid<value_type>>;

template <typename value_type>
using rsq = segment_tree<sum_monoid<value_type>>;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N);
	vector<int> X(N);
	vector<int> Y(N);
	vector<int> dp(N + 1, 0);
	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		A[i]++;
	}
	for (int i = 0; i < N; i++) {
		cin >> X[i];
		X[i]++;
	}
	for (int i = 0; i < N; i++) {
		cin >> Y[i];
		//Y[i]++;
	}
	rmq<int> sg1(N);
	rmq<int> sg2(N);
	dp[0] = 0;

	sg1.update(0, dp[0] - X[0] + Y[0]);
	sg2.update(0, dp[0] + X[0] + Y[0]);
	X.push_back(1 << 30);
	//sg1.update()
	for (int i = 1; i <= N; i++) {
		int t = lower_bound(X.begin(), X.end(), A[i - 1]) - X.begin();
		int a;
	
		if (i <= t) {
			a = sg1.accumulate(0, i) + A[i - 1];
		}
		else {
			if (t != 0) {
				a = sg1.accumulate(0, t) + A[i - 1];
			} else {
				a = (int)1 << 60;
			}
			a = min(a, sg2.accumulate(t, i) - A[i - 1]);
		}
		dp[i] = a;
		if (i < N) {
			sg1.update(i, dp[i] - X[i] + Y[i]);
			sg2.update(i, dp[i] + X[i] + Y[i]);
		}
	}
	
	cout << dp[N] << endl;
}
0