oj.uz

Submission #1080970

# Submission time Handle Problem Language Result Execution time Memory
1080970 2024-08-29T16:32:05 Z vjudge1 Food Court (JOI21_foodcourt) C++17
100 / 100
 557 ms 57444 KB 
#include <bits/stdc++.h>
using namespace std;

template<bool HAS_QUERY, bool HAS_UPDATE, class T, class U, class F1, class F2, class F3>
struct segment_tree_base{
	static_assert(HAS_QUERY || HAS_UPDATE);
#define ifQ if constexpr(HAS_QUERY)
#define ifU if constexpr(HAS_UPDATE)
	int n, size, log;
	vector<T> data;
	vector<U> data_action;
	F1 TT; // monoid operation (always adjacent)
	T T_id; // monoid identity
	F2 UU; // monoid operation (superset, subset)
	U U_id; // monoid identity
	F3 UT; // action of U on T (superset, subset)
	// O(n)
	segment_tree_base(F1 TT, T T_id, F2 UU, U U_id, F3 UT): TT(TT), T_id(T_id), UU(UU), U_id(U_id), UT(UT){ }
	segment_tree_base &operator=(const segment_tree_base &seg){
		n = seg.n;
		size = seg.size;
		log = seg.log;
		data = seg.data;
		data_action = seg.data_action;
	}
	// O(1)
	friend void swap(segment_tree_base &x, segment_tree_base &y){
		swap(x.n, y.n);
		swap(x.size, y.size);
		swap(x.log, y.log);
		swap(x.data, y.data);
		swap(x.data_action, y.data_action);
	}
	// O(n)
	void build(int n){
		assert(n >= 0);
		this->n = n;
		size = 1;
		while(size < n) size <<= 1;
		log = __lg(size);
		ifQ data.assign(size << 1, T_id);
		ifU data_action.assign(HAS_QUERY ? size : size << 1, U_id);
	}
	// O(n)
	void build(int n, T x){
		static_assert(HAS_QUERY);
		assert(n >= 0);
		this->n = n;
		size = 1;
		while(size < n) size <<= 1;
		log = __lg(size);
		data.assign(size << 1, T_id);
		fill(data.begin() + size, data.begin() + size + n, x);
		for(auto i = size - 1; i >= 1; -- i) refresh(i);
		ifU data_action.assign(size, U_id);
	}
	// O(n)
	template<class V>
	void build(const vector<V> &a){
		static_assert(HAS_QUERY);
		n = (int)a.size();
		size = 1;
		while(size < n) size <<= 1;
		log = __lg(size);
		data.assign(size << 1, T_id);
		copy(a.begin(), a.end(), data.begin() + size);
		for(auto i = size - 1; i >= 1; -- i) refresh(i);
		ifU data_action.assign(size, U_id);
	}
	// O(n)
	void build_action(int n){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		assert(n >= 0);
		build(n);
	}
	// O(n)
	void build_action(int n, U f){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		assert(n >= 0);
		this->n = n;
		size = 1;
		while(size < n) size <<= 1;
		log = __lg(size);
		data_action.assign(size << 1, U_id);
		fill(data_action.begin() + size, data_action.begin() + size + n, f);
	}
	// O(n)
	template<class V>
	void build_action(const vector<V> &a){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		n = (int)a.size();
		size = 1;
		while(size < n) size <<= 1;
		log = __lg(size);
		data_action.assign(size << 1, U_id);
		copy(a.begin(), a.end(), data_action.begin() + size);
	}
	// O(1)
	void refresh(int u){
		static_assert(HAS_QUERY);
		data[u] = TT(data[u << 1], data[u << 1 | 1]);
	}
	// O(1)
	void apply(int u, U f){
		static_assert(HAS_UPDATE);
		ifQ data[u] = UT(f, data[u]);
		if(!HAS_QUERY || u < size) data_action[u] = UU(f, data_action[u]);
	}
	// O(1)
	void push(int u){
		static_assert(HAS_UPDATE);
		apply(u << 1, data_action[u]), apply(u << 1 | 1, data_action[u]);
		data_action[u] = U_id;
	}
	// O(log(n)) if HAS_UPDATE, O(1) otherwise.
	T query(int p){
		static_assert(HAS_QUERY);
		assert(0 <= p && p < n);
		p += size;
		ifU for(auto i = log; i >= 1; -- i) push(p >> i);
		return data[p];
	}
	// O(log(n))
	U query_action(int p){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		assert(0 <= p && p < n);
		p += size;
		ifU for(auto i = log; i >= 1; -- i) push(p >> i);
		return data_action[p];
	}
	// O(log(n))
	T query(int ql, int qr){
		static_assert(HAS_QUERY);
		assert(0 <= ql && ql <= qr && qr <= n);
		if(ql == qr) return T_id;
		ql += size, qr += size;
		ifU for(auto i = log; i >= 1; -- i){
			if(ql >> i << i != ql) push(ql >> i);
			if(qr >> i << i != qr) push(qr >> i);
		}
		T res_left = T_id, res_right = T_id;
		for(; ql < qr; ql >>= 1, qr >>= 1){
			if(ql & 1) res_left = TT(res_left, data[ql ++]);
			if(qr & 1) res_right = TT(data[-- qr], res_right);
		}
		return TT(res_left, res_right);
	}
	// O(1)
	T query_all() const{
		static_assert(HAS_QUERY);
		return data[1];
	}
	// O(n)
	vector<T> to_array(){
		static_assert(HAS_QUERY);
		ifU for(auto u = 1; u < size; ++ u) push(u);
		return vector<T>(data.begin() + size, data.begin() + size + n);
	}
	// O(n)
	vector<U> to_array_of_updates(){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		for(auto u = 1; u < size; ++ u) push(u);
		return vector<U>(data_action.begin() + size, data_action.begin() + size + n);
	}
	// O(log(n))
	void set(int p, T x){
		static_assert(HAS_QUERY);
		assert(0 <= p && p < n);
		p += size;
		ifU for(auto i = log; i >= 1; -- i) push(p >> i);
		data[p] = x;
		for(auto i = 1; i <= log; ++ i) refresh(p >> i);
	}
	// O(log(n))
	void set_action(int p, U f){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		assert(0 <= p && p < n);
		p += size;
		for(auto i = log; i >= 1; -- i) push(p >> i);
		data_action[p] = f;
	}
	// O(log(n))
	void update(int p, U f){
		static_assert(HAS_UPDATE);
		assert(0 <= p && p < n);
		p += size;
		for(auto i = log; i >= 1; -- i) push(p >> i);
		ifQ{
			data[p] = UT(f, data[p]);
			for(auto i = 1; i <= log; ++ i) refresh(p >> i);
		}
		else data_action[p] = UU(f, data_action[p]);
	}
	// O(log(n))
	void update(int ql, int qr, U f){
		static_assert(HAS_UPDATE);
		assert(0 <= ql && ql <= qr && qr <= n);
		if(ql == qr) return;
		ql += size, qr += size;
		for(auto i = log; i >= 1; -- i){
			if(ql >> i << i != ql) push(ql >> i);
			if(qr >> i << i != qr) push(qr >> i);
		}
		int _ql = ql, _qr = qr;
		for(; ql < qr; ql >>= 1, qr >>= 1){
			if(ql & 1) apply(ql ++, f);
			if(qr & 1) apply(-- qr, f);
		}
		ql = _ql, qr = _qr;
		ifQ for(auto i = 1; i <= log; ++ i){
			if(ql >> i << i != ql) refresh(ql >> i);
			if(qr >> i << i != qr) refresh(qr >> i);
		}
	}
	void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
		static_assert(HAS_QUERY && HAS_UPDATE);
		assert(0 <= ql && ql <= qr && qr <= n);
		if(ql == qr) return;
		ql += size, qr += size;
		for(auto i = log; i >= 1; -- i){
			if(ql >> i << i != ql) push(ql >> i);
			if(qr >> i << i != qr) push(qr >> i);
		}
		auto recurse = [&](auto self, int u)->void{
			if(exit_rule(data[u])) return;
			if(enter_rule(data[u])){
				apply(u, update_rule(data[u]));
				return;
			}
			push(u);
			self(self, u << 1), self(self, u << 1 | 1);
			refresh(u);
		};
		int _ql = ql, _qr = qr;
		for(; ql < qr; ql >>= 1, qr >>= 1){
			if(ql & 1) recurse(recurse, ql ++);
			if(qr & 1) recurse(recurse, -- qr);
		}
		ql = _ql, qr = _qr;
		for(auto i = 1; i <= log; ++ i){
			if(ql >> i << i != ql) refresh(ql >> i);
			if(qr >> i << i != qr) refresh(qr >> i);
		}
	}
	// pred(sum[ql, r)) is T, T, ..., T, F, F, ..., F
	// Returns max r with T
	// O(log(n))
	int max_pref(int ql, auto pred){
		static_assert(HAS_QUERY);
		assert(0 <= ql && ql <= n && pred(T_id));
		if(ql == n) return n;
		ql += size;
		ifU for(auto i = log; i >= 1; -- i) push(ql >> i);
		T sum = T_id;
		do{
			while(~ql & 1) ql >>= 1;
			if(!pred(TT(sum, data[ql]))){
				while(ql < size){
					ifU push(ql);
					ql = ql << 1;
					if(pred(TT(sum, data[ql]))) sum = TT(sum, data[ql ++]);
				}
				return ql - size;
			}
			sum = TT(sum, data[ql]);
			++ ql;
		}while((ql & -ql) != ql);
		return n;
	}
	// pred(sum[l, qr)) is F, F, ..., F, T, T, ..., T
	// Returns min l with T
	// O(log(n))
	int max_suff(int qr, auto pred){
		static_assert(HAS_QUERY);
		assert(0 <= qr && qr <= n && pred(T_id));
		if(qr == 0) return 0;
		qr += size;
		ifU for(auto i = log; i >= 1; -- i) push(qr - 1 >> i);
		T sum = T_id;
		do{
			-- qr;
			while(qr > 1 && qr & 1) qr >>= 1;
			if(!pred(TT(data[qr], sum))){
				while(qr < size){
					ifU push(qr);
					qr = qr << 1 | 1;
					if(pred(TT(data[qr], sum))) sum = TT(data[qr --], sum);
				}
				return qr + 1 - size;
			}
			sum = TT(data[qr], sum);
		}while((qr & -qr) != qr);
		return 0;
	}
	template<class output_stream>
	friend output_stream &operator<<(output_stream &out, segment_tree_base<HAS_QUERY, HAS_UPDATE, T, U, F1, F2, F3> seg){
		out << "{";
		for(auto i = 0; i < seg.n; ++ i){
			ifQ out << seg.query(i);
			else out << seg.query_action(i);
			if(i != seg.n - 1) out << ", ";
		}
		return out << '}';
	}
#undef ifQ
#undef ifU
};

// Supports query
template<class T, class F>
auto make_Q_segment_tree(F TT, T T_id){
	using U = int;
	auto _UU = [&](U, U)->U{ return U{}; };
	auto _UT = [&](U, T)->T{ return T{}; };
	return segment_tree_base<true, false, T, U, F, decltype(_UU), decltype(_UT)>(TT, T_id, _UU, U{}, _UT);
}
// Supports update
template<class U, class F>
auto make_U_segment_tree(F UU, U U_id){
	using T = int;
	auto _TT = [&](T, T)->T{ return T{}; };
	auto _UT = [&](U, T)->T{ return T{}; };
	return segment_tree_base<false, true, T, U, decltype(_TT), F, decltype(_UT)>(_TT, T{}, UU, U_id, _UT);
}
// Supports query and update
template<class T, class U, class F1, class F2, class F3>
auto make_QU_segment_tree(F1 TT, T T_id, F2 UU, U U_id, F3 UT){
	return segment_tree_base<true, true, T, U, F1, F2, F3>(TT, T_id, UU, U_id, UT);
}

#define ll long long
#define pii pair <int, int>
#define pli pair <ll, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 2.5e5;
const ll inf = 1e18;

using T1 = pli;
struct __TT1{
	T1 operator()(const T1& lhs, const T1& rhs){
		if (lhs.fi < rhs.fi) return lhs;
		return rhs;
	}
} TT1;
T1 T1_id = mp(+inf, 0);

using T2 = ll;
struct __TT2{
	T2 operator()(const T2& lhs, const T2& rhs){
		return max(lhs, rhs);
	}
} TT2;
T2 T2_id = 0;

using U = ll;
struct __UU{
	U operator()(const U& up, const U& down){
		return up+down;
	}
} UU;
U U_id = 0;

struct __UT1{
	T1 operator()(const U& up, const T1& down){
		T1 res;
		res.fi = down.fi+up;
		res.se = down.se;
		return res;
	}
} UT1;
struct __UT2{
	T2 operator()(const U& up, const T2& down){
		return up+down;
	}
} UT2;

int N, M, Q;
vector <T1> arr;
vector <pair <int, pii> > upd[NM+5];
vector <pli> qry[NM+5];
bool has_query[NM+5];
int grp[NM+5], ans[NM+5];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M >> Q;
	segment_tree_base st1 = make_QU_segment_tree(TT1, T1_id, UU, U_id, UT1);
	segment_tree_base st2 = make_QU_segment_tree(TT2, T2_id, UU, U_id, UT2);
	segment_tree_base st3 = make_QU_segment_tree(TT2, T2_id, UU, U_id, UT2);
	arr.resize(Q+1);
	for (int i = 0; i <= Q; i++) arr[i] = mp(0, i);
	st1.build(arr);
	st2.build(Q+1, 0);
	st3.build(Q+1, 0);
	
	for (int i = 1; i <= Q; i++){
		int type; cin >> type;
		if (type == 1){
			int l, r, c, k; cin >> l >> r >> c >> k;
			grp[i] = c;
			upd[l].push_back(mp(i, mp(1, k)));
			upd[r+1].push_back(mp(i, mp(1, -k)));
		}
		else if (type == 2){
			int l, r, k; cin >> l >> r >> k;
			upd[l].push_back(mp(i, mp(2, k)));
			upd[r+1].push_back(mp(i, mp(2, -k)));
		}
		else{
			int a; ll b; cin >> a >> b;
			qry[a].push_back(mp(b, i));
			has_query[i] = 1;
		}
	}

	for (int i = 1; i <= N; i++){
		for (pair <int, pii> p : upd[i]){
			st1.update(p.fi, Q+1, (p.se.fi == 1 ? p.se.se : -p.se.se));
			if (p.se.fi == 1) st2.update(p.fi, Q+1, p.se.se);
			else st3.update(p.fi, Q+1, p.se.se);
		}
		for (pli p : qry[i]){
			int r = p.se, l = st1.query(0, r+1).se;
			if (st1.query(r).fi-st1.query(l).fi < p.fi){
				ans[r] = 0;
				continue;
			}
			p.fi += st3.query(r)+st1.query(l).fi;
			ans[r] = grp[st2.max_pref(l+1, [&](const T2& node){return node < p.fi;})];
		}
	}
	for (int i = 1; i <= Q; i++)
		if (has_query[i]) cout << ans[i] << '\n';
	return 0;
}

Compilation message

foodcourt.cpp:215:36: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  215 |  void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                    ^~~~
foodcourt.cpp:215:52: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  215 |  void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                    ^~~~
foodcourt.cpp:215:69: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  215 |  void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                                     ^~~~
foodcourt.cpp:248:23: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  248 |  int max_pref(int ql, auto pred){
      |                       ^~~~
foodcourt.cpp:273:23: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  273 |  int max_suff(int qr, auto pred){
      |                       ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12476 KB Output is correct
2 Correct 8 ms 12376 KB Output is correct
3 Correct 7 ms 12380 KB Output is correct
4 Correct 7 ms 12380 KB Output is correct
5 Correct 6 ms 12380 KB Output is correct
6 Correct 6 ms 12472 KB Output is correct
7 Correct 8 ms 12376 KB Output is correct
8 Correct 8 ms 12380 KB Output is correct
9 Correct 7 ms 12544 KB Output is correct
10 Correct 6 ms 12380 KB Output is correct
11 Correct 7 ms 12488 KB Output is correct
12 Correct 7 ms 12380 KB Output is correct
13 Correct 6 ms 12376 KB Output is correct
14 Correct 7 ms 12376 KB Output is correct
15 Correct 9 ms 12380 KB Output is correct
16 Correct 7 ms 12476 KB Output is correct
17 Correct 7 ms 12380 KB Output is correct
18 Correct 7 ms 12380 KB Output is correct
19 Correct 7 ms 12380 KB Output is correct
20 Correct 7 ms 12336 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12476 KB Output is correct
2 Correct 8 ms 12376 KB Output is correct
3 Correct 7 ms 12380 KB Output is correct
4 Correct 7 ms 12380 KB Output is correct
5 Correct 6 ms 12380 KB Output is correct
6 Correct 6 ms 12472 KB Output is correct
7 Correct 8 ms 12376 KB Output is correct
8 Correct 8 ms 12380 KB Output is correct
9 Correct 7 ms 12544 KB Output is correct
10 Correct 6 ms 12380 KB Output is correct
11 Correct 7 ms 12488 KB Output is correct
12 Correct 7 ms 12380 KB Output is correct
13 Correct 6 ms 12376 KB Output is correct
14 Correct 7 ms 12376 KB Output is correct
15 Correct 9 ms 12380 KB Output is correct
16 Correct 7 ms 12476 KB Output is correct
17 Correct 7 ms 12380 KB Output is correct
18 Correct 7 ms 12380 KB Output is correct
19 Correct 7 ms 12380 KB Output is correct
20 Correct 7 ms 12336 KB Output is correct
21 Correct 7 ms 12380 KB Output is correct
22 Correct 8 ms 12380 KB Output is correct
23 Correct 7 ms 12380 KB Output is correct
24 Correct 8 ms 12444 KB Output is correct
25 Correct 6 ms 12380 KB Output is correct
26 Correct 8 ms 12484 KB Output is correct
27 Correct 8 ms 12380 KB Output is correct
28 Correct 8 ms 12572 KB Output is correct
29 Correct 8 ms 12380 KB Output is correct
30 Correct 11 ms 12632 KB Output is correct
31 Correct 7 ms 12380 KB Output is correct
32 Correct 8 ms 12376 KB Output is correct
33 Correct 6 ms 12380 KB Output is correct
34 Correct 7 ms 12416 KB Output is correct
35 Correct 7 ms 12380 KB Output is correct
36 Correct 7 ms 12452 KB Output is correct
37 Correct 7 ms 12632 KB Output is correct
38 Correct 8 ms 12380 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 23132 KB Output is correct
2 Correct 95 ms 23216 KB Output is correct
3 Correct 80 ms 23124 KB Output is correct
4 Correct 86 ms 23124 KB Output is correct
5 Correct 81 ms 23120 KB Output is correct
6 Correct 82 ms 23124 KB Output is correct
7 Correct 49 ms 21312 KB Output is correct
8 Correct 47 ms 21596 KB Output is correct
9 Correct 84 ms 23144 KB Output is correct
10 Correct 90 ms 23128 KB Output is correct
11 Correct 90 ms 23032 KB Output is correct
12 Correct 83 ms 23124 KB Output is correct
13 Correct 68 ms 22356 KB Output is correct
14 Correct 78 ms 23028 KB Output is correct
15 Correct 81 ms 23120 KB Output is correct
16 Correct 82 ms 23124 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 54436 KB Output is correct
2 Correct 340 ms 50516 KB Output is correct
3 Correct 493 ms 56408 KB Output is correct
4 Correct 427 ms 50892 KB Output is correct
5 Correct 369 ms 50916 KB Output is correct
6 Correct 557 ms 56832 KB Output is correct
7 Correct 206 ms 50520 KB Output is correct
8 Correct 269 ms 50660 KB Output is correct
9 Correct 474 ms 56120 KB Output is correct
10 Correct 475 ms 56108 KB Output is correct
11 Correct 477 ms 56256 KB Output is correct
12 Correct 491 ms 56660 KB Output is correct
13 Correct 498 ms 56144 KB Output is correct
14 Correct 456 ms 56528 KB Output is correct
15 Correct 468 ms 56404 KB Output is correct
16 Correct 489 ms 56536 KB Output is correct
17 Correct 461 ms 56400 KB Output is correct
18 Correct 459 ms 56404 KB Output is correct
19 Correct 473 ms 56596 KB Output is correct
20 Correct 455 ms 56344 KB Output is correct
21 Correct 465 ms 56652 KB Output is correct
22 Correct 460 ms 56656 KB Output is correct
23 Correct 505 ms 56660 KB Output is correct
24 Correct 482 ms 56736 KB Output is correct
25 Correct 383 ms 55380 KB Output is correct
26 Correct 391 ms 55908 KB Output is correct
27 Correct 377 ms 55232 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12476 KB Output is correct
2 Correct 8 ms 12376 KB Output is correct
3 Correct 7 ms 12380 KB Output is correct
4 Correct 7 ms 12380 KB Output is correct
5 Correct 6 ms 12380 KB Output is correct
6 Correct 6 ms 12472 KB Output is correct
7 Correct 8 ms 12376 KB Output is correct
8 Correct 8 ms 12380 KB Output is correct
9 Correct 7 ms 12544 KB Output is correct
10 Correct 6 ms 12380 KB Output is correct
11 Correct 7 ms 12488 KB Output is correct
12 Correct 7 ms 12380 KB Output is correct
13 Correct 6 ms 12376 KB Output is correct
14 Correct 7 ms 12376 KB Output is correct
15 Correct 9 ms 12380 KB Output is correct
16 Correct 7 ms 12476 KB Output is correct
17 Correct 7 ms 12380 KB Output is correct
18 Correct 7 ms 12380 KB Output is correct
19 Correct 7 ms 12380 KB Output is correct
20 Correct 7 ms 12336 KB Output is correct
21 Correct 74 ms 23132 KB Output is correct
22 Correct 95 ms 23216 KB Output is correct
23 Correct 80 ms 23124 KB Output is correct
24 Correct 86 ms 23124 KB Output is correct
25 Correct 81 ms 23120 KB Output is correct
26 Correct 82 ms 23124 KB Output is correct
27 Correct 49 ms 21312 KB Output is correct
28 Correct 47 ms 21596 KB Output is correct
29 Correct 84 ms 23144 KB Output is correct
30 Correct 90 ms 23128 KB Output is correct
31 Correct 90 ms 23032 KB Output is correct
32 Correct 83 ms 23124 KB Output is correct
33 Correct 68 ms 22356 KB Output is correct
34 Correct 78 ms 23028 KB Output is correct
35 Correct 81 ms 23120 KB Output is correct
36 Correct 82 ms 23124 KB Output is correct
37 Correct 92 ms 22440 KB Output is correct
38 Correct 75 ms 22092 KB Output is correct
39 Correct 43 ms 21076 KB Output is correct
40 Correct 47 ms 21484 KB Output is correct
41 Correct 95 ms 22864 KB Output is correct
42 Correct 99 ms 23060 KB Output is correct
43 Correct 95 ms 22868 KB Output is correct
44 Correct 91 ms 22872 KB Output is correct
45 Correct 91 ms 23124 KB Output is correct
46 Correct 103 ms 22992 KB Output is correct
47 Correct 54 ms 22080 KB Output is correct
48 Correct 84 ms 22700 KB Output is correct
49 Correct 66 ms 21328 KB Output is correct
50 Correct 83 ms 22320 KB Output is correct
51 Correct 89 ms 23088 KB Output is correct
52 Correct 91 ms 23124 KB Output is correct
53 Correct 68 ms 22152 KB Output is correct
54 Correct 87 ms 23284 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 22892 KB Output is correct
2 Correct 96 ms 23376 KB Output is correct
3 Correct 87 ms 23632 KB Output is correct
4 Correct 67 ms 21844 KB Output is correct
5 Correct 81 ms 22868 KB Output is correct
6 Correct 94 ms 23532 KB Output is correct
7 Correct 56 ms 21688 KB Output is correct
8 Correct 53 ms 21572 KB Output is correct
9 Correct 67 ms 22732 KB Output is correct
10 Correct 59 ms 21600 KB Output is correct
11 Correct 86 ms 23164 KB Output is correct
12 Correct 87 ms 23120 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12476 KB Output is correct
2 Correct 8 ms 12376 KB Output is correct
3 Correct 7 ms 12380 KB Output is correct
4 Correct 7 ms 12380 KB Output is correct
5 Correct 6 ms 12380 KB Output is correct
6 Correct 6 ms 12472 KB Output is correct
7 Correct 8 ms 12376 KB Output is correct
8 Correct 8 ms 12380 KB Output is correct
9 Correct 7 ms 12544 KB Output is correct
10 Correct 6 ms 12380 KB Output is correct
11 Correct 7 ms 12488 KB Output is correct
12 Correct 7 ms 12380 KB Output is correct
13 Correct 6 ms 12376 KB Output is correct
14 Correct 7 ms 12376 KB Output is correct
15 Correct 9 ms 12380 KB Output is correct
16 Correct 7 ms 12476 KB Output is correct
17 Correct 7 ms 12380 KB Output is correct
18 Correct 7 ms 12380 KB Output is correct
19 Correct 7 ms 12380 KB Output is correct
20 Correct 7 ms 12336 KB Output is correct
21 Correct 7 ms 12380 KB Output is correct
22 Correct 8 ms 12380 KB Output is correct
23 Correct 7 ms 12380 KB Output is correct
24 Correct 8 ms 12444 KB Output is correct
25 Correct 6 ms 12380 KB Output is correct
26 Correct 8 ms 12484 KB Output is correct
27 Correct 8 ms 12380 KB Output is correct
28 Correct 8 ms 12572 KB Output is correct
29 Correct 8 ms 12380 KB Output is correct
30 Correct 11 ms 12632 KB Output is correct
31 Correct 7 ms 12380 KB Output is correct
32 Correct 8 ms 12376 KB Output is correct
33 Correct 6 ms 12380 KB Output is correct
34 Correct 7 ms 12416 KB Output is correct
35 Correct 7 ms 12380 KB Output is correct
36 Correct 7 ms 12452 KB Output is correct
37 Correct 7 ms 12632 KB Output is correct
38 Correct 8 ms 12380 KB Output is correct
39 Correct 74 ms 23132 KB Output is correct
40 Correct 95 ms 23216 KB Output is correct
41 Correct 80 ms 23124 KB Output is correct
42 Correct 86 ms 23124 KB Output is correct
43 Correct 81 ms 23120 KB Output is correct
44 Correct 82 ms 23124 KB Output is correct
45 Correct 49 ms 21312 KB Output is correct
46 Correct 47 ms 21596 KB Output is correct
47 Correct 84 ms 23144 KB Output is correct
48 Correct 90 ms 23128 KB Output is correct
49 Correct 90 ms 23032 KB Output is correct
50 Correct 83 ms 23124 KB Output is correct
51 Correct 68 ms 22356 KB Output is correct
52 Correct 78 ms 23028 KB Output is correct
53 Correct 81 ms 23120 KB Output is correct
54 Correct 82 ms 23124 KB Output is correct
55 Correct 92 ms 22440 KB Output is correct
56 Correct 75 ms 22092 KB Output is correct
57 Correct 43 ms 21076 KB Output is correct
58 Correct 47 ms 21484 KB Output is correct
59 Correct 95 ms 22864 KB Output is correct
60 Correct 99 ms 23060 KB Output is correct
61 Correct 95 ms 22868 KB Output is correct
62 Correct 91 ms 22872 KB Output is correct
63 Correct 91 ms 23124 KB Output is correct
64 Correct 103 ms 22992 KB Output is correct
65 Correct 54 ms 22080 KB Output is correct
66 Correct 84 ms 22700 KB Output is correct
67 Correct 66 ms 21328 KB Output is correct
68 Correct 83 ms 22320 KB Output is correct
69 Correct 89 ms 23088 KB Output is correct
70 Correct 91 ms 23124 KB Output is correct
71 Correct 68 ms 22152 KB Output is correct
72 Correct 87 ms 23284 KB Output is correct
73 Correct 80 ms 22892 KB Output is correct
74 Correct 96 ms 23376 KB Output is correct
75 Correct 87 ms 23632 KB Output is correct
76 Correct 67 ms 21844 KB Output is correct
77 Correct 81 ms 22868 KB Output is correct
78 Correct 94 ms 23532 KB Output is correct
79 Correct 56 ms 21688 KB Output is correct
80 Correct 53 ms 21572 KB Output is correct
81 Correct 67 ms 22732 KB Output is correct
82 Correct 59 ms 21600 KB Output is correct
83 Correct 86 ms 23164 KB Output is correct
84 Correct 87 ms 23120 KB Output is correct
85 Correct 80 ms 22932 KB Output is correct
86 Correct 95 ms 23388 KB Output is correct
87 Correct 103 ms 22876 KB Output is correct
88 Correct 100 ms 23632 KB Output is correct
89 Correct 60 ms 21588 KB Output is correct
90 Correct 92 ms 23472 KB Output is correct
91 Correct 72 ms 22480 KB Output is correct
92 Correct 77 ms 22256 KB Output is correct
93 Correct 98 ms 23636 KB Output is correct
94 Correct 94 ms 23564 KB Output is correct
95 Correct 96 ms 23380 KB Output is correct
96 Correct 99 ms 23548 KB Output is correct
97 Correct 105 ms 23484 KB Output is correct
98 Correct 79 ms 22740 KB Output is correct
99 Correct 61 ms 22588 KB Output is correct
100 Correct 69 ms 22188 KB Output is correct
101 Correct 81 ms 23372 KB Output is correct
102 Correct 91 ms 23388 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12476 KB Output is correct
2 Correct 8 ms 12376 KB Output is correct
3 Correct 7 ms 12380 KB Output is correct
4 Correct 7 ms 12380 KB Output is correct
5 Correct 6 ms 12380 KB Output is correct
6 Correct 6 ms 12472 KB Output is correct
7 Correct 8 ms 12376 KB Output is correct
8 Correct 8 ms 12380 KB Output is correct
9 Correct 7 ms 12544 KB Output is correct
10 Correct 6 ms 12380 KB Output is correct
11 Correct 7 ms 12488 KB Output is correct
12 Correct 7 ms 12380 KB Output is correct
13 Correct 6 ms 12376 KB Output is correct
14 Correct 7 ms 12376 KB Output is correct
15 Correct 9 ms 12380 KB Output is correct
16 Correct 7 ms 12476 KB Output is correct
17 Correct 7 ms 12380 KB Output is correct
18 Correct 7 ms 12380 KB Output is correct
19 Correct 7 ms 12380 KB Output is correct
20 Correct 7 ms 12336 KB Output is correct
21 Correct 7 ms 12380 KB Output is correct
22 Correct 8 ms 12380 KB Output is correct
23 Correct 7 ms 12380 KB Output is correct
24 Correct 8 ms 12444 KB Output is correct
25 Correct 6 ms 12380 KB Output is correct
26 Correct 8 ms 12484 KB Output is correct
27 Correct 8 ms 12380 KB Output is correct
28 Correct 8 ms 12572 KB Output is correct
29 Correct 8 ms 12380 KB Output is correct
30 Correct 11 ms 12632 KB Output is correct
31 Correct 7 ms 12380 KB Output is correct
32 Correct 8 ms 12376 KB Output is correct
33 Correct 6 ms 12380 KB Output is correct
34 Correct 7 ms 12416 KB Output is correct
35 Correct 7 ms 12380 KB Output is correct
36 Correct 7 ms 12452 KB Output is correct
37 Correct 7 ms 12632 KB Output is correct
38 Correct 8 ms 12380 KB Output is correct
39 Correct 74 ms 23132 KB Output is correct
40 Correct 95 ms 23216 KB Output is correct
41 Correct 80 ms 23124 KB Output is correct
42 Correct 86 ms 23124 KB Output is correct
43 Correct 81 ms 23120 KB Output is correct
44 Correct 82 ms 23124 KB Output is correct
45 Correct 49 ms 21312 KB Output is correct
46 Correct 47 ms 21596 KB Output is correct
47 Correct 84 ms 23144 KB Output is correct
48 Correct 90 ms 23128 KB Output is correct
49 Correct 90 ms 23032 KB Output is correct
50 Correct 83 ms 23124 KB Output is correct
51 Correct 68 ms 22356 KB Output is correct
52 Correct 78 ms 23028 KB Output is correct
53 Correct 81 ms 23120 KB Output is correct
54 Correct 82 ms 23124 KB Output is correct
55 Correct 403 ms 54436 KB Output is correct
56 Correct 340 ms 50516 KB Output is correct
57 Correct 493 ms 56408 KB Output is correct
58 Correct 427 ms 50892 KB Output is correct
59 Correct 369 ms 50916 KB Output is correct
60 Correct 557 ms 56832 KB Output is correct
61 Correct 206 ms 50520 KB Output is correct
62 Correct 269 ms 50660 KB Output is correct
63 Correct 474 ms 56120 KB Output is correct
64 Correct 475 ms 56108 KB Output is correct
65 Correct 477 ms 56256 KB Output is correct
66 Correct 491 ms 56660 KB Output is correct
67 Correct 498 ms 56144 KB Output is correct
68 Correct 456 ms 56528 KB Output is correct
69 Correct 468 ms 56404 KB Output is correct
70 Correct 489 ms 56536 KB Output is correct
71 Correct 461 ms 56400 KB Output is correct
72 Correct 459 ms 56404 KB Output is correct
73 Correct 473 ms 56596 KB Output is correct
74 Correct 455 ms 56344 KB Output is correct
75 Correct 465 ms 56652 KB Output is correct
76 Correct 460 ms 56656 KB Output is correct
77 Correct 505 ms 56660 KB Output is correct
78 Correct 482 ms 56736 KB Output is correct
79 Correct 383 ms 55380 KB Output is correct
80 Correct 391 ms 55908 KB Output is correct
81 Correct 377 ms 55232 KB Output is correct
82 Correct 92 ms 22440 KB Output is correct
83 Correct 75 ms 22092 KB Output is correct
84 Correct 43 ms 21076 KB Output is correct
85 Correct 47 ms 21484 KB Output is correct
86 Correct 95 ms 22864 KB Output is correct
87 Correct 99 ms 23060 KB Output is correct
88 Correct 95 ms 22868 KB Output is correct
89 Correct 91 ms 22872 KB Output is correct
90 Correct 91 ms 23124 KB Output is correct
91 Correct 103 ms 22992 KB Output is correct
92 Correct 54 ms 22080 KB Output is correct
93 Correct 84 ms 22700 KB Output is correct
94 Correct 66 ms 21328 KB Output is correct
95 Correct 83 ms 22320 KB Output is correct
96 Correct 89 ms 23088 KB Output is correct
97 Correct 91 ms 23124 KB Output is correct
98 Correct 68 ms 22152 KB Output is correct
99 Correct 87 ms 23284 KB Output is correct
100 Correct 80 ms 22892 KB Output is correct
101 Correct 96 ms 23376 KB Output is correct
102 Correct 87 ms 23632 KB Output is correct
103 Correct 67 ms 21844 KB Output is correct
104 Correct 81 ms 22868 KB Output is correct
105 Correct 94 ms 23532 KB Output is correct
106 Correct 56 ms 21688 KB Output is correct
107 Correct 53 ms 21572 KB Output is correct
108 Correct 67 ms 22732 KB Output is correct
109 Correct 59 ms 21600 KB Output is correct
110 Correct 86 ms 23164 KB Output is correct
111 Correct 87 ms 23120 KB Output is correct
112 Correct 80 ms 22932 KB Output is correct
113 Correct 95 ms 23388 KB Output is correct
114 Correct 103 ms 22876 KB Output is correct
115 Correct 100 ms 23632 KB Output is correct
116 Correct 60 ms 21588 KB Output is correct
117 Correct 92 ms 23472 KB Output is correct
118 Correct 72 ms 22480 KB Output is correct
119 Correct 77 ms 22256 KB Output is correct
120 Correct 98 ms 23636 KB Output is correct
121 Correct 94 ms 23564 KB Output is correct
122 Correct 96 ms 23380 KB Output is correct
123 Correct 99 ms 23548 KB Output is correct
124 Correct 105 ms 23484 KB Output is correct
125 Correct 79 ms 22740 KB Output is correct
126 Correct 61 ms 22588 KB Output is correct
127 Correct 69 ms 22188 KB Output is correct
128 Correct 81 ms 23372 KB Output is correct
129 Correct 91 ms 23388 KB Output is correct
130 Correct 463 ms 56860 KB Output is correct
131 Correct 323 ms 50832 KB Output is correct
132 Correct 448 ms 56832 KB Output is correct
133 Correct 469 ms 56404 KB Output is correct
134 Correct 426 ms 54100 KB Output is correct
135 Correct 508 ms 57428 KB Output is correct
136 Correct 473 ms 57444 KB Output is correct
137 Correct 475 ms 57168 KB Output is correct
138 Correct 470 ms 56788 KB Output is correct
139 Correct 479 ms 57312 KB Output is correct
140 Correct 478 ms 56876 KB Output is correct
141 Correct 500 ms 57252 KB Output is correct
142 Correct 472 ms 57424 KB Output is correct
143 Correct 483 ms 57200 KB Output is correct
144 Correct 469 ms 56912 KB Output is correct
145 Correct 509 ms 57172 KB Output is correct
146 Correct 487 ms 57104 KB Output is correct
147 Correct 466 ms 57168 KB Output is correct
148 Correct 479 ms 57172 KB Output is correct
149 Correct 475 ms 57196 KB Output is correct
150 Correct 243 ms 53300 KB Output is correct
151 Correct 390 ms 56480 KB Output is correct
152 Correct 433 ms 56400 KB Output is correct
153 Correct 397 ms 56152 KB Output is correct