oj.uz

답안 #543855

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
543855 2022-03-31T13:53:55 Z amunduzbaev 새 집 (APIO18_new_home) C++17
80 / 100
 3601 ms 790028 KB 
#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 * 40;
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];
vector<int> stor[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];
		stor[t[i]].push_back(i);
		ss[t[i]].insert(x[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); };
	
	vector<int> out(n); iota(out.begin(), out.end(), 0);
	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 O = 0, c = 0;
	
	for(int i=0;i<k;i++){
		if(stor[i].empty()) { c++; 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]]);
		}
		
		inc(x[stor[i].back()]);
		dec(x[stor[i][0]]);
	}
	
	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()){
				it--;
				inc(*it);
			}
		} else {
			if(it == ss[t[i]].begin()){
				dec(*it);
			} else {
				auto R = it; it--;
				add(*it, *R);
			}
		}
	};
	
	vector<int> res(q);
	for(auto i : p){
		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 49 ms 129472 KB Output is correct
2 Correct 51 ms 129428 KB Output is correct
3 Correct 50 ms 129464 KB Output is correct
4 Correct 51 ms 129892 KB Output is correct
5 Correct 51 ms 129580 KB Output is correct
6 Correct 67 ms 139360 KB Output is correct
7 Correct 57 ms 131868 KB Output is correct
8 Correct 59 ms 134244 KB Output is correct
9 Correct 62 ms 131848 KB Output is correct
10 Correct 66 ms 139160 KB Output is correct
11 Correct 59 ms 134468 KB Output is correct
12 Correct 63 ms 139408 KB Output is correct
13 Correct 64 ms 134408 KB Output is correct
14 Correct 59 ms 134464 KB Output is correct
15 Correct 57 ms 134408 KB Output is correct
16 Correct 58 ms 134340 KB Output is correct
17 Correct 59 ms 134468 KB Output is correct
18 Correct 56 ms 134340 KB Output is correct
19 Correct 60 ms 134388 KB Output is correct
20 Correct 59 ms 134468 KB Output is correct
21 Correct 50 ms 129520 KB Output is correct
22 Correct 55 ms 131856 KB Output is correct
23 Correct 57 ms 134288 KB Output is correct
24 Correct 58 ms 134256 KB Output is correct
25 Correct 60 ms 134344 KB Output is correct
26 Correct 60 ms 134776 KB Output is correct
27 Correct 55 ms 129580 KB Output is correct
28 Correct 66 ms 134456 KB Output is correct
29 Correct 57 ms 134436 KB Output is correct
30 Correct 57 ms 134396 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 129472 KB Output is correct
2 Correct 51 ms 129428 KB Output is correct
3 Correct 50 ms 129464 KB Output is correct
4 Correct 51 ms 129892 KB Output is correct
5 Correct 51 ms 129580 KB Output is correct
6 Correct 67 ms 139360 KB Output is correct
7 Correct 57 ms 131868 KB Output is correct
8 Correct 59 ms 134244 KB Output is correct
9 Correct 62 ms 131848 KB Output is correct
10 Correct 66 ms 139160 KB Output is correct
11 Correct 59 ms 134468 KB Output is correct
12 Correct 63 ms 139408 KB Output is correct
13 Correct 64 ms 134408 KB Output is correct
14 Correct 59 ms 134464 KB Output is correct
15 Correct 57 ms 134408 KB Output is correct
16 Correct 58 ms 134340 KB Output is correct
17 Correct 59 ms 134468 KB Output is correct
18 Correct 56 ms 134340 KB Output is correct
19 Correct 60 ms 134388 KB Output is correct
20 Correct 59 ms 134468 KB Output is correct
21 Correct 50 ms 129520 KB Output is correct
22 Correct 55 ms 131856 KB Output is correct
23 Correct 57 ms 134288 KB Output is correct
24 Correct 58 ms 134256 KB Output is correct
25 Correct 60 ms 134344 KB Output is correct
26 Correct 60 ms 134776 KB Output is correct
27 Correct 55 ms 129580 KB Output is correct
28 Correct 66 ms 134456 KB Output is correct
29 Correct 57 ms 134436 KB Output is correct
30 Correct 57 ms 134396 KB Output is correct
31 Correct 3417 ms 782124 KB Output is correct
32 Correct 225 ms 135136 KB Output is correct
33 Correct 2847 ms 779576 KB Output is correct
34 Correct 3601 ms 778560 KB Output is correct
35 Correct 3285 ms 789012 KB Output is correct
36 Correct 2966 ms 784108 KB Output is correct
37 Correct 2487 ms 785492 KB Output is correct
38 Correct 2183 ms 781116 KB Output is correct
39 Correct 1576 ms 783436 KB Output is correct
40 Correct 1660 ms 782176 KB Output is correct
41 Correct 2119 ms 783836 KB Output is correct
42 Correct 2096 ms 787272 KB Output is correct
43 Correct 113 ms 136324 KB Output is correct
44 Correct 2065 ms 783332 KB Output is correct
45 Correct 1855 ms 780916 KB Output is correct
46 Correct 1739 ms 780048 KB Output is correct
47 Correct 1048 ms 782960 KB Output is correct
48 Correct 1125 ms 782364 KB Output is correct
49 Correct 1257 ms 785220 KB Output is correct
50 Correct 1337 ms 790028 KB Output is correct
51 Correct 1474 ms 784276 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1168 ms 221760 KB Output is correct
2 Correct 935 ms 223564 KB Output is correct
3 Correct 942 ms 206492 KB Output is correct
4 Correct 1133 ms 218568 KB Output is correct
5 Correct 826 ms 223068 KB Output is correct
6 Correct 904 ms 223564 KB Output is correct
7 Correct 775 ms 206412 KB Output is correct
8 Correct 1010 ms 218152 KB Output is correct
9 Correct 1060 ms 223076 KB Output is correct
10 Correct 993 ms 224748 KB Output is correct
11 Correct 731 ms 222156 KB Output is correct
12 Correct 844 ms 224100 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2138 ms 244068 KB Output is correct
2 Correct 510 ms 160136 KB Output is correct
3 Correct 2095 ms 258916 KB Output is correct
4 Correct 865 ms 218292 KB Output is correct
5 Correct 1565 ms 240952 KB Output is correct
6 Correct 1435 ms 234616 KB Output is correct
7 Correct 1737 ms 257532 KB Output is correct
8 Correct 1912 ms 258796 KB Output is correct
9 Correct 843 ms 219468 KB Output is correct
10 Correct 1450 ms 238584 KB Output is correct
11 Correct 1970 ms 253352 KB Output is correct
12 Correct 1985 ms 260044 KB Output is correct
13 Correct 965 ms 252456 KB Output is correct
14 Correct 917 ms 251960 KB Output is correct
15 Correct 1084 ms 256228 KB Output is correct
16 Correct 1314 ms 257544 KB Output is correct
17 Correct 1086 ms 255980 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 129472 KB Output is correct
2 Correct 51 ms 129428 KB Output is correct
3 Correct 50 ms 129464 KB Output is correct
4 Correct 51 ms 129892 KB Output is correct
5 Correct 51 ms 129580 KB Output is correct
6 Correct 67 ms 139360 KB Output is correct
7 Correct 57 ms 131868 KB Output is correct
8 Correct 59 ms 134244 KB Output is correct
9 Correct 62 ms 131848 KB Output is correct
10 Correct 66 ms 139160 KB Output is correct
11 Correct 59 ms 134468 KB Output is correct
12 Correct 63 ms 139408 KB Output is correct
13 Correct 64 ms 134408 KB Output is correct
14 Correct 59 ms 134464 KB Output is correct
15 Correct 57 ms 134408 KB Output is correct
16 Correct 58 ms 134340 KB Output is correct
17 Correct 59 ms 134468 KB Output is correct
18 Correct 56 ms 134340 KB Output is correct
19 Correct 60 ms 134388 KB Output is correct
20 Correct 59 ms 134468 KB Output is correct
21 Correct 50 ms 129520 KB Output is correct
22 Correct 55 ms 131856 KB Output is correct
23 Correct 57 ms 134288 KB Output is correct
24 Correct 58 ms 134256 KB Output is correct
25 Correct 60 ms 134344 KB Output is correct
26 Correct 60 ms 134776 KB Output is correct
27 Correct 55 ms 129580 KB Output is correct
28 Correct 66 ms 134456 KB Output is correct
29 Correct 57 ms 134436 KB Output is correct
30 Correct 57 ms 134396 KB Output is correct
31 Correct 3417 ms 782124 KB Output is correct
32 Correct 225 ms 135136 KB Output is correct
33 Correct 2847 ms 779576 KB Output is correct
34 Correct 3601 ms 778560 KB Output is correct
35 Correct 3285 ms 789012 KB Output is correct
36 Correct 2966 ms 784108 KB Output is correct
37 Correct 2487 ms 785492 KB Output is correct
38 Correct 2183 ms 781116 KB Output is correct
39 Correct 1576 ms 783436 KB Output is correct
40 Correct 1660 ms 782176 KB Output is correct
41 Correct 2119 ms 783836 KB Output is correct
42 Correct 2096 ms 787272 KB Output is correct
43 Correct 113 ms 136324 KB Output is correct
44 Correct 2065 ms 783332 KB Output is correct
45 Correct 1855 ms 780916 KB Output is correct
46 Correct 1739 ms 780048 KB Output is correct
47 Correct 1048 ms 782960 KB Output is correct
48 Correct 1125 ms 782364 KB Output is correct
49 Correct 1257 ms 785220 KB Output is correct
50 Correct 1337 ms 790028 KB Output is correct
51 Correct 1474 ms 784276 KB Output is correct
52 Correct 792 ms 436024 KB Output is correct
53 Correct 800 ms 451216 KB Output is correct
54 Correct 1906 ms 788644 KB Output is correct
55 Correct 1611 ms 492028 KB Output is correct
56 Correct 1408 ms 452432 KB Output is correct
57 Correct 2007 ms 784416 KB Output is correct
58 Correct 1603 ms 493196 KB Output is correct
59 Correct 1370 ms 454460 KB Output is correct
60 Correct 2007 ms 787392 KB Output is correct
61 Correct 133 ms 141400 KB Output is correct
62 Correct 801 ms 436188 KB Output is correct
63 Correct 1428 ms 446944 KB Output is correct
64 Correct 1631 ms 486008 KB Output is correct
65 Correct 2123 ms 789460 KB Output is correct
66 Correct 2329 ms 786764 KB Output is correct
67 Correct 332 ms 147112 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 129472 KB Output is correct
2 Correct 51 ms 129428 KB Output is correct
3 Correct 50 ms 129464 KB Output is correct
4 Correct 51 ms 129892 KB Output is correct
5 Correct 51 ms 129580 KB Output is correct
6 Correct 67 ms 139360 KB Output is correct
7 Correct 57 ms 131868 KB Output is correct
8 Correct 59 ms 134244 KB Output is correct
9 Correct 62 ms 131848 KB Output is correct
10 Correct 66 ms 139160 KB Output is correct
11 Correct 59 ms 134468 KB Output is correct
12 Correct 63 ms 139408 KB Output is correct
13 Correct 64 ms 134408 KB Output is correct
14 Correct 59 ms 134464 KB Output is correct
15 Correct 57 ms 134408 KB Output is correct
16 Correct 58 ms 134340 KB Output is correct
17 Correct 59 ms 134468 KB Output is correct
18 Correct 56 ms 134340 KB Output is correct
19 Correct 60 ms 134388 KB Output is correct
20 Correct 59 ms 134468 KB Output is correct
21 Correct 50 ms 129520 KB Output is correct
22 Correct 55 ms 131856 KB Output is correct
23 Correct 57 ms 134288 KB Output is correct
24 Correct 58 ms 134256 KB Output is correct
25 Correct 60 ms 134344 KB Output is correct
26 Correct 60 ms 134776 KB Output is correct
27 Correct 55 ms 129580 KB Output is correct
28 Correct 66 ms 134456 KB Output is correct
29 Correct 57 ms 134436 KB Output is correct
30 Correct 57 ms 134396 KB Output is correct
31 Correct 3417 ms 782124 KB Output is correct
32 Correct 225 ms 135136 KB Output is correct
33 Correct 2847 ms 779576 KB Output is correct
34 Correct 3601 ms 778560 KB Output is correct
35 Correct 3285 ms 789012 KB Output is correct
36 Correct 2966 ms 784108 KB Output is correct
37 Correct 2487 ms 785492 KB Output is correct
38 Correct 2183 ms 781116 KB Output is correct
39 Correct 1576 ms 783436 KB Output is correct
40 Correct 1660 ms 782176 KB Output is correct
41 Correct 2119 ms 783836 KB Output is correct
42 Correct 2096 ms 787272 KB Output is correct
43 Correct 113 ms 136324 KB Output is correct
44 Correct 2065 ms 783332 KB Output is correct
45 Correct 1855 ms 780916 KB Output is correct
46 Correct 1739 ms 780048 KB Output is correct
47 Correct 1048 ms 782960 KB Output is correct
48 Correct 1125 ms 782364 KB Output is correct
49 Correct 1257 ms 785220 KB Output is correct
50 Correct 1337 ms 790028 KB Output is correct
51 Correct 1474 ms 784276 KB Output is correct
52 Correct 1168 ms 221760 KB Output is correct
53 Correct 935 ms 223564 KB Output is correct
54 Correct 942 ms 206492 KB Output is correct
55 Correct 1133 ms 218568 KB Output is correct
56 Correct 826 ms 223068 KB Output is correct
57 Correct 904 ms 223564 KB Output is correct
58 Correct 775 ms 206412 KB Output is correct
59 Correct 1010 ms 218152 KB Output is correct
60 Correct 1060 ms 223076 KB Output is correct
61 Correct 993 ms 224748 KB Output is correct
62 Correct 731 ms 222156 KB Output is correct
63 Correct 844 ms 224100 KB Output is correct
64 Correct 2138 ms 244068 KB Output is correct
65 Correct 510 ms 160136 KB Output is correct
66 Correct 2095 ms 258916 KB Output is correct
67 Correct 865 ms 218292 KB Output is correct
68 Correct 1565 ms 240952 KB Output is correct
69 Correct 1435 ms 234616 KB Output is correct
70 Correct 1737 ms 257532 KB Output is correct
71 Correct 1912 ms 258796 KB Output is correct
72 Correct 843 ms 219468 KB Output is correct
73 Correct 1450 ms 238584 KB Output is correct
74 Correct 1970 ms 253352 KB Output is correct
75 Correct 1985 ms 260044 KB Output is correct
76 Correct 965 ms 252456 KB Output is correct
77 Correct 917 ms 251960 KB Output is correct
78 Correct 1084 ms 256228 KB Output is correct
79 Correct 1314 ms 257544 KB Output is correct
80 Correct 1086 ms 255980 KB Output is correct
81 Correct 792 ms 436024 KB Output is correct
82 Correct 800 ms 451216 KB Output is correct
83 Correct 1906 ms 788644 KB Output is correct
84 Correct 1611 ms 492028 KB Output is correct
85 Correct 1408 ms 452432 KB Output is correct
86 Correct 2007 ms 784416 KB Output is correct
87 Correct 1603 ms 493196 KB Output is correct
88 Correct 1370 ms 454460 KB Output is correct
89 Correct 2007 ms 787392 KB Output is correct
90 Correct 133 ms 141400 KB Output is correct
91 Correct 801 ms 436188 KB Output is correct
92 Correct 1428 ms 446944 KB Output is correct
93 Correct 1631 ms 486008 KB Output is correct
94 Correct 2123 ms 789460 KB Output is correct
95 Correct 2329 ms 786764 KB Output is correct
96 Correct 332 ms 147112 KB Output is correct
97 Incorrect 951 ms 221292 KB Output isn't correct
98 Halted 0 ms 0 KB -