답안 #543837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543837	2022-03-31T13:37:11 Z	amunduzbaev	새 집 (APIO18_new_home)	C++17	47 / 100	4621 ms	759732 KB

new_home

#include "bits/stdc++.h"
using namespace std;

namespace NLOGsq{

#define ar array
#define pq priority_queue

const int N = 3e5 + 5;
const int M = N * 30;
const int MX = 1e8 + 5;
 
struct node{
	pq<int> in[2], del[2];
	int f[2];
	
	node (){
		f[0] = f[1] = 0;
	}
};
 
node def;
 
struct ST{
	vector<node> tree;
	int last;
	ST(){
		tree.push_back(def);
		last = 0;
	}
	
	void make_l(int x){
		//~ tree.push_back(def);
		if(tree[x].f[0]) return;
		tree.push_back(def);
		tree[x].f[0] = ++last; // tree[x].f[1] = ++last;
		//~ assert(last < M);
	}
	void make_r(int x){
		//~ tree.push_back(def);
		if(tree[x].f[1]) return;
		tree.push_back(def);
		tree[x].f[1] = ++last; // tree[x].f[1] = ++last;
		//~ assert(last < M);
	}
	
	void add(int l, int r, int s, int t, int lx = 0, int rx = MX, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			if(t == 1){
				tree[x].in[0].push(s + (lx - l));
			} else {
				tree[x].in[1].push(s - (lx - l));
			} return;
		} int m = (lx + rx) >> 1;
		//~ make(x);
		if(lx <= r && m >= l){
			make_l(x);
			add(l, r, s, t, lx, m, tree[x].f[0]);
		} if(m + 1 <= r && rx >= l){
			make_r(x);
			add(l, r, s, t, m+1, rx, tree[x].f[1]);
		}
		//~ add(l, r, s, t, lx, m, tree[x].f[0]), add(l, r, s, t, m+1, rx, tree[x].f[1]);
	}
	
	void bal(pq<int>& a, pq<int>& b){
		while(!a.empty() && !b.empty() && a.top() == b.top()){
			a.pop();
			b.pop();
		}
	}
	
	void del(int l, int r, int s, int t, int lx = 0, int rx = MX, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			if(t == 1){
				tree[x].del[0].push(s + (lx - l));
			} else {
				tree[x].del[1].push(s - (lx - l));
			} return;
		} int m = (lx + rx) >> 1;
		if(lx <= r && m >= l){
			make_l(x);
			del(l, r, s, t, lx, m, tree[x].f[0]);
		} if(m + 1 <= r && rx >= l){
			make_r(x);
			del(l, r, s, t, m+1, rx, tree[x].f[1]);
		}
	}
	
	int get(int i, int lx = 0, int rx = MX, int x = 0){
		int res = 0;
		bal(tree[x].in[0], tree[x].del[0]);
		bal(tree[x].in[1], tree[x].del[1]);
		if(!tree[x].in[0].empty()) res = max(res, tree[x].in[0].top() + (i - lx));
		if(!tree[x].in[1].empty()) res = max(res, tree[x].in[1].top() - (i - lx));
		if(lx == rx) return res;
		int m = (lx + rx) >> 1;
		if(i <= m) return max((tree[x].f[0] ? get(i, lx, m, tree[x].f[0]) : 0), res);
		else return max((tree[x].f[1] ? get(i, m+1, rx, tree[x].f[1]) : 0), res);
	}
}tree;
/*

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1

*/

int x[N], t[N], a[N], b[N], l[N], y[N];
multiset<int> ss[N];

void solve(int n, int k, int q){ //assert(false);
	for(int i=0;i<n;i++){
		cin>>x[i]>>t[i]>>a[i]>>b[i];
		--t[i];
	}

	auto add = [&](int l, int r){
		if(l == r) return;
		int m = (l + r) >> 1;
		tree.add(l, m, 0, 1);
		tree.add(m + 1, r, r - m - 1, -1);
	}; auto inc = [&](int x) { tree.add(x, MX, 0, 1); };
	auto dec = [&](int x) { tree.add(0, x, x, -1); };
	
	auto dadd = [&](int l, int r){
		if(l == r) return;
		int m = (l + r) >> 1;
		tree.del(l, m, 0, 1);
		tree.del(m + 1, r, r - m - 1, -1);
	}; auto dinc = [&](int x) { tree.del(x, MX, 0, 1); };
	auto ddec = [&](int x) { tree.del(0, x, x, -1); };
	
	//~ bool is = 1;
	//~ for(int i=0;i<k;i++){
		//~ if(stor[i].empty()) { is = 0; break; }
		//~ sort(stor[i].begin(), stor[i].end(), [&](int i, int j){
			//~ return (x[i] < x[j]);
		//~ });
		//~ for(int j=1;j<(int)stor[i].size();j++){
			//~ add(x[stor[i][j-1]], x[stor[i][j]]);
		//~ }
		
		//~ dec(x[stor[i][0]]);
		//~ inc(x[stor[i].back()]);
	//~ }
	
	vector<int> in(n); iota(in.begin(), in.end(), 0);
	vector<int> out(n); iota(out.begin(), out.end(), 0);
	sort(in.begin(), in.end(), [&](int i, int j){
		return (a[i] < a[j]);
	});
	sort(out.begin(), out.end(), [&](int i, int j){
		return (b[i] < b[j]);
	});
	vector<int> p(q);
	
	for(int i=0;i<q;i++){ p[i] = i;
		cin>>l[i]>>y[i];
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (y[i] < y[j]);
	});
	
	int I = 0, O = 0, c = k;
	auto NEW = [&](int i){
		auto it = ss[t[i]].upper_bound(x[i]);
		if(ss[t[i]].empty()) c--;
		if(it == ss[t[i]].end()){
			if(it != ss[t[i]].begin()){
				it--;
				dinc(*it);
				add(*it, x[i]);
				inc(x[i]);
			} else {
				inc(x[i]);
				dec(x[i]);
			}
		} else {
			if(it == ss[t[i]].begin()){
				ddec(*it);
				add(x[i], *it);
				dec(x[i]);
			} else {
				auto R = it; it--;
				dadd(*it, *R);
				add(*it, x[i]);
				add(x[i], *R);
			}
		}
		
		ss[t[i]].insert(x[i]);
	};
	
	auto DEL = [&](int i){
		ss[t[i]].erase(ss[t[i]].find(x[i]));
		if(ss[t[i]].empty()) c++;
		auto it = ss[t[i]].upper_bound(x[i]);
		if(it == ss[t[i]].end()){
			if(it == ss[t[i]].begin()){
				dinc(x[i]);
				ddec(x[i]);
			} else {
				it--;
				dadd(*it, x[i]);
				dinc(x[i]);
				inc(*it);
			}
		} else {
			if(it == ss[t[i]].begin()){
				dadd(x[i], *it);
				ddec(x[i]);
				dec(*it);
			} else {
				auto R = it; it--;
				dadd(*it, x[i]);
				dadd(x[i], *R);
				add(*it, *R);
			}
		}
	};
	
	vector<int> res(q);
	for(auto i : p){
		while(I < n && a[in[I]] <= y[i]){
			NEW(in[I]);
			I++;
		}
		
		while(O < n && b[out[O]] < y[i]){
			DEL(out[O]);
			O++;
		}
		
		if(!c) res[i] = tree.get(l[i]);
		else res[i] = -1;
	}
	
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}
};

namespace temp{
const int N = 3e5 + 5;
const int M = N * 30;
const int MX = 1e8 + 5;

struct ST{
	int tree[M][2], f[M][2];
	int last;
	
	ST(){
		memset(tree, -1, sizeof tree);
		last = 0;
	}
	
	void make(int x){
		if(!f[x][0]) f[x][0] = ++last;
		if(!f[x][1]) f[x][1] = ++last;
	}
	
	void umax(int l, int r, int s, int t, int lx = 0, int rx = MX, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			if(t == 1) tree[x][0] = max(tree[x][0], s + (lx - l));
			else tree[x][1] = max(tree[x][1], s - (lx - l));
			return;
		} int m = (lx + rx) >> 1;
		make(x);
		umax(l, r, s, t, lx, m, f[x][0]);
		umax(l, r, s, t, m+1, rx, f[x][1]);
	}
	
	int get(int i, int lx = 0, int rx = MX, int x = 0){
		int res = 0;
		if(~tree[x][0]) res = max(res, tree[x][0] + (i - lx));
		if(~tree[x][1]) res = max(res, tree[x][1] - (i - lx));
		if(lx == rx) return res;
		int m = (lx + rx) >> 1;
		if(i <= m) return max((f[x][0] ? get(i, lx, m, f[x][0]) : 0), res);
		else return max((f[x][1] ? get(i, m+1, rx, f[x][1]) : 0), res);
	}
}tree;

int x[N], t[N], a[N], b[N], l[N], y[N];
multiset<int> ss[N];

void solve(int n, int k, int q){
	for(int i=0;i<n;i++){
		cin>>x[i]>>t[i]>>a[i]>>b[i];
		--t[i];
	}

	auto add = [&](int l, int r){
		if(l == r) return;
		int m = (l + r) >> 1;
		tree.umax(l, m, 0, 1);
		tree.umax(m + 1, r, r - m - 1, -1);
	}; auto inc = [&](int x) { tree.umax(x, MX, 0, 1); };
	auto dec = [&](int x) { tree.umax(0, x, x, -1); };
	
	//~ auto dadd = [&](int l, int r){
		//~ if(l == r) return;
		//~ int m = (l + r) >> 1;
		//~ tree.del(l, m, 0, 1);
		//~ tree.del(m + 1, r, r - m - 1, -1);
	//~ }; auto dinc = [&](int x) { tree.del(x, MX, 0, 1); };
	//~ auto ddec = [&](int x) { tree.del(0, x, x, -1); };
	
	//~ bool is = 1;
	//~ for(int i=0;i<k;i++){
		//~ if(stor[i].empty()) { is = 0; break; }
		//~ sort(stor[i].begin(), stor[i].end(), [&](int i, int j){
			//~ return (x[i] < x[j]);
		//~ });
		//~ for(int j=1;j<(int)stor[i].size();j++){
			//~ add(x[stor[i][j-1]], x[stor[i][j]]);
		//~ }
		
		//~ dec(x[stor[i][0]]);
		//~ inc(x[stor[i].back()]);
	//~ }
	
	vector<int> in(n); iota(in.begin(), in.end(), 0);
	vector<int> out(n); iota(out.begin(), out.end(), 0);
	sort(in.begin(), in.end(), [&](int i, int j){
		return (a[i] < a[j]);
	});
	sort(out.begin(), out.end(), [&](int i, int j){
		return (b[i] < b[j]);
	});
	vector<int> p(q);
	
	for(int i=0;i<q;i++){ p[i] = i;
		cin>>l[i]>>y[i];
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (y[i] < y[j]);
	});
	
	int I = 0, O = 0, c = k;
	auto NEW = [&](int i){
		auto it = ss[t[i]].upper_bound(x[i]);
		if(ss[t[i]].empty()) c--;
		if(it == ss[t[i]].end()){
			if(it != ss[t[i]].begin()){
				it--;
				//~ dinc(*it);
				add(*it, x[i]);
				inc(x[i]);
			} else {
				inc(x[i]);
				dec(x[i]);
			}
		} else {
			if(it == ss[t[i]].begin()){
				//~ ddec(*it);
				add(x[i], *it);
				dec(x[i]);
			} else {
				auto R = it; it--;
				//~ dadd(*it, *R);
				add(*it, x[i]);
				add(x[i], *R);
			}
		}
		
		ss[t[i]].insert(x[i]);
	};
	
	auto DEL = [&](int i){
		ss[t[i]].erase(ss[t[i]].find(x[i]));
		if(ss[t[i]].empty()) c++;
		auto it = ss[t[i]].upper_bound(x[i]);
		if(it == ss[t[i]].end()){
			if(it == ss[t[i]].begin()){
				//~ dinc(x[i]);
				//~ ddec(x[i]);
			} else {
				it--;
				//~ dadd(*it, x[i]);
				//~ dinc(x[i]);
				inc(*it);
			}
		} else {
			if(it == ss[t[i]].begin()){
				//~ dadd(x[i], *it);
				//~ ddec(x[i]);
				dec(*it);
			} else {
				auto R = it; it--;
				//~ dadd(*it, x[i]);
				//~ dadd(x[i], *R);
				add(*it, *R);
			}
		}
	};
	
	vector<int> res(q);
	for(auto i : p){
		while(I < n && a[in[I]] <= y[i]){
			NEW(in[I]);
			I++;
		}
		
		while(O < n && b[out[O]] < y[i]){
			DEL(out[O]);
			O++;
		}
		
		if(!c) res[i] = tree.get(l[i]);
		else res[i] = -1;
	}
	
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}

};

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k, q; cin>>n>>k>>q;
	if(n <= 60000 && q <= 60000){
		NLOGsq::solve(n, k, q);
	} else {
		temp::solve(n, k, q);
	}
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	98948 KB	Output is correct
2	Correct	49 ms	98960 KB	Output is correct
3	Correct	57 ms	98988 KB	Output is correct
4	Correct	47 ms	99404 KB	Output is correct
5	Correct	49 ms	99068 KB	Output is correct
6	Correct	73 ms	108872 KB	Output is correct
7	Correct	56 ms	101324 KB	Output is correct
8	Correct	63 ms	103808 KB	Output is correct
9	Correct	53 ms	101372 KB	Output is correct
10	Correct	64 ms	108624 KB	Output is correct
11	Correct	60 ms	104004 KB	Output is correct
12	Correct	61 ms	108924 KB	Output is correct
13	Correct	54 ms	103932 KB	Output is correct
14	Correct	59 ms	103988 KB	Output is correct
15	Correct	50 ms	103908 KB	Output is correct
16	Correct	73 ms	103832 KB	Output is correct
17	Correct	64 ms	103952 KB	Output is correct
18	Correct	63 ms	103832 KB	Output is correct
19	Correct	62 ms	103820 KB	Output is correct
20	Correct	84 ms	103948 KB	Output is correct
21	Correct	61 ms	99096 KB	Output is correct
22	Correct	53 ms	101320 KB	Output is correct
23	Correct	54 ms	103768 KB	Output is correct
24	Correct	55 ms	103804 KB	Output is correct
25	Correct	59 ms	103908 KB	Output is correct
26	Correct	61 ms	104236 KB	Output is correct
27	Correct	54 ms	99068 KB	Output is correct
28	Correct	51 ms	103912 KB	Output is correct
29	Correct	58 ms	103924 KB	Output is correct
30	Correct	67 ms	103924 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	98948 KB	Output is correct
2	Correct	49 ms	98960 KB	Output is correct
3	Correct	57 ms	98988 KB	Output is correct
4	Correct	47 ms	99404 KB	Output is correct
5	Correct	49 ms	99068 KB	Output is correct
6	Correct	73 ms	108872 KB	Output is correct
7	Correct	56 ms	101324 KB	Output is correct
8	Correct	63 ms	103808 KB	Output is correct
9	Correct	53 ms	101372 KB	Output is correct
10	Correct	64 ms	108624 KB	Output is correct
11	Correct	60 ms	104004 KB	Output is correct
12	Correct	61 ms	108924 KB	Output is correct
13	Correct	54 ms	103932 KB	Output is correct
14	Correct	59 ms	103988 KB	Output is correct
15	Correct	50 ms	103908 KB	Output is correct
16	Correct	73 ms	103832 KB	Output is correct
17	Correct	64 ms	103952 KB	Output is correct
18	Correct	63 ms	103832 KB	Output is correct
19	Correct	62 ms	103820 KB	Output is correct
20	Correct	84 ms	103948 KB	Output is correct
21	Correct	61 ms	99096 KB	Output is correct
22	Correct	53 ms	101320 KB	Output is correct
23	Correct	54 ms	103768 KB	Output is correct
24	Correct	55 ms	103804 KB	Output is correct
25	Correct	59 ms	103908 KB	Output is correct
26	Correct	61 ms	104236 KB	Output is correct
27	Correct	54 ms	99068 KB	Output is correct
28	Correct	51 ms	103912 KB	Output is correct
29	Correct	58 ms	103924 KB	Output is correct
30	Correct	67 ms	103924 KB	Output is correct
31	Correct	4621 ms	752332 KB	Output is correct
32	Correct	317 ms	105452 KB	Output is correct
33	Correct	3738 ms	750724 KB	Output is correct
34	Correct	4562 ms	749452 KB	Output is correct
35	Correct	4010 ms	759732 KB	Output is correct
36	Correct	3489 ms	754736 KB	Output is correct
37	Correct	3000 ms	756148 KB	Output is correct
38	Correct	2624 ms	751720 KB	Output is correct
39	Correct	1871 ms	753768 KB	Output is correct
40	Correct	2132 ms	752632 KB	Output is correct
41	Correct	2683 ms	754168 KB	Output is correct
42	Correct	2697 ms	757860 KB	Output is correct
43	Correct	150 ms	106880 KB	Output is correct
44	Correct	2515 ms	753836 KB	Output is correct
45	Correct	2167 ms	751716 KB	Output is correct
46	Correct	1998 ms	750664 KB	Output is correct
47	Correct	1078 ms	753548 KB	Output is correct
48	Correct	1121 ms	752520 KB	Output is correct
49	Correct	1295 ms	754624 KB	Output is correct
50	Correct	1440 ms	759204 KB	Output is correct
51	Correct	1402 ms	753700 KB	Output is correct

Subtask #3

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1577 ms	196868 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1726 ms	389640 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	98948 KB	Output is correct
2	Correct	49 ms	98960 KB	Output is correct
3	Correct	57 ms	98988 KB	Output is correct
4	Correct	47 ms	99404 KB	Output is correct
5	Correct	49 ms	99068 KB	Output is correct
6	Correct	73 ms	108872 KB	Output is correct
7	Correct	56 ms	101324 KB	Output is correct
8	Correct	63 ms	103808 KB	Output is correct
9	Correct	53 ms	101372 KB	Output is correct
10	Correct	64 ms	108624 KB	Output is correct
11	Correct	60 ms	104004 KB	Output is correct
12	Correct	61 ms	108924 KB	Output is correct
13	Correct	54 ms	103932 KB	Output is correct
14	Correct	59 ms	103988 KB	Output is correct
15	Correct	50 ms	103908 KB	Output is correct
16	Correct	73 ms	103832 KB	Output is correct
17	Correct	64 ms	103952 KB	Output is correct
18	Correct	63 ms	103832 KB	Output is correct
19	Correct	62 ms	103820 KB	Output is correct
20	Correct	84 ms	103948 KB	Output is correct
21	Correct	61 ms	99096 KB	Output is correct
22	Correct	53 ms	101320 KB	Output is correct
23	Correct	54 ms	103768 KB	Output is correct
24	Correct	55 ms	103804 KB	Output is correct
25	Correct	59 ms	103908 KB	Output is correct
26	Correct	61 ms	104236 KB	Output is correct
27	Correct	54 ms	99068 KB	Output is correct
28	Correct	51 ms	103912 KB	Output is correct
29	Correct	58 ms	103924 KB	Output is correct
30	Correct	67 ms	103924 KB	Output is correct
31	Correct	4621 ms	752332 KB	Output is correct
32	Correct	317 ms	105452 KB	Output is correct
33	Correct	3738 ms	750724 KB	Output is correct
34	Correct	4562 ms	749452 KB	Output is correct
35	Correct	4010 ms	759732 KB	Output is correct
36	Correct	3489 ms	754736 KB	Output is correct
37	Correct	3000 ms	756148 KB	Output is correct
38	Correct	2624 ms	751720 KB	Output is correct
39	Correct	1871 ms	753768 KB	Output is correct
40	Correct	2132 ms	752632 KB	Output is correct
41	Correct	2683 ms	754168 KB	Output is correct
42	Correct	2697 ms	757860 KB	Output is correct
43	Correct	150 ms	106880 KB	Output is correct
44	Correct	2515 ms	753836 KB	Output is correct
45	Correct	2167 ms	751716 KB	Output is correct
46	Correct	1998 ms	750664 KB	Output is correct
47	Correct	1078 ms	753548 KB	Output is correct
48	Correct	1121 ms	752520 KB	Output is correct
49	Correct	1295 ms	754624 KB	Output is correct
50	Correct	1440 ms	759204 KB	Output is correct
51	Correct	1402 ms	753700 KB	Output is correct
52	Correct	925 ms	405568 KB	Output is correct
53	Correct	916 ms	420636 KB	Output is correct
54	Correct	1990 ms	758288 KB	Output is correct
55	Correct	1827 ms	461304 KB	Output is correct
56	Correct	1614 ms	421800 KB	Output is correct
57	Correct	2483 ms	753852 KB	Output is correct
58	Correct	2106 ms	462444 KB	Output is correct
59	Correct	1899 ms	423884 KB	Output is correct
60	Correct	2508 ms	756768 KB	Output is correct
61	Correct	169 ms	110864 KB	Output is correct
62	Correct	977 ms	405624 KB	Output is correct
63	Correct	1569 ms	416288 KB	Output is correct
64	Correct	2024 ms	455224 KB	Output is correct
65	Correct	2404 ms	758836 KB	Output is correct
66	Correct	2438 ms	755972 KB	Output is correct
67	Correct	360 ms	116576 KB	Output is correct

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	98948 KB	Output is correct
2	Correct	49 ms	98960 KB	Output is correct
3	Correct	57 ms	98988 KB	Output is correct
4	Correct	47 ms	99404 KB	Output is correct
5	Correct	49 ms	99068 KB	Output is correct
6	Correct	73 ms	108872 KB	Output is correct
7	Correct	56 ms	101324 KB	Output is correct
8	Correct	63 ms	103808 KB	Output is correct
9	Correct	53 ms	101372 KB	Output is correct
10	Correct	64 ms	108624 KB	Output is correct
11	Correct	60 ms	104004 KB	Output is correct
12	Correct	61 ms	108924 KB	Output is correct
13	Correct	54 ms	103932 KB	Output is correct
14	Correct	59 ms	103988 KB	Output is correct
15	Correct	50 ms	103908 KB	Output is correct
16	Correct	73 ms	103832 KB	Output is correct
17	Correct	64 ms	103952 KB	Output is correct
18	Correct	63 ms	103832 KB	Output is correct
19	Correct	62 ms	103820 KB	Output is correct
20	Correct	84 ms	103948 KB	Output is correct
21	Correct	61 ms	99096 KB	Output is correct
22	Correct	53 ms	101320 KB	Output is correct
23	Correct	54 ms	103768 KB	Output is correct
24	Correct	55 ms	103804 KB	Output is correct
25	Correct	59 ms	103908 KB	Output is correct
26	Correct	61 ms	104236 KB	Output is correct
27	Correct	54 ms	99068 KB	Output is correct
28	Correct	51 ms	103912 KB	Output is correct
29	Correct	58 ms	103924 KB	Output is correct
30	Correct	67 ms	103924 KB	Output is correct
31	Correct	4621 ms	752332 KB	Output is correct
32	Correct	317 ms	105452 KB	Output is correct
33	Correct	3738 ms	750724 KB	Output is correct
34	Correct	4562 ms	749452 KB	Output is correct
35	Correct	4010 ms	759732 KB	Output is correct
36	Correct	3489 ms	754736 KB	Output is correct
37	Correct	3000 ms	756148 KB	Output is correct
38	Correct	2624 ms	751720 KB	Output is correct
39	Correct	1871 ms	753768 KB	Output is correct
40	Correct	2132 ms	752632 KB	Output is correct
41	Correct	2683 ms	754168 KB	Output is correct
42	Correct	2697 ms	757860 KB	Output is correct
43	Correct	150 ms	106880 KB	Output is correct
44	Correct	2515 ms	753836 KB	Output is correct
45	Correct	2167 ms	751716 KB	Output is correct
46	Correct	1998 ms	750664 KB	Output is correct
47	Correct	1078 ms	753548 KB	Output is correct
48	Correct	1121 ms	752520 KB	Output is correct
49	Correct	1295 ms	754624 KB	Output is correct
50	Correct	1440 ms	759204 KB	Output is correct
51	Correct	1402 ms	753700 KB	Output is correct
52	Incorrect	1577 ms	196868 KB	Output isn't correct
53	Halted	0 ms	0 KB	-