oj.uz

Submission #676195

# Submission time Handle Problem Language Result Execution time Memory
676195 2022-12-29T18:46:42 Z dutinmeow Two Antennas (JOI19_antennas) C++17
100 / 100
 1026 ms 51072 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 276 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 308 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 276 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 308 KB Output is correct
25 Correct 123 ms 5248 KB Output is correct
26 Correct 20 ms 1328 KB Output is correct
27 Correct 201 ms 7752 KB Output is correct
28 Correct 181 ms 8568 KB Output is correct
29 Correct 125 ms 5520 KB Output is correct
30 Correct 122 ms 6324 KB Output is correct
31 Correct 137 ms 6532 KB Output is correct
32 Correct 182 ms 8696 KB Output is correct
33 Correct 160 ms 7116 KB Output is correct
34 Correct 94 ms 4524 KB Output is correct
35 Correct 172 ms 7676 KB Output is correct
36 Correct 183 ms 7972 KB Output is correct
37 Correct 103 ms 4904 KB Output is correct
38 Correct 173 ms 7364 KB Output is correct
39 Correct 29 ms 1724 KB Output is correct
40 Correct 171 ms 7252 KB Output is correct
41 Correct 129 ms 5856 KB Output is correct
42 Correct 175 ms 7248 KB Output is correct
43 Correct 59 ms 3124 KB Output is correct
44 Correct 184 ms 7260 KB Output is correct
45 Correct 34 ms 1996 KB Output is correct
46 Correct 185 ms 7372 KB Output is correct
47 Correct 47 ms 2620 KB Output is correct
48 Correct 185 ms 7500 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 39388 KB Output is correct
2 Correct 581 ms 43876 KB Output is correct
3 Correct 370 ms 30912 KB Output is correct
4 Correct 580 ms 43916 KB Output is correct
5 Correct 238 ms 20372 KB Output is correct
6 Correct 592 ms 43816 KB Output is correct
7 Correct 495 ms 38016 KB Output is correct
8 Correct 619 ms 43848 KB Output is correct
9 Correct 72 ms 7088 KB Output is correct
10 Correct 621 ms 43800 KB Output is correct
11 Correct 334 ms 27512 KB Output is correct
12 Correct 585 ms 43860 KB Output is correct
13 Correct 348 ms 42796 KB Output is correct
14 Correct 344 ms 42368 KB Output is correct
15 Correct 322 ms 41396 KB Output is correct
16 Correct 321 ms 41756 KB Output is correct
17 Correct 355 ms 42840 KB Output is correct
18 Correct 336 ms 41888 KB Output is correct
19 Correct 337 ms 42052 KB Output is correct
20 Correct 364 ms 42064 KB Output is correct
21 Correct 351 ms 42632 KB Output is correct
22 Correct 380 ms 42232 KB Output is correct
23 Correct 329 ms 42344 KB Output is correct
24 Correct 308 ms 41308 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 276 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 308 KB Output is correct
25 Correct 123 ms 5248 KB Output is correct
26 Correct 20 ms 1328 KB Output is correct
27 Correct 201 ms 7752 KB Output is correct
28 Correct 181 ms 8568 KB Output is correct
29 Correct 125 ms 5520 KB Output is correct
30 Correct 122 ms 6324 KB Output is correct
31 Correct 137 ms 6532 KB Output is correct
32 Correct 182 ms 8696 KB Output is correct
33 Correct 160 ms 7116 KB Output is correct
34 Correct 94 ms 4524 KB Output is correct
35 Correct 172 ms 7676 KB Output is correct
36 Correct 183 ms 7972 KB Output is correct
37 Correct 103 ms 4904 KB Output is correct
38 Correct 173 ms 7364 KB Output is correct
39 Correct 29 ms 1724 KB Output is correct
40 Correct 171 ms 7252 KB Output is correct
41 Correct 129 ms 5856 KB Output is correct
42 Correct 175 ms 7248 KB Output is correct
43 Correct 59 ms 3124 KB Output is correct
44 Correct 184 ms 7260 KB Output is correct
45 Correct 34 ms 1996 KB Output is correct
46 Correct 185 ms 7372 KB Output is correct
47 Correct 47 ms 2620 KB Output is correct
48 Correct 185 ms 7500 KB Output is correct
49 Correct 519 ms 39388 KB Output is correct
50 Correct 581 ms 43876 KB Output is correct
51 Correct 370 ms 30912 KB Output is correct
52 Correct 580 ms 43916 KB Output is correct
53 Correct 238 ms 20372 KB Output is correct
54 Correct 592 ms 43816 KB Output is correct
55 Correct 495 ms 38016 KB Output is correct
56 Correct 619 ms 43848 KB Output is correct
57 Correct 72 ms 7088 KB Output is correct
58 Correct 621 ms 43800 KB Output is correct
59 Correct 334 ms 27512 KB Output is correct
60 Correct 585 ms 43860 KB Output is correct
61 Correct 348 ms 42796 KB Output is correct
62 Correct 344 ms 42368 KB Output is correct
63 Correct 322 ms 41396 KB Output is correct
64 Correct 321 ms 41756 KB Output is correct
65 Correct 355 ms 42840 KB Output is correct
66 Correct 336 ms 41888 KB Output is correct
67 Correct 337 ms 42052 KB Output is correct
68 Correct 364 ms 42064 KB Output is correct
69 Correct 351 ms 42632 KB Output is correct
70 Correct 380 ms 42232 KB Output is correct
71 Correct 329 ms 42344 KB Output is correct
72 Correct 308 ms 41308 KB Output is correct
73 Correct 818 ms 45648 KB Output is correct
74 Correct 606 ms 44680 KB Output is correct
75 Correct 783 ms 39160 KB Output is correct
76 Correct 1004 ms 51072 KB Output is correct
77 Correct 522 ms 26392 KB Output is correct
78 Correct 849 ms 49140 KB Output is correct
79 Correct 879 ms 45740 KB Output is correct
80 Correct 970 ms 50996 KB Output is correct
81 Correct 331 ms 14444 KB Output is correct
82 Correct 757 ms 48036 KB Output is correct
83 Correct 694 ms 35820 KB Output is correct
84 Correct 1026 ms 51036 KB Output is correct
85 Correct 567 ms 47684 KB Output is correct
86 Correct 684 ms 49680 KB Output is correct
87 Correct 443 ms 42960 KB Output is correct
88 Correct 661 ms 48476 KB Output is correct
89 Correct 608 ms 48728 KB Output is correct
90 Correct 694 ms 48968 KB Output is correct
91 Correct 462 ms 45228 KB Output is correct
92 Correct 691 ms 49620 KB Output is correct
93 Correct 403 ms 44468 KB Output is correct
94 Correct 698 ms 49616 KB Output is correct
95 Correct 451 ms 44912 KB Output is correct
96 Correct 677 ms 48560 KB Output is correct