oj.uz

Submission #1080975

# Submission time Handle Problem Language Result Execution time Memory
1080975 2024-08-29T16:34:48 Z daoquanglinh2007 Food Court (JOI21_foodcourt) C++17
100 / 100
 575 ms 56404 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 7 ms 12376 KB Output is correct
2 Correct 10 ms 12664 KB Output is correct
3 Correct 7 ms 12416 KB Output is correct
4 Correct 7 ms 12552 KB Output is correct
5 Correct 6 ms 12516 KB Output is correct
6 Correct 7 ms 12380 KB Output is correct
7 Correct 7 ms 12380 KB Output is correct
8 Correct 7 ms 12384 KB Output is correct
9 Correct 8 ms 12380 KB Output is correct
10 Correct 7 ms 12380 KB Output is correct
11 Correct 7 ms 12380 KB Output is correct
12 Correct 7 ms 12376 KB Output is correct
13 Correct 5 ms 12380 KB Output is correct
14 Correct 6 ms 12564 KB Output is correct
15 Correct 8 ms 12380 KB Output is correct
16 Correct 7 ms 12380 KB Output is correct
17 Correct 7 ms 12380 KB Output is correct
18 Correct 7 ms 12380 KB Output is correct
19 Correct 6 ms 12380 KB Output is correct
20 Correct 7 ms 12380 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12376 KB Output is correct
2 Correct 10 ms 12664 KB Output is correct
3 Correct 7 ms 12416 KB Output is correct
4 Correct 7 ms 12552 KB Output is correct
5 Correct 6 ms 12516 KB Output is correct
6 Correct 7 ms 12380 KB Output is correct
7 Correct 7 ms 12380 KB Output is correct
8 Correct 7 ms 12384 KB Output is correct
9 Correct 8 ms 12380 KB Output is correct
10 Correct 7 ms 12380 KB Output is correct
11 Correct 7 ms 12380 KB Output is correct
12 Correct 7 ms 12376 KB Output is correct
13 Correct 5 ms 12380 KB Output is correct
14 Correct 6 ms 12564 KB Output is correct
15 Correct 8 ms 12380 KB Output is correct
16 Correct 7 ms 12380 KB Output is correct
17 Correct 7 ms 12380 KB Output is correct
18 Correct 7 ms 12380 KB Output is correct
19 Correct 6 ms 12380 KB Output is correct
20 Correct 7 ms 12380 KB Output is correct
21 Correct 7 ms 12380 KB Output is correct
22 Correct 7 ms 12496 KB Output is correct
23 Correct 7 ms 12380 KB Output is correct
24 Correct 7 ms 12392 KB Output is correct
25 Correct 6 ms 12380 KB Output is correct
26 Correct 6 ms 12380 KB Output is correct
27 Correct 7 ms 12376 KB Output is correct
28 Correct 8 ms 12376 KB Output is correct
29 Correct 8 ms 12380 KB Output is correct
30 Correct 7 ms 12380 KB Output is correct
31 Correct 7 ms 12380 KB Output is correct
32 Correct 7 ms 12376 KB Output is correct
33 Correct 7 ms 12380 KB Output is correct
34 Correct 6 ms 12564 KB Output is correct
35 Correct 6 ms 12552 KB Output is correct
36 Correct 6 ms 12380 KB Output is correct
37 Correct 6 ms 12380 KB Output is correct
38 Correct 6 ms 12552 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 23016 KB Output is correct
2 Correct 83 ms 23216 KB Output is correct
3 Correct 86 ms 23124 KB Output is correct
4 Correct 81 ms 23116 KB Output is correct
5 Correct 83 ms 23132 KB Output is correct
6 Correct 82 ms 23124 KB Output is correct
7 Correct 46 ms 21528 KB Output is correct
8 Correct 48 ms 21588 KB Output is correct
9 Correct 87 ms 23128 KB Output is correct
10 Correct 76 ms 23164 KB Output is correct
11 Correct 89 ms 23128 KB Output is correct
12 Correct 86 ms 23132 KB Output is correct
13 Correct 67 ms 22352 KB Output is correct
14 Correct 77 ms 22868 KB Output is correct
15 Correct 83 ms 23176 KB Output is correct
16 Correct 84 ms 23288 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 54484 KB Output is correct
2 Correct 336 ms 50512 KB Output is correct
3 Correct 477 ms 56104 KB Output is correct
4 Correct 365 ms 50772 KB Output is correct
5 Correct 379 ms 50644 KB Output is correct
6 Correct 494 ms 56404 KB Output is correct
7 Correct 205 ms 50516 KB Output is correct
8 Correct 220 ms 50380 KB Output is correct
9 Correct 475 ms 55688 KB Output is correct
10 Correct 471 ms 55680 KB Output is correct
11 Correct 527 ms 55672 KB Output is correct
12 Correct 499 ms 56144 KB Output is correct
13 Correct 469 ms 55636 KB Output is correct
14 Correct 470 ms 56172 KB Output is correct
15 Correct 542 ms 56400 KB Output is correct
16 Correct 479 ms 56100 KB Output is correct
17 Correct 499 ms 56164 KB Output is correct
18 Correct 468 ms 55888 KB Output is correct
19 Correct 459 ms 56060 KB Output is correct
20 Correct 445 ms 55888 KB Output is correct
21 Correct 459 ms 56248 KB Output is correct
22 Correct 446 ms 56144 KB Output is correct
23 Correct 466 ms 56184 KB Output is correct
24 Correct 484 ms 56148 KB Output is correct
25 Correct 381 ms 55216 KB Output is correct
26 Correct 411 ms 55632 KB Output is correct
27 Correct 383 ms 54944 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12376 KB Output is correct
2 Correct 10 ms 12664 KB Output is correct
3 Correct 7 ms 12416 KB Output is correct
4 Correct 7 ms 12552 KB Output is correct
5 Correct 6 ms 12516 KB Output is correct
6 Correct 7 ms 12380 KB Output is correct
7 Correct 7 ms 12380 KB Output is correct
8 Correct 7 ms 12384 KB Output is correct
9 Correct 8 ms 12380 KB Output is correct
10 Correct 7 ms 12380 KB Output is correct
11 Correct 7 ms 12380 KB Output is correct
12 Correct 7 ms 12376 KB Output is correct
13 Correct 5 ms 12380 KB Output is correct
14 Correct 6 ms 12564 KB Output is correct
15 Correct 8 ms 12380 KB Output is correct
16 Correct 7 ms 12380 KB Output is correct
17 Correct 7 ms 12380 KB Output is correct
18 Correct 7 ms 12380 KB Output is correct
19 Correct 6 ms 12380 KB Output is correct
20 Correct 7 ms 12380 KB Output is correct
21 Correct 84 ms 23016 KB Output is correct
22 Correct 83 ms 23216 KB Output is correct
23 Correct 86 ms 23124 KB Output is correct
24 Correct 81 ms 23116 KB Output is correct
25 Correct 83 ms 23132 KB Output is correct
26 Correct 82 ms 23124 KB Output is correct
27 Correct 46 ms 21528 KB Output is correct
28 Correct 48 ms 21588 KB Output is correct
29 Correct 87 ms 23128 KB Output is correct
30 Correct 76 ms 23164 KB Output is correct
31 Correct 89 ms 23128 KB Output is correct
32 Correct 86 ms 23132 KB Output is correct
33 Correct 67 ms 22352 KB Output is correct
34 Correct 77 ms 22868 KB Output is correct
35 Correct 83 ms 23176 KB Output is correct
36 Correct 84 ms 23288 KB Output is correct
37 Correct 83 ms 22356 KB Output is correct
38 Correct 69 ms 22100 KB Output is correct
39 Correct 40 ms 21072 KB Output is correct
40 Correct 48 ms 21480 KB Output is correct
41 Correct 87 ms 22932 KB Output is correct
42 Correct 90 ms 23120 KB Output is correct
43 Correct 96 ms 23120 KB Output is correct
44 Correct 92 ms 22864 KB Output is correct
45 Correct 91 ms 23088 KB Output is correct
46 Correct 114 ms 22864 KB Output is correct
47 Correct 55 ms 22084 KB Output is correct
48 Correct 79 ms 22864 KB Output is correct
49 Correct 62 ms 21432 KB Output is correct
50 Correct 73 ms 22356 KB Output is correct
51 Correct 94 ms 23120 KB Output is correct
52 Correct 89 ms 23060 KB Output is correct
53 Correct 71 ms 22100 KB Output is correct
54 Correct 84 ms 23124 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 22868 KB Output is correct
2 Correct 90 ms 23344 KB Output is correct
3 Correct 90 ms 23472 KB Output is correct
4 Correct 68 ms 21840 KB Output is correct
5 Correct 84 ms 22732 KB Output is correct
6 Correct 88 ms 23376 KB Output is correct
7 Correct 52 ms 21732 KB Output is correct
8 Correct 63 ms 21576 KB Output is correct
9 Correct 65 ms 22736 KB Output is correct
10 Correct 61 ms 21584 KB Output is correct
11 Correct 81 ms 23120 KB Output is correct
12 Correct 102 ms 23032 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12376 KB Output is correct
2 Correct 10 ms 12664 KB Output is correct
3 Correct 7 ms 12416 KB Output is correct
4 Correct 7 ms 12552 KB Output is correct
5 Correct 6 ms 12516 KB Output is correct
6 Correct 7 ms 12380 KB Output is correct
7 Correct 7 ms 12380 KB Output is correct
8 Correct 7 ms 12384 KB Output is correct
9 Correct 8 ms 12380 KB Output is correct
10 Correct 7 ms 12380 KB Output is correct
11 Correct 7 ms 12380 KB Output is correct
12 Correct 7 ms 12376 KB Output is correct
13 Correct 5 ms 12380 KB Output is correct
14 Correct 6 ms 12564 KB Output is correct
15 Correct 8 ms 12380 KB Output is correct
16 Correct 7 ms 12380 KB Output is correct
17 Correct 7 ms 12380 KB Output is correct
18 Correct 7 ms 12380 KB Output is correct
19 Correct 6 ms 12380 KB Output is correct
20 Correct 7 ms 12380 KB Output is correct
21 Correct 7 ms 12380 KB Output is correct
22 Correct 7 ms 12496 KB Output is correct
23 Correct 7 ms 12380 KB Output is correct
24 Correct 7 ms 12392 KB Output is correct
25 Correct 6 ms 12380 KB Output is correct
26 Correct 6 ms 12380 KB Output is correct
27 Correct 7 ms 12376 KB Output is correct
28 Correct 8 ms 12376 KB Output is correct
29 Correct 8 ms 12380 KB Output is correct
30 Correct 7 ms 12380 KB Output is correct
31 Correct 7 ms 12380 KB Output is correct
32 Correct 7 ms 12376 KB Output is correct
33 Correct 7 ms 12380 KB Output is correct
34 Correct 6 ms 12564 KB Output is correct
35 Correct 6 ms 12552 KB Output is correct
36 Correct 6 ms 12380 KB Output is correct
37 Correct 6 ms 12380 KB Output is correct
38 Correct 6 ms 12552 KB Output is correct
39 Correct 84 ms 23016 KB Output is correct
40 Correct 83 ms 23216 KB Output is correct
41 Correct 86 ms 23124 KB Output is correct
42 Correct 81 ms 23116 KB Output is correct
43 Correct 83 ms 23132 KB Output is correct
44 Correct 82 ms 23124 KB Output is correct
45 Correct 46 ms 21528 KB Output is correct
46 Correct 48 ms 21588 KB Output is correct
47 Correct 87 ms 23128 KB Output is correct
48 Correct 76 ms 23164 KB Output is correct
49 Correct 89 ms 23128 KB Output is correct
50 Correct 86 ms 23132 KB Output is correct
51 Correct 67 ms 22352 KB Output is correct
52 Correct 77 ms 22868 KB Output is correct
53 Correct 83 ms 23176 KB Output is correct
54 Correct 84 ms 23288 KB Output is correct
55 Correct 83 ms 22356 KB Output is correct
56 Correct 69 ms 22100 KB Output is correct
57 Correct 40 ms 21072 KB Output is correct
58 Correct 48 ms 21480 KB Output is correct
59 Correct 87 ms 22932 KB Output is correct
60 Correct 90 ms 23120 KB Output is correct
61 Correct 96 ms 23120 KB Output is correct
62 Correct 92 ms 22864 KB Output is correct
63 Correct 91 ms 23088 KB Output is correct
64 Correct 114 ms 22864 KB Output is correct
65 Correct 55 ms 22084 KB Output is correct
66 Correct 79 ms 22864 KB Output is correct
67 Correct 62 ms 21432 KB Output is correct
68 Correct 73 ms 22356 KB Output is correct
69 Correct 94 ms 23120 KB Output is correct
70 Correct 89 ms 23060 KB Output is correct
71 Correct 71 ms 22100 KB Output is correct
72 Correct 84 ms 23124 KB Output is correct
73 Correct 95 ms 22868 KB Output is correct
74 Correct 90 ms 23344 KB Output is correct
75 Correct 90 ms 23472 KB Output is correct
76 Correct 68 ms 21840 KB Output is correct
77 Correct 84 ms 22732 KB Output is correct
78 Correct 88 ms 23376 KB Output is correct
79 Correct 52 ms 21732 KB Output is correct
80 Correct 63 ms 21576 KB Output is correct
81 Correct 65 ms 22736 KB Output is correct
82 Correct 61 ms 21584 KB Output is correct
83 Correct 81 ms 23120 KB Output is correct
84 Correct 102 ms 23032 KB Output is correct
85 Correct 81 ms 22876 KB Output is correct
86 Correct 92 ms 23384 KB Output is correct
87 Correct 88 ms 22916 KB Output is correct
88 Correct 108 ms 23380 KB Output is correct
89 Correct 65 ms 21596 KB Output is correct
90 Correct 94 ms 23380 KB Output is correct
91 Correct 78 ms 22360 KB Output is correct
92 Correct 72 ms 22096 KB Output is correct
93 Correct 106 ms 23376 KB Output is correct
94 Correct 93 ms 23368 KB Output is correct
95 Correct 88 ms 23376 KB Output is correct
96 Correct 100 ms 23496 KB Output is correct
97 Correct 103 ms 23380 KB Output is correct
98 Correct 82 ms 22668 KB Output is correct
99 Correct 60 ms 22624 KB Output is correct
100 Correct 74 ms 22104 KB Output is correct
101 Correct 87 ms 23380 KB Output is correct
102 Correct 87 ms 23120 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12376 KB Output is correct
2 Correct 10 ms 12664 KB Output is correct
3 Correct 7 ms 12416 KB Output is correct
4 Correct 7 ms 12552 KB Output is correct
5 Correct 6 ms 12516 KB Output is correct
6 Correct 7 ms 12380 KB Output is correct
7 Correct 7 ms 12380 KB Output is correct
8 Correct 7 ms 12384 KB Output is correct
9 Correct 8 ms 12380 KB Output is correct
10 Correct 7 ms 12380 KB Output is correct
11 Correct 7 ms 12380 KB Output is correct
12 Correct 7 ms 12376 KB Output is correct
13 Correct 5 ms 12380 KB Output is correct
14 Correct 6 ms 12564 KB Output is correct
15 Correct 8 ms 12380 KB Output is correct
16 Correct 7 ms 12380 KB Output is correct
17 Correct 7 ms 12380 KB Output is correct
18 Correct 7 ms 12380 KB Output is correct
19 Correct 6 ms 12380 KB Output is correct
20 Correct 7 ms 12380 KB Output is correct
21 Correct 7 ms 12380 KB Output is correct
22 Correct 7 ms 12496 KB Output is correct
23 Correct 7 ms 12380 KB Output is correct
24 Correct 7 ms 12392 KB Output is correct
25 Correct 6 ms 12380 KB Output is correct
26 Correct 6 ms 12380 KB Output is correct
27 Correct 7 ms 12376 KB Output is correct
28 Correct 8 ms 12376 KB Output is correct
29 Correct 8 ms 12380 KB Output is correct
30 Correct 7 ms 12380 KB Output is correct
31 Correct 7 ms 12380 KB Output is correct
32 Correct 7 ms 12376 KB Output is correct
33 Correct 7 ms 12380 KB Output is correct
34 Correct 6 ms 12564 KB Output is correct
35 Correct 6 ms 12552 KB Output is correct
36 Correct 6 ms 12380 KB Output is correct
37 Correct 6 ms 12380 KB Output is correct
38 Correct 6 ms 12552 KB Output is correct
39 Correct 84 ms 23016 KB Output is correct
40 Correct 83 ms 23216 KB Output is correct
41 Correct 86 ms 23124 KB Output is correct
42 Correct 81 ms 23116 KB Output is correct
43 Correct 83 ms 23132 KB Output is correct
44 Correct 82 ms 23124 KB Output is correct
45 Correct 46 ms 21528 KB Output is correct
46 Correct 48 ms 21588 KB Output is correct
47 Correct 87 ms 23128 KB Output is correct
48 Correct 76 ms 23164 KB Output is correct
49 Correct 89 ms 23128 KB Output is correct
50 Correct 86 ms 23132 KB Output is correct
51 Correct 67 ms 22352 KB Output is correct
52 Correct 77 ms 22868 KB Output is correct
53 Correct 83 ms 23176 KB Output is correct
54 Correct 84 ms 23288 KB Output is correct
55 Correct 451 ms 54484 KB Output is correct
56 Correct 336 ms 50512 KB Output is correct
57 Correct 477 ms 56104 KB Output is correct
58 Correct 365 ms 50772 KB Output is correct
59 Correct 379 ms 50644 KB Output is correct
60 Correct 494 ms 56404 KB Output is correct
61 Correct 205 ms 50516 KB Output is correct
62 Correct 220 ms 50380 KB Output is correct
63 Correct 475 ms 55688 KB Output is correct
64 Correct 471 ms 55680 KB Output is correct
65 Correct 527 ms 55672 KB Output is correct
66 Correct 499 ms 56144 KB Output is correct
67 Correct 469 ms 55636 KB Output is correct
68 Correct 470 ms 56172 KB Output is correct
69 Correct 542 ms 56400 KB Output is correct
70 Correct 479 ms 56100 KB Output is correct
71 Correct 499 ms 56164 KB Output is correct
72 Correct 468 ms 55888 KB Output is correct
73 Correct 459 ms 56060 KB Output is correct
74 Correct 445 ms 55888 KB Output is correct
75 Correct 459 ms 56248 KB Output is correct
76 Correct 446 ms 56144 KB Output is correct
77 Correct 466 ms 56184 KB Output is correct
78 Correct 484 ms 56148 KB Output is correct
79 Correct 381 ms 55216 KB Output is correct
80 Correct 411 ms 55632 KB Output is correct
81 Correct 383 ms 54944 KB Output is correct
82 Correct 83 ms 22356 KB Output is correct
83 Correct 69 ms 22100 KB Output is correct
84 Correct 40 ms 21072 KB Output is correct
85 Correct 48 ms 21480 KB Output is correct
86 Correct 87 ms 22932 KB Output is correct
87 Correct 90 ms 23120 KB Output is correct
88 Correct 96 ms 23120 KB Output is correct
89 Correct 92 ms 22864 KB Output is correct
90 Correct 91 ms 23088 KB Output is correct
91 Correct 114 ms 22864 KB Output is correct
92 Correct 55 ms 22084 KB Output is correct
93 Correct 79 ms 22864 KB Output is correct
94 Correct 62 ms 21432 KB Output is correct
95 Correct 73 ms 22356 KB Output is correct
96 Correct 94 ms 23120 KB Output is correct
97 Correct 89 ms 23060 KB Output is correct
98 Correct 71 ms 22100 KB Output is correct
99 Correct 84 ms 23124 KB Output is correct
100 Correct 95 ms 22868 KB Output is correct
101 Correct 90 ms 23344 KB Output is correct
102 Correct 90 ms 23472 KB Output is correct
103 Correct 68 ms 21840 KB Output is correct
104 Correct 84 ms 22732 KB Output is correct
105 Correct 88 ms 23376 KB Output is correct
106 Correct 52 ms 21732 KB Output is correct
107 Correct 63 ms 21576 KB Output is correct
108 Correct 65 ms 22736 KB Output is correct
109 Correct 61 ms 21584 KB Output is correct
110 Correct 81 ms 23120 KB Output is correct
111 Correct 102 ms 23032 KB Output is correct
112 Correct 81 ms 22876 KB Output is correct
113 Correct 92 ms 23384 KB Output is correct
114 Correct 88 ms 22916 KB Output is correct
115 Correct 108 ms 23380 KB Output is correct
116 Correct 65 ms 21596 KB Output is correct
117 Correct 94 ms 23380 KB Output is correct
118 Correct 78 ms 22360 KB Output is correct
119 Correct 72 ms 22096 KB Output is correct
120 Correct 106 ms 23376 KB Output is correct
121 Correct 93 ms 23368 KB Output is correct
122 Correct 88 ms 23376 KB Output is correct
123 Correct 100 ms 23496 KB Output is correct
124 Correct 103 ms 23380 KB Output is correct
125 Correct 82 ms 22668 KB Output is correct
126 Correct 60 ms 22624 KB Output is correct
127 Correct 74 ms 22104 KB Output is correct
128 Correct 87 ms 23380 KB Output is correct
129 Correct 87 ms 23120 KB Output is correct
130 Correct 523 ms 55796 KB Output is correct
131 Correct 352 ms 50296 KB Output is correct
132 Correct 447 ms 55788 KB Output is correct
133 Correct 514 ms 55380 KB Output is correct
134 Correct 428 ms 53200 KB Output is correct
135 Correct 568 ms 56148 KB Output is correct
136 Correct 562 ms 55928 KB Output is correct
137 Correct 506 ms 55932 KB Output is correct
138 Correct 488 ms 55564 KB Output is correct
139 Correct 491 ms 56144 KB Output is correct
140 Correct 444 ms 54008 KB Output is correct
141 Correct 525 ms 54284 KB Output is correct
142 Correct 488 ms 54356 KB Output is correct
143 Correct 495 ms 54100 KB Output is correct
144 Correct 465 ms 54128 KB Output is correct
145 Correct 476 ms 54376 KB Output is correct
146 Correct 575 ms 54464 KB Output is correct
147 Correct 462 ms 54328 KB Output is correct
148 Correct 487 ms 54388 KB Output is correct
149 Correct 459 ms 54388 KB Output is correct
150 Correct 299 ms 50704 KB Output is correct
151 Correct 399 ms 53844 KB Output is correct
152 Correct 418 ms 53912 KB Output is correct
153 Correct 391 ms 53156 KB Output is correct