結果

問題 No.704 ゴミ拾い Medium
ユーザー ats5515ats5515
提出日時 2018-06-15 23:37:15
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 154 ms / 1,500 ms
コード長 3,255 bytes
コンパイル時間 1,599 ms
コンパイル使用メモリ 89,224 KB
実行使用メモリ 31,456 KB
最終ジャッジ日時 2023-09-13 05:23:21
合計ジャッジ時間 6,199 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 136 ms
31,100 KB
testcase_25 AC 154 ms
31,068 KB
testcase_26 AC 145 ms
30,964 KB
testcase_27 AC 141 ms
31,140 KB
testcase_28 AC 147 ms
31,372 KB
testcase_29 AC 135 ms
31,352 KB
testcase_30 AC 142 ms
31,284 KB
testcase_31 AC 147 ms
30,968 KB
testcase_32 AC 139 ms
30,972 KB
testcase_33 AC 141 ms
31,452 KB
testcase_34 AC 131 ms
31,292 KB
testcase_35 AC 130 ms
31,456 KB
testcase_36 AC 132 ms
30,964 KB
testcase_37 AC 132 ms
31,296 KB
testcase_38 AC 131 ms
31,400 KB
testcase_39 AC 130 ms
31,440 KB
testcase_40 AC 133 ms
31,444 KB
testcase_41 AC 130 ms
31,456 KB
testcase_42 AC 131 ms
31,292 KB
testcase_43 AC 132 ms
31,288 KB
testcase_44 AC 2 ms
4,380 KB
testcase_45 AC 1 ms
4,380 KB
testcase_46 AC 143 ms
31,356 KB
testcase_47 AC 145 ms
31,288 KB
権限があれば一括ダウンロードができます

ソースコード

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