Submission #676195

#	Time	Username	Problem	Language	Result	Execution time	Memory
676195		dutinmeow	Two Antennas (JOI19_antennas)	C++17	100 / 100	1026 ms	51072 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

#pragma region debug

#ifndef NDEBUG
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	return os << '(' << p.first << ", " << p.second << ')';
}

template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}

template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	os << '[';
	if (v.size()) {
		os << *v.begin();
		for (auto i = ++v.begin(); i != v.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const deque<T> &d) {
	os << '[';
	if (d.size()) {
		os << *d.begin();
		for (auto i = ++d.begin(); i != d.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, stack<T> s) {
	os << '[';
	if (s.size()) {
		int n = s.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = s.top();
			s.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
	}
	return os << "]>";
}

template<typename T>
ostream &operator<<(ostream &os, queue<T> q) {
	os << '[';
	if (q.size()) {
		int n = q.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = q.front();
			q.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
	}
	return os << "]>";
}

template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &a) {
	os << '[';
	if (N) {
		os << *a.begin();
		for (auto i = ++a.begin(); i != a.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = ++s.begin(); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = ++s.begin(); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = ++s.begin(); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = ++m.begin(); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const unordered_map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = ++m.begin(); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

map<char, string> _dbg_dict {
	{'1', "--------------------------------"},
	{'2', "================================"},
	{'3', "≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡"},
	{'4', "################################"},
	{'*', "********************************"},
	{'_', "_"},
	{'<', "<!---- "},
	{'>', " ----!>"},
	{'(', "(!==== "},
	{')', "==== !)"},
	{'[', "[!≡≡≡≡ "},
	{']', " ≡≡≡≡!]"},
	{'{', "{!#### "},
	{'}', " ####!}"},
	{'c', "checkpoint "},
	{'l', "line "},
	{'n', "\n"},
	{'t', "\t"}
};

template<typename T>
void _dbg_print(string var, const T &a) { cerr << var << " = " << a << '\n'; }

void _dbg_print(string var, const char *a) {
	int n = strlen(a);
	for (int i = 0; i < n; i++) 
		cerr << (i < n - 1 && a[i] == '_' && _dbg_dict.find(a[i + 1]) != _dbg_dict.end() ? _dbg_dict[a[++i]] : string(1, a[i]));
}

#define dbg1(a) _dbg_print(#a, a);
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define dbg9(a, b, c, d, e, f, g, h, i) dbg1(a) dbg8(b, c, d, e, f, g, h, i)
#define dbg10(a, b, c, d, e, f, g, h, i, j) dbg1(a) dbg9(b, c, d, e, f, g, h, i, j)
#define dbg11(a, b, c, d, e, f, g, h, i, j, k) dbg1(a) dbg10(b, c, d, e, f, g, h, i, j, k)
#define dbg12(a, b, c, d, e, f, g, h, i, j, k, l) dbg1(a) dbg11(b, c, d, e, f, g, h, i, j, k, l)
#define dbg13(a, b, c, d, e, f, g, h, i, j, k, l, m) dbg1(a) dbg12(b, c, d, e, f, g, h, i, j, k, l, m)
#define dbg14(a, b, c, d, e, f, g, h, i, j, k, l, m, n) dbg1(a) dbg13(b, c, d, e, f, g, h, i, j, k, l, m, n)
#define dbg15(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) dbg1(a) dbg14(b, c, d, e, f, g, h, i, j, k, l, m, n, o)
#define dbg16(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) dbg1(a) dbg15(b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _16, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg16, dbg15, dbg14, dbg13, dbg12, dbg11, dbg10, dbg9, dbg8, \
	dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define dbg(...)
#endif

#pragma endregion debug

#pragma region zip

#ifndef ZIP_HPP
#define ZIP_HPP

namespace zip_internal {
	template<typename Iter>
	using select_access_type_for = conditional_t<
		is_same_v<Iter, vector<bool>::iterator> ||
		is_same_v<Iter, vector<bool>::const_iterator>,
		typename Iter::value_type,
		typename Iter::reference
	>;

	template<typename ...Args, size_t ...Index>
	auto any_match_impl(tuple<Args...> const & lhs, tuple<Args...> const & rhs, index_sequence<Index...>) -> bool {
		auto result = false;
		result = (... | (get<Index>(lhs) == get<Index>(rhs)));
		return result;
	}

	template<typename ...Args>
	auto any_match(tuple<Args...> const &lhs, tuple<Args...> const &rhs) -> bool {
		return any_match_impl(lhs, rhs, index_sequence_for<Args...>{});
	}

	template<typename ... Iters>
	class zip_iterator {
	public:
		using value_type = tuple<select_access_type_for<Iters>...>;

		zip_iterator() = delete;

		zip_iterator(Iters &&...iters) : m_iters {forward<Iters>(iters)...} {}

		auto operator++() -> zip_iterator &{
			apply([](auto && ... args) { ((args += 1), ...); }, m_iters);
			return *this;
		}

		auto operator++(int) -> zip_iterator {
			auto tmp = *this;
			++*this;
			return tmp;
		}

		auto operator!=(zip_iterator const &other) {
			return !(*this == other);
		}

		auto operator==(zip_iterator const &other) {
			auto result = false;
			return any_match(m_iters, other.m_iters);
		}

		auto operator*() -> value_type {
			return apply([](auto && ... args) { return value_type(*args...); }, m_iters);
		}

	private:
		tuple<Iters...> m_iters;
	};

	template<typename T>
	using select_iterator_for = conditional_t<
		is_const_v<remove_reference_t<T>>, 
		typename decay_t<T>::const_iterator, 
		typename decay_t<T>::iterator
	>;

	template<typename ...T>
	class zipper {
	public:
		using zip_type = zip_iterator<select_iterator_for<T>...>;

		template<typename ...Args>
		zipper(Args && ... args) : m_args{forward<Args>(args)...} {}

		auto begin() -> zip_type {
			return apply([](auto &&...args){ return zip_type(std::begin(args)...); }, m_args);
		}

		auto end() -> zip_type {
			return apply([](auto && ... args) { return zip_type(std::end(args)...); }, m_args);
		}

	private:
		tuple<T...> m_args;
	};
}

template<typename ...T>
auto zip(T &&...t) { return zip_internal::zipper<T ...>{forward<T>(t)...}; }

#endif

#pragma endregion zip

#pragma region y_combinator

#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

#endif

#pragma endregion y_combinator

#pragma region chmax

#ifndef CHMAX_HPP
#define CHMAX_HPP

template<typename T>
bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

#endif

#pragma endregion chmax

const long long NINF = -2e18;

struct segment_tree {
	int n;
	vector<long long> na, pb, lz;

	segment_tree(int _n) : n(_n) {
		na.resize(4 * n, NINF);
		pb.resize(4 * n, NINF);
		lz.resize(4 * n, NINF);
	}

private:
	void update_a(int a, long long v, int t, int tl, int tr) {
		if (tl == tr) {
			na[t] = v;
			return;
		}
		if (lz[t] != NINF) {
			chmax(pb[t * 2], lz[t] + na[t * 2]);
			chmax(lz[t * 2], lz[t]);
			chmax(pb[t * 2 + 1], lz[t] + na[t * 2 + 1]);
			chmax(lz[t * 2 + 1], lz[t]);
			lz[t] = NINF;
		}
		int tm = (tl + tr) / 2;
		if (a <= tm)
			update_a(a, v, t * 2, tl, tm);
		else 
			update_a(a, v, t * 2 + 1, tm + 1, tr);
		na[t] = max(na[t * 2], na[t * 2 + 1]);
	}

	void update_b(int bl, int br, long long v, int t, int tl, int tr) {
		if (br < tl || tr < bl)
			return;
		if (bl <= tl && tr <= br) {
			chmax(pb[t], v + na[t]);
			chmax(lz[t], v);
			return;
		}
		if (lz[t] != NINF) {
			chmax(pb[t * 2], lz[t] + na[t * 2]);
			chmax(lz[t * 2], lz[t]);
			chmax(pb[t * 2 + 1], lz[t] + na[t * 2 + 1]);
			chmax(lz[t * 2 + 1], lz[t]);
			lz[t] = NINF;
		}
		int tm = (tl + tr) / 2;
		update_b(bl, br, v, t * 2, tl, tm);
		update_b(bl, br, v, t * 2 + 1, tm + 1, tr);
		pb[t] = max(pb[t * 2], pb[t * 2 + 1]);
	}

	long long query(int ql, int qr, int t, int tl, int tr) {
		if (qr < tl || tr < ql)
			return NINF;
		if (ql <= tl && tr <= qr) 
			return pb[t];
		if (lz[t] != NINF) {
			chmax(pb[t * 2], lz[t] + na[t * 2]);
			chmax(lz[t * 2], lz[t]);
			chmax(pb[t * 2 + 1], lz[t] + na[t * 2 + 1]);
			chmax(lz[t * 2 + 1], lz[t]);
			lz[t] = NINF;
		}
		int tm = (tl + tr) / 2;
		return max(query(ql, qr, t * 2, tl, tm), query(ql, qr, t * 2 + 1, tm + 1, tr));
	}

public:

	void update_a(int a, long long v) { return update_a(a, v, 1, 0, n - 1); }

	void update_b(int bl, int br, long long v) { return update_b(bl, br, v, 1, 0, n - 1); }

	int query(int ql, int qr) { return query(ql, qr, 1, 0, n - 1); }

	friend ostream &operator<<(ostream& os, const segment_tree &_st) {
		auto st = _st;
		vector<long long> _na(st.n), _pb(st.n);
 
		auto dfs = y_combinator([&](auto dfs, int t, int tl, int tr) -> void {
			if (tl == tr) {
				tie(_na[tl], _pb[tl]) = tie(st.na[t], st.pb[t]);
				return;
			}
			if (st.lz[t] != NINF) {
				chmax(st.pb[t * 2], st.lz[t] + st.na[t * 2]);
				chmax(st.lz[t * 2], st.lz[t]);
				chmax(st.pb[t * 2 + 1], st.lz[t] + st.na[t * 2 + 1]);
				chmax(st.lz[t * 2 + 1], st.lz[t]);
				st.lz[t] = NINF;
			}
			int tm = (tl + tr) / 2;
			dfs(t * 2, tl, tm);
			dfs(t * 2 + 1, tm + 1, tr);
		});
 
		dfs(1, 0, st.n - 1);
 
		long long maxsum = 0;
		for (auto [a, b] : zip(_na, _pb))
			chmax(maxsum, b);
 
		os << '\n';
		os << "na = [";
		for (auto a : _na)
			os << (a > NINF / 2 ? to_string(a) : "INF") << ", ";
		os << "]\npb = [";
		for (auto a : _pb)
			os << (a > NINF / 2 ? to_string(a) : "INF") << ", ";
		os << "]\n";
		os << "max sum (in pb) is " << maxsum << '\n';
		return os;
	}
};

int main() {
	int N;
	cin >> N;
	vector<int> H(N), A(N), B(N);
	for (auto &&[h, a, b] : zip(H, A, B)) 
		cin >> h >> a >> b;
	int Q;
	cin >> Q;
	vector<pair<int, int>> Y(Q);
	for (auto &[l, r] : Y) {
		cin >> l >> r;
		l--, r--;
	}
	
	auto solve = [&](vector<int> &ans) {
		vector<vector<int>> S(N), E(N);
		for (int i = 0; i < N; i++) {
			if (i + A[i] < N) {
				S[i + A[i]].push_back(i);
				E[min(N - 1, i + B[i])].push_back(i);
			}
		}

		vector<vector<pair<int, int>>> Z(N);
		for (int i = 0; i < Q; i++) {
			auto [l, r] = Y[i];
			Z[r].emplace_back(l, i);
		}
		segment_tree sgt(N);
		for (int i = 0; i < N; i++) {
			for (int a : S[i])
				sgt.update_a(a, -H[a]);
			if (0 <= i - A[i])
				sgt.update_b(max(0, i - B[i]), i - A[i], H[i]);
			// dbg("_2\n", i, sgt);
			for (auto [l, q] : Z[i]) 
				chmax(ans[q], sgt.query(l, i));
			for (int a : E[i])
				sgt.update_a(a, NINF);
		}
	};

	vector<int> ans(Q, -1);
	solve(ans);

	reverse(H.begin(), H.end());
	reverse(A.begin(), A.end());
	reverse(B.begin(), B.end());
	for (auto &[l, r] : Y) {
		int tl = l, tr = r;
		l = N - 1 - tr, r = N - 1 - tl;
	}
	solve(ans);

	for (int a : ans)
		cout << a << '\n';
}

Compilation message (stderr)

antennas.cpp:4: warning: ignoring '#pragma region debug' [-Wunknown-pragmas]
    4 | #pragma region debug
      | 
antennas.cpp:197: warning: ignoring '#pragma endregion debug' [-Wunknown-pragmas]
  197 | #pragma endregion debug
      | 
antennas.cpp:199: warning: ignoring '#pragma region zip' [-Wunknown-pragmas]
  199 | #pragma region zip
      | 
antennas.cpp:295: warning: ignoring '#pragma endregion zip' [-Wunknown-pragmas]
  295 | #pragma endregion zip
      | 
antennas.cpp:297: warning: ignoring '#pragma region y_combinator' [-Wunknown-pragmas]
  297 | #pragma region y_combinator
      | 
antennas.cpp:322: warning: ignoring '#pragma endregion y_combinator' [-Wunknown-pragmas]
  322 | #pragma endregion y_combinator
      | 
antennas.cpp:324: warning: ignoring '#pragma region chmax' [-Wunknown-pragmas]
  324 | #pragma region chmax
      | 
antennas.cpp:340: warning: ignoring '#pragma endregion chmax' [-Wunknown-pragmas]
  340 | #pragma endregion chmax
      | 
antennas.cpp: In instantiation of 'auto zip_internal::zip_iterator<Iters>::operator==(const zip_internal::zip_iterator<Iters>&) [with Iters = {__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int, std::allocator<long long int> > >, __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int, std::allocator<long long int> > >}]':
antennas.cpp:246:19:   required from 'auto zip_internal::zip_iterator<Iters>::operator!=(const zip_internal::zip_iterator<Iters>&) [with Iters = {__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int, std::allocator<long long int> > >, __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int, std::allocator<long long int> > >}]'
antennas.cpp:444:34:   required from here
antennas.cpp:250:9: warning: unused variable 'result' [-Wunused-variable]
  250 |    auto result = false;
      |         ^~~~~~
antennas.cpp: In instantiation of 'auto zip_internal::zip_iterator<Iters>::operator==(const zip_internal::zip_iterator<Iters>&) [with Iters = {__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >}]':
antennas.cpp:246:19:   required from 'auto zip_internal::zip_iterator<Iters>::operator!=(const zip_internal::zip_iterator<Iters>&) [with Iters = {__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >}]'
antennas.cpp:464:37:   required from here
antennas.cpp:250:9: warning: unused variable 'result' [-Wunused-variable]

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65