답안 #84171 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
84171	2018-11-13T20:39:03 Z	radoslav11	새 집 (APIO18_new_home)	C++14	47 / 100	5000 ms	317868 KB

new_home

/*
   We will use sweep line to solve the problem. We split the stores into 2 queries: 
   1) Add store i at time a[i]
   2) Remove store i at time b[i] + 1
   We will also have queries in the sweep line. Everything will be sorted by time in increasing order.

   Now to handle queries we will maintain K sets - the available positions of j-type stores. Then if A and B are two consecutive stores, the closest elements to all positions in [A; B] are A or B.
   Then let's have a two segment trees wtih sets - one for closest elements to the left and one for closest elements to the right. Now addition of store with type X will be done like that:

   1) Let A <= X <= B and A and B are the closest stores of the same type. 
   2) We remove the interval [A; B] from the DS.
   3) We add the intervals [A; X] and [X; B].

   Adding or removing an interval is done by finding the middle position and then concidering the two ranges - [L; Mid] and [Mid + 1; R].

   The complexity will be O(N * log N * log N).

   As sets are slow, we will compress the input in each segment tree node beforehand and then use priority queue instead of sets.

   Unfortunately the above data structure was too slow. So my second idea is to change the data structure to two simple treaps and do binary search on them. 
   The complexity will be O(N log N) this way. 

   Again unfortunately the treap solution was too slow (it got 47). So the third idea is to make the data structure offline. Then the treap can be replaced with segment tree.
   */

#include <bits/stdc++.h>
#define endl '\n'

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 21);
const int inf = (int)1e9 + 42;

vector<pair<int, int> > Li;

struct segment_tree_L
{
	vector<pair<int, int> > a;

	struct node
	{
		int mx;
		node() { mx = -inf; }
		node(int val) { mx = val; }
	};

	node temp, broken;

	node merge(node l, node r)
	{
		temp.mx = max(l.mx, r.mx);
		return temp;
	}

	int bound_L[4 * MAXN], bound_R[4 * MAXN];

	node tr[4 * MAXN];
	int CNT[MAXN];

	void init(int l, int r, int idx)
	{
		bound_L[idx] = l;
		bound_R[idx] = r;
		if(l == r)
		{
			CNT[l] = 0;
			tr[idx] = node();
			return;
		}

		int mid = (l + r) >> 1;
		init(l, mid, 2 * idx + 1);
		init(mid + 1, r, 2 * idx + 2);

		tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
	}

	void add(int pos, int l, int r, int idx)
	{
		if(l > pos || r < pos)
			return;

		if(l == r && l == pos)
		{
			CNT[l]++;
			tr[idx].mx = CNT[l] ? a[l].second : -inf;
			return;
		}

		int mid = (l + r) >> 1;
		add(pos, l, mid, 2 * idx + 1);
		add(pos, mid + 1, r, 2 * idx + 2);

		tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
	}
	
	void rem(int pos, int l, int r, int idx)
	{
		if(l > pos || r < pos)
			return;

		if(l == r && l == pos)
		{
			CNT[l]--;
			tr[idx].mx = CNT[l] ? a[l].second : -inf;
			return;
		}

		int mid = (l + r) >> 1;
		rem(pos, l, mid, 2 * idx + 1);
		rem(pos, mid + 1, r, 2 * idx + 2);

		tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
	}

	void get_nodes(int qL, int qR, int l, int r, int idx, vector<int> &li)
	{
		if(l > qR || r < qL) return;
		if(qL <= l && r <= qR)
		{
			li.push_back(idx);
			return;
		}

		int mid = (l + r) >> 1;
		get_nodes(qL, qR, l, mid, 2 * idx + 1, li);
		get_nodes(qL, qR, mid + 1, r, 2 * idx + 2, li);
	}

	int get_right(int l, int r, int idx, int X)
	{
		if(l == r) return l;
		int mid = (l + r) >> 1;
		if(tr[2 * idx + 1].mx >= X) return get_right(l, mid, 2 * idx + 1, X);
		else return get_right(mid + 1, r, 2 * idx + 2, X);
	}

	int N;

	void init()
	{
		N = SZ(Li);
		a = Li;
		init(0, N - 1, 0);
	}

	void add_interval(int l, int r)
	{
		int pos = L_B(ALL(a), make_pair(l, r)) - a.begin();
		add(pos, 0, N - 1, 0);
	}

	void rem_interval(int l, int r)
	{
		int pos = L_B(ALL(a), make_pair(l, r)) - a.begin();
		rem(pos, 0, N - 1, 0);
	}

	int query(int x)
	{
		vector<int> li;
		int Ren = L_B(ALL(a), make_pair(x, 10 + inf)) - a.begin() - 1; 
		get_nodes(0, Ren, 0, N - 1, 0, li);

		for(auto it: li)
			if(tr[it].mx >= x)
				return x - a[get_right(bound_L[it], bound_R[it], it, x)].first;

		return -inf;
	}

} L;

struct segment_tree_R
{
	vector<pair<int, int> > a;

	struct node
	{
		int mn;
		node() { mn = inf; }
		node(int val) { mn = val; }
	};

	node temp, broken;

	node merge(node l, node r)
	{
		temp.mn = min(l.mn, r.mn);
		return temp;
	}

	int bound_L[4 * MAXN], bound_R[4 * MAXN];

	node tr[4 * MAXN];
	int CNT[MAXN];

	void init(int l, int r, int idx)
	{
		bound_L[idx] = l;
		bound_R[idx] = r;
		if(l == r)
		{
			CNT[l] = 0;
			tr[idx] = node();
			return;
		}

		int mid = (l + r) >> 1;
		init(l, mid, 2 * idx + 1);
		init(mid + 1, r, 2 * idx + 2);

		tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
	}

	void add(int pos, int l, int r, int idx)
	{
		if(l > pos || r < pos)
			return;

		if(l == r && l == pos)
		{
			CNT[l]++;
			tr[idx].mn = CNT[l] ? a[l].second : inf;
			return;
		}

		int mid = (l + r) >> 1;
		add(pos, l, mid, 2 * idx + 1);
		add(pos, mid + 1, r, 2 * idx + 2);

		tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
	}
	
	void rem(int pos, int l, int r, int idx)
	{
		if(l > pos || r < pos)
			return;

		if(l == r && l == pos)
		{
			CNT[l]--;
			tr[idx].mn = CNT[l] ? a[l].second : inf;
			return;
		}

		int mid = (l + r) >> 1;
		rem(pos, l, mid, 2 * idx + 1);
		rem(pos, mid + 1, r, 2 * idx + 2);

		tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
	}

	void get_nodes(int qL, int qR, int l, int r, int idx, vector<int> &li)
	{
		if(l > qR || r < qL) return;
		if(qL <= l && r <= qR)
		{
			li.push_back(idx);
			return;
		}

		int mid = (l + r) >> 1;
		get_nodes(qL, qR, l, mid, 2 * idx + 1, li);
		get_nodes(qL, qR, mid + 1, r, 2 * idx + 2, li);
	}

	int get_left(int l, int r, int idx, int X)
	{
		if(l == r) return l;
		int mid = (l + r) >> 1;
		if(tr[2 * idx + 2].mn <= X) return get_left(mid + 1, r, 2 * idx + 2, X);
		else return get_left(l, mid, 2 * idx + 1, X);
	}

	int N;

	void init()
	{
		N = SZ(Li);
		a = Li;
		
		for(auto &it: a) swap(it.first, it.second);

		sort(ALL(a));

		init(0, N - 1, 0);
	}

	void add_interval(int l, int r)
	{
		int pos = L_B(ALL(a), make_pair(r, l)) - a.begin();
		add(pos, 0, N - 1, 0);
	}

	void rem_interval(int l, int r)
	{
		int pos = L_B(ALL(a), make_pair(r, l)) - a.begin();
		rem(pos, 0, N - 1, 0);
	}

	int query(int x)
	{
		vector<int> li;
		int Lst = L_B(ALL(a), make_pair(x, -inf - 10)) - a.begin(); 
		get_nodes(Lst, N - 1, 0, N - 1, 0, li);

		reverse(li.begin(), li.end());
		for(auto it: li)
			if(tr[it].mn <= x)
				return a[get_left(bound_L[it], bound_R[it], it, x)].first - x;

		return -inf;
	}

} R;

int read_int();

int n, k, q;

struct event
{
	int type;
	int T, x, tp, idx;

	event() { type = tp = T = x = 0; idx = -1; }
	event(int t, int Tm, int X, int i, int pp = -1)
	{
		type = t;
		T = Tm;
		x = X;
		idx = i;
		tp = pp;
	}
};

bool cmp(event a, event b) 
{ 
	if(a.T != b.T) return a.T < b.T; 
	return a.type < b.type;
}

vector<event> Ev;
int answer[MAXN];

void read()
{
	n = read_int();
	k = read_int();
	q = read_int();

	for(int i = 0; i < n; i++)
	{
		int x, t, a, b;
		x = read_int();
		t = read_int();
		a = read_int();
		b = read_int();

		Ev.push_back(event(0, a, x, i, t));
		Ev.push_back(event(1, b + 1, x, i, t));
	}

	for(int i = 0; i < q; i++)
	{
		int x, t;
		x = read_int();
		t = read_int();
		Ev.push_back(event(2, t, x, i));
	}
}

set<pair<int, int> > ST[MAXN];

void add_interval(int l, int r)
{
	int mid = (l + r) / 2;
	if(l <= mid) L.add_interval(l, mid);
	if(mid + 1 <= r) R.add_interval(mid + 1, r);
}

void rem_interval(int l, int r)
{
	int mid = (l + r) / 2;
	if(l <= mid) L.rem_interval(l, mid);
	if(mid + 1 <= r) R.rem_interval(mid + 1, r);
}

int query(int x) { return max(L.query(x), R.query(x)); }

void add(int y, int x, int i)
{
	auto aft = ST[y].L_B({x, i});
	auto bef = prev(aft);

	ST[y].insert({x, i});

	rem_interval(bef->first, aft->first);
	add_interval(bef->first, x);
	add_interval(x, aft->first);
}

void rem(int y, int x, int i)
{
	ST[y].erase({x, i});

	auto aft = ST[y].L_B({x, i});
	auto bef = prev(aft);

	rem_interval(bef->first, x);
	rem_interval(x, aft->first);
	add_interval(bef->first, aft->first);
}

void prep_add_interval(int l, int r)
{
	int mid = (l + r) / 2;
	if(l <= mid) Li.push_back({l, mid});
	if(mid + 1 <= r) Li.push_back({mid + 1, r});
}

void prep_add(int y, int x, int i)
{
	auto aft = ST[y].L_B({x, i});
	auto bef = prev(aft);

	ST[y].insert({x, i});

	prep_add_interval(bef->first, x);
	prep_add_interval(x, aft->first);
}

void prep_rem(int y, int x, int i)
{
	ST[y].erase({x, i});

	auto aft = ST[y].L_B({x, i});
	auto bef = prev(aft);

	prep_add_interval(bef->first, aft->first);
}

void solve()
{
	for(int i = 1; i <= k; i++)
		ST[i].insert({-inf, -1}), ST[i].insert({inf, -1});
	
	prep_add_interval(-inf, inf);

	sort(ALL(Ev), cmp);
	
	for(auto it: Ev)
		if(it.type == 0)
			prep_add(it.tp, it.x, it.idx);
		else if(it.type == 1)
			prep_rem(it.tp, it.x, it.idx);

	sort(ALL(Li));
	Li.erase(unique(ALL(Li)), Li.end());
	
	L.init();
	R.init();
	
	for(int i = 0; i < k; i++)
		add_interval(-inf, inf);

	for(auto it: Ev)
		if(it.type == 0)
			add(it.tp, it.x, it.idx);
		else if(it.type == 1)
			rem(it.tp, it.x, it.idx);
		else 
			answer[it.idx] = query(it.x);

	for(int i = 0; i < q; i++)
		if(answer[i] < (int)2e8) cout << answer[i] << endl;
		else cout << -1 << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	read();
	solve();
	return 0;
}

const int maxl = 100000;
char buff[maxl];
int ret_int, pos_buff = 0;

void next_char() { if(++pos_buff == maxl) fread(buff, 1, maxl, stdin), pos_buff = 0; }

int read_int()
{
	ret_int = 0;
	for(; buff[pos_buff] < '0' || buff[pos_buff] > '9'; next_char());
	for(; buff[pos_buff] >= '0' && buff[pos_buff] <= '9'; next_char())
		ret_int = ret_int * 10 + buff[pos_buff] - '0';
	return ret_int;
}

Compilation message

new_home.cpp: In function 'void next_char()':
new_home.cpp:504:70: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void next_char() { if(++pos_buff == maxl) fread(buff, 1, maxl, stdin), pos_buff = 0; }
                                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	145 ms	164728 KB	Output is correct
2	Correct	140 ms	164728 KB	Output is correct
3	Correct	147 ms	164728 KB	Output is correct
4	Correct	137 ms	164728 KB	Output is correct
5	Correct	143 ms	164908 KB	Output is correct
6	Correct	145 ms	165112 KB	Output is correct
7	Correct	153 ms	165112 KB	Output is correct
8	Correct	148 ms	165112 KB	Output is correct
9	Correct	145 ms	165112 KB	Output is correct
10	Correct	144 ms	165112 KB	Output is correct
11	Correct	143 ms	165112 KB	Output is correct
12	Correct	146 ms	165112 KB	Output is correct
13	Correct	141 ms	165112 KB	Output is correct
14	Correct	147 ms	165112 KB	Output is correct
15	Correct	144 ms	165112 KB	Output is correct
16	Correct	147 ms	165112 KB	Output is correct
17	Correct	146 ms	165112 KB	Output is correct
18	Correct	138 ms	165112 KB	Output is correct
19	Correct	140 ms	165136 KB	Output is correct
20	Correct	149 ms	165136 KB	Output is correct
21	Correct	138 ms	165136 KB	Output is correct
22	Correct	148 ms	165136 KB	Output is correct
23	Correct	143 ms	165136 KB	Output is correct
24	Correct	143 ms	165136 KB	Output is correct
25	Correct	151 ms	165136 KB	Output is correct
26	Correct	146 ms	165136 KB	Output is correct
27	Correct	146 ms	165136 KB	Output is correct
28	Correct	149 ms	165208 KB	Output is correct
29	Correct	147 ms	165208 KB	Output is correct
30	Correct	146 ms	165208 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	145 ms	164728 KB	Output is correct
2	Correct	140 ms	164728 KB	Output is correct
3	Correct	147 ms	164728 KB	Output is correct
4	Correct	137 ms	164728 KB	Output is correct
5	Correct	143 ms	164908 KB	Output is correct
6	Correct	145 ms	165112 KB	Output is correct
7	Correct	153 ms	165112 KB	Output is correct
8	Correct	148 ms	165112 KB	Output is correct
9	Correct	145 ms	165112 KB	Output is correct
10	Correct	144 ms	165112 KB	Output is correct
11	Correct	143 ms	165112 KB	Output is correct
12	Correct	146 ms	165112 KB	Output is correct
13	Correct	141 ms	165112 KB	Output is correct
14	Correct	147 ms	165112 KB	Output is correct
15	Correct	144 ms	165112 KB	Output is correct
16	Correct	147 ms	165112 KB	Output is correct
17	Correct	146 ms	165112 KB	Output is correct
18	Correct	138 ms	165112 KB	Output is correct
19	Correct	140 ms	165136 KB	Output is correct
20	Correct	149 ms	165136 KB	Output is correct
21	Correct	138 ms	165136 KB	Output is correct
22	Correct	148 ms	165136 KB	Output is correct
23	Correct	143 ms	165136 KB	Output is correct
24	Correct	143 ms	165136 KB	Output is correct
25	Correct	151 ms	165136 KB	Output is correct
26	Correct	146 ms	165136 KB	Output is correct
27	Correct	146 ms	165136 KB	Output is correct
28	Correct	149 ms	165208 KB	Output is correct
29	Correct	147 ms	165208 KB	Output is correct
30	Correct	146 ms	165208 KB	Output is correct
31	Correct	996 ms	199232 KB	Output is correct
32	Correct	349 ms	199232 KB	Output is correct
33	Correct	984 ms	199232 KB	Output is correct
34	Correct	960 ms	199232 KB	Output is correct
35	Correct	1002 ms	199260 KB	Output is correct
36	Correct	997 ms	199260 KB	Output is correct
37	Correct	783 ms	199260 KB	Output is correct
38	Correct	781 ms	199260 KB	Output is correct
39	Correct	665 ms	199260 KB	Output is correct
40	Correct	707 ms	199260 KB	Output is correct
41	Correct	841 ms	199260 KB	Output is correct
42	Correct	850 ms	199260 KB	Output is correct
43	Correct	244 ms	199260 KB	Output is correct
44	Correct	854 ms	199260 KB	Output is correct
45	Correct	829 ms	199260 KB	Output is correct
46	Correct	809 ms	199260 KB	Output is correct
47	Correct	551 ms	199260 KB	Output is correct
48	Correct	564 ms	199260 KB	Output is correct
49	Correct	596 ms	199260 KB	Output is correct
50	Correct	627 ms	199260 KB	Output is correct
51	Correct	634 ms	199260 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5109 ms	316300 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5037 ms	317868 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	145 ms	164728 KB	Output is correct
2	Correct	140 ms	164728 KB	Output is correct
3	Correct	147 ms	164728 KB	Output is correct
4	Correct	137 ms	164728 KB	Output is correct
5	Correct	143 ms	164908 KB	Output is correct
6	Correct	145 ms	165112 KB	Output is correct
7	Correct	153 ms	165112 KB	Output is correct
8	Correct	148 ms	165112 KB	Output is correct
9	Correct	145 ms	165112 KB	Output is correct
10	Correct	144 ms	165112 KB	Output is correct
11	Correct	143 ms	165112 KB	Output is correct
12	Correct	146 ms	165112 KB	Output is correct
13	Correct	141 ms	165112 KB	Output is correct
14	Correct	147 ms	165112 KB	Output is correct
15	Correct	144 ms	165112 KB	Output is correct
16	Correct	147 ms	165112 KB	Output is correct
17	Correct	146 ms	165112 KB	Output is correct
18	Correct	138 ms	165112 KB	Output is correct
19	Correct	140 ms	165136 KB	Output is correct
20	Correct	149 ms	165136 KB	Output is correct
21	Correct	138 ms	165136 KB	Output is correct
22	Correct	148 ms	165136 KB	Output is correct
23	Correct	143 ms	165136 KB	Output is correct
24	Correct	143 ms	165136 KB	Output is correct
25	Correct	151 ms	165136 KB	Output is correct
26	Correct	146 ms	165136 KB	Output is correct
27	Correct	146 ms	165136 KB	Output is correct
28	Correct	149 ms	165208 KB	Output is correct
29	Correct	147 ms	165208 KB	Output is correct
30	Correct	146 ms	165208 KB	Output is correct
31	Correct	996 ms	199232 KB	Output is correct
32	Correct	349 ms	199232 KB	Output is correct
33	Correct	984 ms	199232 KB	Output is correct
34	Correct	960 ms	199232 KB	Output is correct
35	Correct	1002 ms	199260 KB	Output is correct
36	Correct	997 ms	199260 KB	Output is correct
37	Correct	783 ms	199260 KB	Output is correct
38	Correct	781 ms	199260 KB	Output is correct
39	Correct	665 ms	199260 KB	Output is correct
40	Correct	707 ms	199260 KB	Output is correct
41	Correct	841 ms	199260 KB	Output is correct
42	Correct	850 ms	199260 KB	Output is correct
43	Correct	244 ms	199260 KB	Output is correct
44	Correct	854 ms	199260 KB	Output is correct
45	Correct	829 ms	199260 KB	Output is correct
46	Correct	809 ms	199260 KB	Output is correct
47	Correct	551 ms	199260 KB	Output is correct
48	Correct	564 ms	199260 KB	Output is correct
49	Correct	596 ms	199260 KB	Output is correct
50	Correct	627 ms	199260 KB	Output is correct
51	Correct	634 ms	199260 KB	Output is correct
52	Correct	780 ms	317868 KB	Output is correct
53	Correct	744 ms	317868 KB	Output is correct
54	Correct	904 ms	317868 KB	Output is correct
55	Correct	818 ms	317868 KB	Output is correct
56	Correct	780 ms	317868 KB	Output is correct
57	Correct	836 ms	317868 KB	Output is correct
58	Correct	838 ms	317868 KB	Output is correct
59	Correct	840 ms	317868 KB	Output is correct
60	Correct	860 ms	317868 KB	Output is correct
61	Correct	267 ms	317868 KB	Output is correct
62	Correct	771 ms	317868 KB	Output is correct
63	Correct	877 ms	317868 KB	Output is correct
64	Correct	877 ms	317868 KB	Output is correct
65	Correct	905 ms	317868 KB	Output is correct
66	Correct	852 ms	317868 KB	Output is correct
67	Correct	431 ms	317868 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	145 ms	164728 KB	Output is correct
2	Correct	140 ms	164728 KB	Output is correct
3	Correct	147 ms	164728 KB	Output is correct
4	Correct	137 ms	164728 KB	Output is correct
5	Correct	143 ms	164908 KB	Output is correct
6	Correct	145 ms	165112 KB	Output is correct
7	Correct	153 ms	165112 KB	Output is correct
8	Correct	148 ms	165112 KB	Output is correct
9	Correct	145 ms	165112 KB	Output is correct
10	Correct	144 ms	165112 KB	Output is correct
11	Correct	143 ms	165112 KB	Output is correct
12	Correct	146 ms	165112 KB	Output is correct
13	Correct	141 ms	165112 KB	Output is correct
14	Correct	147 ms	165112 KB	Output is correct
15	Correct	144 ms	165112 KB	Output is correct
16	Correct	147 ms	165112 KB	Output is correct
17	Correct	146 ms	165112 KB	Output is correct
18	Correct	138 ms	165112 KB	Output is correct
19	Correct	140 ms	165136 KB	Output is correct
20	Correct	149 ms	165136 KB	Output is correct
21	Correct	138 ms	165136 KB	Output is correct
22	Correct	148 ms	165136 KB	Output is correct
23	Correct	143 ms	165136 KB	Output is correct
24	Correct	143 ms	165136 KB	Output is correct
25	Correct	151 ms	165136 KB	Output is correct
26	Correct	146 ms	165136 KB	Output is correct
27	Correct	146 ms	165136 KB	Output is correct
28	Correct	149 ms	165208 KB	Output is correct
29	Correct	147 ms	165208 KB	Output is correct
30	Correct	146 ms	165208 KB	Output is correct
31	Correct	996 ms	199232 KB	Output is correct
32	Correct	349 ms	199232 KB	Output is correct
33	Correct	984 ms	199232 KB	Output is correct
34	Correct	960 ms	199232 KB	Output is correct
35	Correct	1002 ms	199260 KB	Output is correct
36	Correct	997 ms	199260 KB	Output is correct
37	Correct	783 ms	199260 KB	Output is correct
38	Correct	781 ms	199260 KB	Output is correct
39	Correct	665 ms	199260 KB	Output is correct
40	Correct	707 ms	199260 KB	Output is correct
41	Correct	841 ms	199260 KB	Output is correct
42	Correct	850 ms	199260 KB	Output is correct
43	Correct	244 ms	199260 KB	Output is correct
44	Correct	854 ms	199260 KB	Output is correct
45	Correct	829 ms	199260 KB	Output is correct
46	Correct	809 ms	199260 KB	Output is correct
47	Correct	551 ms	199260 KB	Output is correct
48	Correct	564 ms	199260 KB	Output is correct
49	Correct	596 ms	199260 KB	Output is correct
50	Correct	627 ms	199260 KB	Output is correct
51	Correct	634 ms	199260 KB	Output is correct
52	Execution timed out	5109 ms	316300 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

답안 #84171

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 35.0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0