Submission #789622

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
789622	2023-07-21T15:03:53 Z	hugo_pm	Two Currencies (JOI23_currencies)	C++17	100 / 100	1184 ms	99388 KB

currencies

// Begin hl/core.hpp
#pragma once
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using v32 = vector<int>;
using v64 = vector<ll>;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
const int m197 = 1000000007;
const int m998 = 998244353;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)

template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }
template<typename T>
int len(const T &x) { return (int)(x.size()); }

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
	cout << ' ' << H;
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type
operator<<(Ostream& os,  const Cont& v){
	os << "[";
	for (auto &x : v) os << x << ", ";
	return os << "]";
}

template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p) {
	return os << "{" << p.first << ", " << p.second << "}";
}

template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
	static_assert(D >= 1, "Vector dimension must be greater than zero!");
	template<typename... Args>
		Vec(int n, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};

template<typename T>
struct Vec<1, T> : public vector<T> {
	Vec(int n, const T& val = T()) : vector<T>(n, val) {}
};

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

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

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

ll nxt() { ll x; cin >> x; return x; }
template<typename T>
vector<T> read_vector(int n) {
	vector<T> v(n);
	for (T &x : v) cin >> x;
	return v;
}
vector<int> rv32(int n) { return read_vector<int>(n); }
vector<ll> rv64(int n) { return read_vector<ll>(n); }

template<typename T>
void print_vector(vector<T> data, bool print_size, bool new_line) {
	int n = data.size();
	if (print_size) cout << n << '\n';
	for (int i = 0; i < n; ++i) cout << data[i] << " \n"[i+1 == n || new_line];
}

void fastio() {
	ios::sync_with_stdio(false), cin.tie(0);
}

vector<int> az_to_int(string s) {
	vector<int> ret(s.size());
	rep(i, 0, (int)s.size()) ret[i] = s[i] - 'a';
	return ret;
}
// End hl/core.hpp
// Begin hl/data/usual.hpp
#pragma once
// Begin hl/data/segtree.hpp
#pragma once
#include <vector>

template<class node, node (*op)(node, node), node (*e)()>
class segtree {
public:
	segtree(std::vector<node> v) : _n(v.size()), log(0) {
		while ((1 << log) < _n) {
			++log;
		}

		size = (1 << log);
		data.assign(2*size, e());

		for (int i = 0; i < _n; ++i) {
			data[size+i] = v[i];
		}

		for (int i = size-1; i >= 1; --i) {
			update(i);
		}
	}

	segtree(int t = 0, node x = e()) : segtree(std::vector<node>(t, x)) { }

	node get(int pos) {
		return data[size+pos];
	}

	void set(int pos, node val) {
		pos += size;
		data[pos] = val;
		for (int i = 1; i <= log; ++i) {
			update(pos >> i);
		}
	}

	void refresh(int pos, node proposal) {
		set(pos, op(data[size+pos], proposal));
	}

	node query_semi_open(int left, int right) {
		left += size;
		right += size;
		node res_left = e(), res_right = e(); 

		while (left < right) {
			if (left & 1) {
				res_left = op(res_left, data[left++]);
			}
			if (right & 1) {
				res_right = op(data[--right], res_right);
			}
			left >>= 1, right >>= 1;	
		}

		return op(res_left, res_right);
	}

	node query_all() {
		return data[1];
	}

private:
	int _n, log, size;
	std::vector<node> data;

	void update(int k) {
		data[k] = op(data[k<<1], data[k<<1|1]);
	}
};
// End hl/data/segtree.hpp
// Begin hl/data/lazy_segtree.hpp
#pragma once
#include <vector>
#include <cassert>

template<class node,
node (*op)(node, node),
node (*e)(),
class fun,
node (*eval)(fun, node),
fun (*composition)(fun, fun),
fun (*id)()>
class lazy_segtree {
public:
	lazy_segtree(std::vector<node> v) : _n(v.size()), log(0) {
		while ((1 << log) < _n) {
			++log;
		}

		size = (1 << log);
		data.assign(2*size, e());
		lazy.assign(size, id());

		for (int i = 0; i < _n; ++i) {
			data[size + i] = v[i];
		}

		for (int i = size-1; i >= 1; --i) {
			update_one(i);
		}
	}

	lazy_segtree(int t = 0, node x = e()) : lazy_segtree(std::vector<node>(t, x)) { }

	node get(int pos) {
		int leaf = pos + size;
		push_anc(leaf);
		return data[leaf];
	}

	void set(int pos, node val) {
		int leaf = pos + size;
		push_anc(leaf);
		data[leaf] = val;
		update_anc(leaf);
	}

	node query_semi_open(int left, int right) {
		left += size;
		right += size;
		node res_left = e(), res_right = e();

		push_anc(left, left);
		push_anc(right, right);

		while (left < right) {
			if (left & 1) {
				res_left = op(res_left, data[left++]);
			}
			if (right & 1) {
				res_right = op(data[--right], res_right);
			}
			left >>= 1;
			right >>= 1;	
		}

		return op(res_left, res_right);
	}

	node query_all() {
		return data[1];
	}

	void apply_one(int pos, fun fct) {
		int leaf = pos + size;
		push_anc(leaf);
		data[leaf] = eval(fct, data[leaf]);
		update_anc(leaf);
	}

	void apply_semi_open(int left, int right, fun fct) {
		left += size;
		right += size;

		if (left == right) {
			return;
		}

		push_anc(left, left);
		push_anc(right - 1, right);

		int old_left = left, old_right = right;
		while (left < right) {
			if (left & 1) {
				all_apply(left++, fct);
			}
			if (right & 1) {
				all_apply(--right, fct);
			}
			left >>= 1;
			right >>= 1;
		}

		left = old_left, right = old_right;
		update_anc(left, left);
		update_anc(right - 1, right);
	}

private:
	int _n, log, size;
	std::vector<node> data;
	std::vector<fun> lazy;

	void update_one(int k) {
		data[k] = op(data[k << 1], data[k << 1 | 1]);
	}

	void update_anc(int leaf, int dev = 1) {
		int s = 1 + __builtin_ctz(dev);
		for (int i = s; i <= log; ++i) {
			update_one(leaf >> i);
		}
	}

	void all_apply(int k, fun fct) {
		data[k] = eval(fct, data[k]);
		if (k < size) {
			lazy[k] = composition(fct, lazy[k]);
		}
	}

	void push_one(int k) {
		all_apply(k << 1, lazy[k]);
		all_apply(k << 1 | 1, lazy[k]);
		lazy[k] = id();
	}

	void push_anc(int leaf, int dev = 1) {
		int s = 1 + __builtin_ctz(dev);
		for (int i = log; i >= s; --i) {
			push_one(leaf >> i);
		}
	}
};
// End hl/data/lazy_segtree.hpp
#include <optional>
using ll = long long;

template<typename T, const T BIG_>
struct numeric_segtree {
	static constexpr T BIG = BIG_;
	static T fct_sum(T a, T b) { return a + b; }
	static T e_sum() { return 0; }

	static T fct_min(T a, T b) { return (a < b ? a : b); }
	static T e_min() { return BIG; }

	static T fct_max(T a, T b) { return (a > b ? a : b); }
	static T e_max() { return -BIG; }

	using segtree_min = segtree<T, fct_min, e_min>;
	using segtree_max = segtree<T, fct_max, e_max>;
	using segtree_sum = segtree<T, fct_sum, e_sum>;

	using lazy_min_add = lazy_segtree<T, fct_min, e_min, T, fct_sum, fct_sum, e_sum>;
	using lazy_max_add = lazy_segtree<T, fct_max, e_max, T, fct_sum, fct_sum, e_sum>;
	using lazy_sum_add = lazy_segtree<T, fct_sum, e_sum, T, fct_sum, fct_sum, e_sum>;

	using set_struct = std::optional<T>;
	static set_struct comp_set(set_struct f1, set_struct f2) {
		return (f1 ? f1 : f2);
	}
	static T eval_set(set_struct fct, T val) {
		return (fct ? *fct : val);
	}
	static set_struct e_set() {
		return std::nullopt;
	}

	using lazy_min_set = lazy_segtree<T, fct_min, e_min, set_struct, eval_set, comp_set, e_set>;
	using lazy_max_set = lazy_segtree<T, fct_max, e_max, set_struct, eval_set, comp_set, e_set>;
	using lazy_sum_set = lazy_segtree<T, fct_sum, e_sum, set_struct, eval_set, comp_set, e_set>;
};

using usual32 = numeric_segtree<int, (int)1e9>;
using usual64 = numeric_segtree<long long, (ll)3e18>;

// End hl/data/usual.hpp
#define int long long

using pii = pair<int, int>;
using vi = vector<int>;
const int INF = 3e18;
pii opmin(pii a, pii b) {
    return min(a, b);
}
pii e_min() { return {INF, -1}; }
using SegSum = usual64::segtree_sum;
using SegMin = segtree<pii, opmin, e_min>;

struct PathSumEdge {
	vector<vi> adj;
	int N;
	int ordCnt = 0;
	vector<pii> begEnd;
	vector<pii> passages;
	vector<int> firstPass;
	vector<int> depth;
	SegMin lca_tree;
	SegSum sum_tree;

	void dfs(int node, int anc) {
		begEnd[node].first = ordCnt++;
		firstPass[node]= passages.size();
		passages.emplace_back(depth[node], node);
		for(auto voisin : adj[node]) if (voisin != anc) {
			depth[voisin] = depth[node]+1;
			dfs(voisin, node);
			passages.emplace_back(depth[node], node);
		}
		begEnd[node].second = ordCnt++;
	}

	void resetSum() {
		sum_tree = SegSum(2*N, 0);
	}

	PathSumEdge(int _N, vector<vi> _adj) :
	adj(_adj), N(_N), begEnd(_N), firstPass(_N), depth(_N) {
		assert(N == (int)adj.size());
		dfs(0, -1);
		lca_tree = SegMin(passages);
		resetSum();
	}

	void edgeAdd(int u, int v, int delta) {
		if (depth[u] > depth[v]) swap(u, v);
		// u parent, v child
		sum_tree.refresh(begEnd[v].first, delta);
		sum_tree.refresh(begEnd[v].second, -delta);
	}

	int getLca(int u, int v) {
		if(firstPass[u] > firstPass[v]){
			swap(u, v);
		}
		return lca_tree.query_semi_open(firstPass[u], firstPass[v]+1).second;
	}
	int edgePathSum(int u, int v, int lca) {
		int res = 0;
		// (lca, u/v]
		for (int x : {u, v})
			res += sum_tree.query_semi_open(begEnd[lca].first+1, begEnd[x].first+1);
		return res;
	}
};

struct Query {
	// gold = initial - tout
	int S, T, gold, silver;
	int lca = -1;
	// [lo, hi] : seuil
	int lo, hi;
};
signed main() {
	fastio();
	int nbNode = nxt(), nbChk = nxt(), nbReq = nxt();
	vector<vi> adj(nbNode);
	vector<pii> edges;
	rep(iEdge, 0, nbNode-1) {
		int u = nxt()-1, v = nxt()-1;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.emplace_back(u, v);
	}
	PathSumEdge ps(nbNode, adj);
	vector<pair<int, pii>> checkpoints;
	rep(iChk, 0, nbChk) {
		int iEdge = nxt()-1, bonus = nxt();
		checkpoints.emplace_back(bonus, edges[iEdge]);
		// calcul nombre de chk
		ps.edgeAdd(edges[iEdge].first, edges[iEdge].second, 1);
	}
	sort(all(checkpoints));
	vector<Query> queries(nbReq);
	vector<vector<int>> done(nbChk+1);
	int nbDone = 0;
	vector<vector<int>> _empty(nbChk+1);
	auto todo = _empty;
	rep(iReq, 0, nbReq) {
		Query &r = queries[iReq];
		cin >> r.S >> r.T >> r.gold >> r.silver;
		--r.S; --r.T;
		r.lca = ps.getLca(r.S, r.T);
		r.gold -= ps.edgePathSum(r.S, r.T, r.lca);
		r.lo = 0, r.hi = nbChk;
		if (r.lo == r.hi) {
			done[r.lo+(r.hi-r.lo+1)/2].push_back(iReq); ++nbDone;
		} else {
			todo[r.lo+(r.hi-r.lo+1)/2].push_back(iReq);
		}
	}
	vector<vector<int>> old;
	while (nbDone < nbReq) {
		old = todo;
		todo = _empty;
		ps.resetSum();
		rep(taken, 1, nbChk+1) {
			auto [bonus, edge] = checkpoints[taken-1];
			auto [u, v] = edge;
			ps.edgeAdd(u, v, bonus);
			for (int iReq : old[taken]) {
				Query &r = queries[iReq];
				if (r.silver < ps.edgePathSum(r.S, r.T, r.lca)) {
					r.hi = taken-1;
				} else {
					r.lo = taken;
				}
				if (r.lo == r.hi) {
					done[r.lo+(r.hi-r.lo+1)/2].push_back(iReq); ++nbDone;
				} else {
					todo[r.lo+(r.hi-r.lo+1)/2].push_back(iReq);
				}
			}
		}
	}
	vector<int> answers(nbReq);
	ps.resetSum();
	rep(taken, 0, nbChk+1) {
		for (int iReq : done[taken]) {
			const Query &r = queries[iReq];
			answers[iReq] = max(-1LL, r.gold + ps.edgePathSum(r.S, r.T, r.lca));
		}
		if (taken < nbChk) {
			auto [u, v] = checkpoints[taken].second;
			ps.edgeAdd(u, v, 1);
		}
	}
	rep(iReq, 0, nbReq) {
		cout << answers[iReq] << '\n';
	}
}

Compilation message

currencies.cpp:2:9: warning: #pragma once in main file
    2 | #pragma once
      |         ^~~~
currencies.cpp:109:9: warning: #pragma once in main file
  109 | #pragma once
      |         ^~~~
currencies.cpp:111:9: warning: #pragma once in main file
  111 | #pragma once
      |         ^~~~
currencies.cpp:184:9: warning: #pragma once in main file
  184 | #pragma once
      |         ^~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	6 ms	1608 KB	Output is correct
6	Correct	11 ms	1876 KB	Output is correct
7	Correct	7 ms	1592 KB	Output is correct
8	Correct	8 ms	1876 KB	Output is correct
9	Correct	12 ms	1864 KB	Output is correct
10	Correct	9 ms	1860 KB	Output is correct
11	Correct	9 ms	1956 KB	Output is correct
12	Correct	12 ms	2004 KB	Output is correct
13	Correct	8 ms	2004 KB	Output is correct
14	Correct	8 ms	2040 KB	Output is correct
15	Correct	8 ms	2024 KB	Output is correct
16	Correct	11 ms	1912 KB	Output is correct
17	Correct	10 ms	2004 KB	Output is correct
18	Correct	9 ms	2000 KB	Output is correct
19	Correct	8 ms	2004 KB	Output is correct
20	Correct	8 ms	1984 KB	Output is correct
21	Correct	11 ms	1876 KB	Output is correct
22	Correct	8 ms	1964 KB	Output is correct
23	Correct	7 ms	1876 KB	Output is correct
24	Correct	8 ms	1992 KB	Output is correct
25	Correct	8 ms	1960 KB	Output is correct
26	Correct	8 ms	1876 KB	Output is correct
27	Correct	5 ms	1876 KB	Output is correct
28	Correct	6 ms	1876 KB	Output is correct
29	Correct	6 ms	1784 KB	Output is correct
30	Correct	12 ms	1900 KB	Output is correct
31	Correct	9 ms	1948 KB	Output is correct
32	Correct	11 ms	1972 KB	Output is correct
33	Correct	7 ms	2004 KB	Output is correct
34	Correct	7 ms	2004 KB	Output is correct
35	Correct	8 ms	2072 KB	Output is correct

Subtask #2

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	9 ms	1888 KB	Output is correct
3	Correct	9 ms	1876 KB	Output is correct
4	Correct	8 ms	1876 KB	Output is correct
5	Correct	750 ms	75140 KB	Output is correct
6	Correct	831 ms	87264 KB	Output is correct
7	Correct	845 ms	79460 KB	Output is correct
8	Correct	641 ms	70544 KB	Output is correct
9	Correct	666 ms	72084 KB	Output is correct
10	Correct	1028 ms	95864 KB	Output is correct
11	Correct	1004 ms	95500 KB	Output is correct
12	Correct	1127 ms	95632 KB	Output is correct
13	Correct	1073 ms	93036 KB	Output is correct
14	Correct	1006 ms	95688 KB	Output is correct
15	Correct	939 ms	98528 KB	Output is correct
16	Correct	894 ms	99004 KB	Output is correct
17	Correct	986 ms	98160 KB	Output is correct
18	Correct	1112 ms	92116 KB	Output is correct
19	Correct	1092 ms	92000 KB	Output is correct
20	Correct	1125 ms	94604 KB	Output is correct
21	Correct	862 ms	94492 KB	Output is correct
22	Correct	872 ms	94348 KB	Output is correct
23	Correct	877 ms	94472 KB	Output is correct
24	Correct	884 ms	94484 KB	Output is correct
25	Correct	802 ms	92540 KB	Output is correct
26	Correct	816 ms	92528 KB	Output is correct
27	Correct	842 ms	91364 KB	Output is correct
28	Correct	600 ms	93992 KB	Output is correct
29	Correct	515 ms	93052 KB	Output is correct
30	Correct	618 ms	89620 KB	Output is correct
31	Correct	654 ms	89652 KB	Output is correct

Subtask #3

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	8 ms	2008 KB	Output is correct
3	Correct	7 ms	2004 KB	Output is correct
4	Correct	8 ms	2004 KB	Output is correct
5	Correct	580 ms	83056 KB	Output is correct
6	Correct	605 ms	77912 KB	Output is correct
7	Correct	660 ms	71760 KB	Output is correct
8	Correct	1000 ms	99148 KB	Output is correct
9	Correct	923 ms	99168 KB	Output is correct
10	Correct	929 ms	99044 KB	Output is correct
11	Correct	776 ms	99240 KB	Output is correct
12	Correct	802 ms	99144 KB	Output is correct
13	Correct	830 ms	99124 KB	Output is correct
14	Correct	689 ms	99388 KB	Output is correct
15	Correct	725 ms	96580 KB	Output is correct
16	Correct	677 ms	99140 KB	Output is correct
17	Correct	716 ms	99144 KB	Output is correct

Subtask #4

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	6 ms	1608 KB	Output is correct
6	Correct	11 ms	1876 KB	Output is correct
7	Correct	7 ms	1592 KB	Output is correct
8	Correct	8 ms	1876 KB	Output is correct
9	Correct	12 ms	1864 KB	Output is correct
10	Correct	9 ms	1860 KB	Output is correct
11	Correct	9 ms	1956 KB	Output is correct
12	Correct	12 ms	2004 KB	Output is correct
13	Correct	8 ms	2004 KB	Output is correct
14	Correct	8 ms	2040 KB	Output is correct
15	Correct	8 ms	2024 KB	Output is correct
16	Correct	11 ms	1912 KB	Output is correct
17	Correct	10 ms	2004 KB	Output is correct
18	Correct	9 ms	2000 KB	Output is correct
19	Correct	8 ms	2004 KB	Output is correct
20	Correct	8 ms	1984 KB	Output is correct
21	Correct	11 ms	1876 KB	Output is correct
22	Correct	8 ms	1964 KB	Output is correct
23	Correct	7 ms	1876 KB	Output is correct
24	Correct	8 ms	1992 KB	Output is correct
25	Correct	8 ms	1960 KB	Output is correct
26	Correct	8 ms	1876 KB	Output is correct
27	Correct	5 ms	1876 KB	Output is correct
28	Correct	6 ms	1876 KB	Output is correct
29	Correct	6 ms	1784 KB	Output is correct
30	Correct	12 ms	1900 KB	Output is correct
31	Correct	9 ms	1948 KB	Output is correct
32	Correct	11 ms	1972 KB	Output is correct
33	Correct	7 ms	2004 KB	Output is correct
34	Correct	7 ms	2004 KB	Output is correct
35	Correct	8 ms	2072 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	9 ms	1888 KB	Output is correct
38	Correct	9 ms	1876 KB	Output is correct
39	Correct	8 ms	1876 KB	Output is correct
40	Correct	750 ms	75140 KB	Output is correct
41	Correct	831 ms	87264 KB	Output is correct
42	Correct	845 ms	79460 KB	Output is correct
43	Correct	641 ms	70544 KB	Output is correct
44	Correct	666 ms	72084 KB	Output is correct
45	Correct	1028 ms	95864 KB	Output is correct
46	Correct	1004 ms	95500 KB	Output is correct
47	Correct	1127 ms	95632 KB	Output is correct
48	Correct	1073 ms	93036 KB	Output is correct
49	Correct	1006 ms	95688 KB	Output is correct
50	Correct	939 ms	98528 KB	Output is correct
51	Correct	894 ms	99004 KB	Output is correct
52	Correct	986 ms	98160 KB	Output is correct
53	Correct	1112 ms	92116 KB	Output is correct
54	Correct	1092 ms	92000 KB	Output is correct
55	Correct	1125 ms	94604 KB	Output is correct
56	Correct	862 ms	94492 KB	Output is correct
57	Correct	872 ms	94348 KB	Output is correct
58	Correct	877 ms	94472 KB	Output is correct
59	Correct	884 ms	94484 KB	Output is correct
60	Correct	802 ms	92540 KB	Output is correct
61	Correct	816 ms	92528 KB	Output is correct
62	Correct	842 ms	91364 KB	Output is correct
63	Correct	600 ms	93992 KB	Output is correct
64	Correct	515 ms	93052 KB	Output is correct
65	Correct	618 ms	89620 KB	Output is correct
66	Correct	654 ms	89652 KB	Output is correct
67	Correct	1 ms	212 KB	Output is correct
68	Correct	8 ms	2008 KB	Output is correct
69	Correct	7 ms	2004 KB	Output is correct
70	Correct	8 ms	2004 KB	Output is correct
71	Correct	580 ms	83056 KB	Output is correct
72	Correct	605 ms	77912 KB	Output is correct
73	Correct	660 ms	71760 KB	Output is correct
74	Correct	1000 ms	99148 KB	Output is correct
75	Correct	923 ms	99168 KB	Output is correct
76	Correct	929 ms	99044 KB	Output is correct
77	Correct	776 ms	99240 KB	Output is correct
78	Correct	802 ms	99144 KB	Output is correct
79	Correct	830 ms	99124 KB	Output is correct
80	Correct	689 ms	99388 KB	Output is correct
81	Correct	725 ms	96580 KB	Output is correct
82	Correct	677 ms	99140 KB	Output is correct
83	Correct	716 ms	99144 KB	Output is correct
84	Correct	729 ms	73872 KB	Output is correct
85	Correct	673 ms	61660 KB	Output is correct
86	Correct	629 ms	59492 KB	Output is correct
87	Correct	1149 ms	95548 KB	Output is correct
88	Correct	1110 ms	91412 KB	Output is correct
89	Correct	1157 ms	93004 KB	Output is correct
90	Correct	1184 ms	93032 KB	Output is correct
91	Correct	1121 ms	95540 KB	Output is correct
92	Correct	952 ms	96028 KB	Output is correct
93	Correct	953 ms	97688 KB	Output is correct
94	Correct	1168 ms	91888 KB	Output is correct
95	Correct	1130 ms	91868 KB	Output is correct
96	Correct	1105 ms	91852 KB	Output is correct
97	Correct	1112 ms	91944 KB	Output is correct
98	Correct	1033 ms	93948 KB	Output is correct
99	Correct	960 ms	93484 KB	Output is correct
100	Correct	940 ms	93908 KB	Output is correct
101	Correct	1002 ms	94056 KB	Output is correct
102	Correct	913 ms	96012 KB	Output is correct
103	Correct	853 ms	93400 KB	Output is correct
104	Correct	927 ms	93364 KB	Output is correct
105	Correct	686 ms	87444 KB	Output is correct
106	Correct	613 ms	92916 KB	Output is correct
107	Correct	637 ms	88276 KB	Output is correct
108	Correct	657 ms	88372 KB	Output is correct