oj.uz

답안 #406271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406271 2021-05-17T10:06:46 Z kshitij_sodani 새 집 (APIO18_new_home) C++14
80 / 100
 5000 ms 528124 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
int n,k,q;
int ans[300001];
set<int> pre[300001];
map<int,int> pre2[300001];
bool vis[3000001];
map<pair<int,pair<int,int>>,int> xx;
map<pair<int,pair<int,int>>,int> xx2;
map<int,int> ss;
map<int,int> ss2;
map<int,int> ss3;
map<int,int> ss4;
vector<pair<int,int>> yy;

int ne=0;
int nn;
pair<int,int> solve(int i,int j){
	pair<int,int> ac={i,0};
	pair<int,int> ac2={j+1,0};
	return {lower_bound(yy.begin(),yy.end(),ac)-yy.begin(),lower_bound(yy.begin(),yy.end(),ac2)-yy.begin()-1};
}
priority_queue<pair<int,int>> tree[4*400001];
priority_queue<pair<int,int>> tree2[4*400001];
int tree3[4*800001][2];
int kk=1;
//int ans[300001];
void update(int no,int l,int r,int aa,int bb,pair<int,int> x,int st){
	/*if(no==0){
		cout<<aa<<":"<<bb<<":"<<x.a<<":"<<x.b<<endl;
	}*/
	
	if(r<aa or l>bb or aa>bb){
		return;
	}
	if(aa<=l and r<=bb){
		//cout<<l<<",,"<<r<<endl;
		if(kk){
			if(tree[no].size()){
				pair<int,int> ma=tree[no].top();
				tree[no].pop();
				tree[no].push(max(ma,x));
				 ma=tree2[no].top();
				tree2[no].pop();
				tree2[no].push(max(ma,{-x.a,x.b}));
			}
			else{
				tree[no].push(x);

				tree2[no].push({-x.a,x.b});

			}
			return ;
		}
		tree[no].push(x);

		tree2[no].push({-x.a,x.b});


	}
	else{
		int mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,x,st);
		update(no*2+2,mid+1,r,aa,bb,x,st);
	}
}
void update2(int no,int l,int r,int aa,int bb,int x,int st){
/*	if(no==0){
		cout<<aa<<":"<<bb<<":"<<x<<endl;
	}*/
	
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		//cout<<l<<",,"<<r<<endl;
		tree3[no][0]=min(tree3[no][0],x);
		tree3[no][1]=max(tree3[no][1],x);
/*		if(kk){
			if(tree[no].size()){
				pair<int,int> ma=tree[no].top();
				tree[no].pop();
				tree[no].push(max(ma,x));
				 ma=tree2[no].top();
				tree2[no].pop();
				tree2[no].push(max(ma,{-x.a,x.b}));
			}
			else{
				tree[no].push(x);

				tree2[no].push({-x.a,x.b});

			}
			return ;
		}
		tree[no].push(x);

		tree2[no].push({-x.a,x.b});
*/

	}
	else{
		int mid=(l+r)/2;
		update2(no*2+1,l,mid,aa,bb,x,st);
		update2(no*2+2,mid+1,r,aa,bb,x,st);
	}
}
int query(int no,int l,int r,int i){
	int cur=0;
	while(tree[no].size()){
		if(vis[(tree[no].top()).b]){
			tree[no].pop();

		}
		else{
			break;
		}
	}
	while(tree2[no].size()){
		if(vis[(tree2[no].top()).b]){
			tree2[no].pop();
			
		}
		else{
			break;
		}
	}

	if(tree[no].size()){
		//cout<<l<<","<<r<<","<<yy[i].a<<endl;
		cur=max(cur,abs((tree[no].top()).a-yy[i].a));
		
		cur=max(cur,abs(-(tree2[no].top()).a-yy[i].a));
	}
	if(l<r){
		int mid=(l+r)/2;
		if(i<=mid){
			cur=max(cur,query(no*2+1,l,mid,i));
		}
		else{
			cur=max(cur,query(no*2+2,mid+1,r,i));
		}
	}
	return cur;

}
int query2(int no,int l,int r,int i){
	int cur=0;
	//cout<<l<<"<"<<r<<"<"<<yy[i].a<<"<"<<tree3[no][0]<<"<"<<tree3[no][1]<<endl;
	cur=max(cur,yy[i].a-tree3[no][0]);
	cur=max(cur,tree3[no][1]-yy[i].a);
	if(l<r){
		int mid=(l+r)/2;
		if(i<=mid){
			cur=max(cur,query2(no*2+1,l,mid,i));
		}
		else{
			cur=max(cur,query2(no*2+2,mid+1,r,i));
		}
	}
	return cur;

}
void add(int i,int aa,int bb,int st){
	int mid=(aa+bb)/2;
	if(kk==1){
		if(st==1){
			//cout<<aa<<","<<bb<<endl;
		//	xx[{i,{aa,mid}}]=ne;
		
			pair<int,int> ind=solve(aa,mid);

			update2(0,0,nn-1,ind.a,ind.b,aa,0);
			//ne++;
			//xx[{i,{mid+1,bb}}]=ne;
			ind=solve(mid+1,bb);
			update2(0,0,nn-1,ind.a,ind.b,bb,0);
			//ne++;
		}
		return ;
	}
	if(st==1){
		xx[{i,{aa,mid}}]=ne;
		
		pair<int,int> ind=solve(aa,mid);

		update(0,0,nn-1,ind.a,ind.b,{aa,ne},0);
		ne++;
		xx[{i,{mid+1,bb}}]=ne;
		ind=solve(mid+1,bb);
		update(0,0,nn-1,ind.a,ind.b,{bb,ne},1);
		ne++;
	}
	else{
		vis[xx[{i,{aa,mid}}]]=1;
		vis[xx[{i,{mid+1,bb}}]]=1;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k>>q;

	vector<pair<pair<int,int>,pair<int,int>>> cur;
	vector<pair<int,int>> zz5;
	for(int i=0;i<n;i++){
		int x,aa,bb,tt;
		cin>>x>>tt>>aa>>bb;
		ss[x]++;
		tt--;
		if(aa!=1){
			kk=0;
		}
		cur.pb({{aa,-1},{x,tt}});
		cur.pb({{bb,1},{x,tt}});
	//	pre[tt].insert(x);
		zz5.pb({tt,x});
	}
	
	for(int i=0;i<q;i++){
		int x,aa;
		cin>>x>>aa;
		ss[x]++;
		cur.pb({{aa,0},{x,i}});
		ss3[x]++;
		/*if(kk){
			//pre[aa].insert(x);
		}*/
	}
	if(kk){
		for(auto j:zz5){
			pre[j.a].insert(j.b);
		}
		for(int i=0;i<4*ss.size()+10;i++){
			tree3[i][0]=1e8;
			tree3[i][1]=0;
		}
	}



	sort(cur.begin(),cur.end());
	int ind5=-1;
	
	ss[-2e8]++;
	
	ss[2e8]++;
	for(auto j:ss){
		ind5++;
		ss2[j.a]=ind5;
		//yy.pb({j.a,ind5});
	}
	ind5=-1;
	for(auto j:ss3){
		ind5++;
		ss4[j.a]=ind5;
		yy.pb({j.a,ind5});
	}
	nn=yy.size();
	//sort(cur.begin(),cur.end());
	/*for(auto j:yy){
		cout<<j.a<<",";
	}
	cout<<endl;*/
	//cout<<kk<<endl;
	for(int i=0;i<k;i++){
		pre[i].insert(-2e8);
		pre2[i][-2e8]++;
		pre[i].insert(2e8);
		pre2[i][2e8]++;
		//if(kk==0){
		/*if(kk==0){
			add(i,-2e8,2e8,1);
		}*/

	//	xx[{i,{-2e8,2e8}}]=;
	//	update(0,0,nn-1,0,nn-1);
	}

	for(int i=0;i<k;i++){
		vector<int> xx;
		for(auto j:pre[i]){
			xx.pb(j);
		}
	/*	for(auto j:xx){
			cout<<j<<".";
		}
		cout<<endl;*/
		for(int j=0;j+1<xx.size();j++){
			add(i,xx[j],xx[j+1],1);
			//cout<<i<<":"<<xx[j]<<":"<<xx[j+1]<<endl;
		}
	}

	for(auto j:cur){
		if(j.a.b==-1){
			//add
			/*if(kk){
				continue;
			}*/
			//continue;
			if(pre2[j.b.b].find(j.b.a)!=pre2[j.b.b].end()){
				if(pre2[j.b.b][j.b.a]>0){
					pre2[j.b.b][j.b.a]++;
					continue;
				}
			}
			//else{
				pre2[j.b.b][j.b.a]++;
				if(kk){
					continue;
				}
				int re=*(pre[j.b.b].lower_bound(j.b.a));
				auto jj=pre[j.b.b].lower_bound(j.b.a);
				jj--;
				int le=*jj;
				pre[j.b.b].insert(j.b.a);
				add(j.b.b,le,re,0);
				add(j.b.b,le,j.b.a,1);
				add(j.b.b,j.b.a,re,1);
			//}
		}
		else if(j.a.b==1){
			//remove 
			/*if(kk){




				continue;
			}*/
			//continue;
			pre2[j.b.b][j.b.a]--;
			if(pre2[j.b.b][j.b.a]==0){
				//cout<<11<<endl;
				pre[j.b.b].erase(j.b.a);
				int re=*(pre[j.b.b].lower_bound(j.b.a));
				auto jj=pre[j.b.b].lower_bound(j.b.a);
				jj--;
				int le=*jj;
				add(j.b.b,le,j.b.a,0);
				add(j.b.b,j.b.a,re,0);
				add(j.b.b,le,re,1);
				
			}
		}
		else{
			//cout<<j.b.a<<":"<<j.b.b<<endl;
			if(kk){
				int ans2=query2(0,0,nn-1,ss4[j.b.a]);
				if(ans2>1e8){
					ans2=-1;
				}
				ans[j.b.b]=ans2;
				continue;
			}
			int ans2=query(0,0,nn-1,ss4[j.b.a]);
			if(ans2>1e8){
				ans2=-1;
			}
			ans[j.b.b]=ans2;
		}
	}
	for(int i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}
	/*for(int i=0;i<cur.size();i++){
		cur[i].b.a=ss2[cur[i].b.a];
	}*/





	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:241:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  241 |   for(int i=0;i<4*ss.size()+10;i++){
      |               ~^~~~~~~~~~~~~~~
new_home.cpp:296:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  296 |   for(int j=0;j+1<xx.size();j++){
      |               ~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 128592 KB Output is correct
2 Correct 113 ms 128684 KB Output is correct
3 Correct 77 ms 128580 KB Output is correct
4 Correct 78 ms 128684 KB Output is correct
5 Correct 83 ms 128696 KB Output is correct
6 Correct 94 ms 129096 KB Output is correct
7 Correct 76 ms 129120 KB Output is correct
8 Correct 80 ms 129228 KB Output is correct
9 Correct 85 ms 129144 KB Output is correct
10 Correct 80 ms 129120 KB Output is correct
11 Correct 80 ms 129088 KB Output is correct
12 Correct 81 ms 129072 KB Output is correct
13 Correct 78 ms 129060 KB Output is correct
14 Correct 82 ms 129028 KB Output is correct
15 Correct 74 ms 129124 KB Output is correct
16 Correct 83 ms 129188 KB Output is correct
17 Correct 89 ms 129112 KB Output is correct
18 Correct 86 ms 129328 KB Output is correct
19 Correct 74 ms 129172 KB Output is correct
20 Correct 112 ms 129192 KB Output is correct
21 Correct 83 ms 128840 KB Output is correct
22 Correct 93 ms 129108 KB Output is correct
23 Correct 76 ms 129236 KB Output is correct
24 Correct 79 ms 129232 KB Output is correct
25 Correct 96 ms 129192 KB Output is correct
26 Correct 89 ms 129124 KB Output is correct
27 Correct 79 ms 128964 KB Output is correct
28 Correct 78 ms 129044 KB Output is correct
29 Correct 77 ms 129172 KB Output is correct
30 Correct 132 ms 129044 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 128592 KB Output is correct
2 Correct 113 ms 128684 KB Output is correct
3 Correct 77 ms 128580 KB Output is correct
4 Correct 78 ms 128684 KB Output is correct
5 Correct 83 ms 128696 KB Output is correct
6 Correct 94 ms 129096 KB Output is correct
7 Correct 76 ms 129120 KB Output is correct
8 Correct 80 ms 129228 KB Output is correct
9 Correct 85 ms 129144 KB Output is correct
10 Correct 80 ms 129120 KB Output is correct
11 Correct 80 ms 129088 KB Output is correct
12 Correct 81 ms 129072 KB Output is correct
13 Correct 78 ms 129060 KB Output is correct
14 Correct 82 ms 129028 KB Output is correct
15 Correct 74 ms 129124 KB Output is correct
16 Correct 83 ms 129188 KB Output is correct
17 Correct 89 ms 129112 KB Output is correct
18 Correct 86 ms 129328 KB Output is correct
19 Correct 74 ms 129172 KB Output is correct
20 Correct 112 ms 129192 KB Output is correct
21 Correct 83 ms 128840 KB Output is correct
22 Correct 93 ms 129108 KB Output is correct
23 Correct 76 ms 129236 KB Output is correct
24 Correct 79 ms 129232 KB Output is correct
25 Correct 96 ms 129192 KB Output is correct
26 Correct 89 ms 129124 KB Output is correct
27 Correct 79 ms 128964 KB Output is correct
28 Correct 78 ms 129044 KB Output is correct
29 Correct 77 ms 129172 KB Output is correct
30 Correct 132 ms 129044 KB Output is correct
31 Correct 2588 ms 242280 KB Output is correct
32 Correct 144 ms 134488 KB Output is correct
33 Correct 1886 ms 206744 KB Output is correct
34 Correct 2710 ms 242936 KB Output is correct
35 Correct 2356 ms 231660 KB Output is correct
36 Correct 2025 ms 206152 KB Output is correct
37 Correct 1524 ms 212072 KB Output is correct
38 Correct 1310 ms 196188 KB Output is correct
39 Correct 1040 ms 199172 KB Output is correct
40 Correct 939 ms 195708 KB Output is correct
41 Correct 2405 ms 205048 KB Output is correct
42 Correct 2620 ms 207972 KB Output is correct
43 Correct 150 ms 134516 KB Output is correct
44 Correct 2389 ms 203700 KB Output is correct
45 Correct 2320 ms 197088 KB Output is correct
46 Correct 1857 ms 193724 KB Output is correct
47 Correct 868 ms 198260 KB Output is correct
48 Correct 861 ms 197480 KB Output is correct
49 Correct 1046 ms 201756 KB Output is correct
50 Correct 1534 ms 212908 KB Output is correct
51 Correct 1065 ms 196556 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3490 ms 295000 KB Output is correct
2 Correct 2852 ms 282600 KB Output is correct
3 Correct 3128 ms 340388 KB Output is correct
4 Correct 3482 ms 302672 KB Output is correct
5 Correct 2838 ms 282204 KB Output is correct
6 Correct 2863 ms 282640 KB Output is correct
7 Correct 2923 ms 340240 KB Output is correct
8 Correct 3206 ms 302836 KB Output is correct
9 Correct 3415 ms 289148 KB Output is correct
10 Correct 3130 ms 282944 KB Output is correct
11 Correct 1790 ms 280816 KB Output is correct
12 Correct 1988 ms 282392 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4451 ms 284368 KB Output is correct
2 Correct 451 ms 151520 KB Output is correct
3 Correct 4190 ms 282084 KB Output is correct
4 Correct 3334 ms 337660 KB Output is correct
5 Correct 3917 ms 292484 KB Output is correct
6 Correct 3804 ms 300112 KB Output is correct
7 Correct 4277 ms 282052 KB Output is correct
8 Correct 4094 ms 283388 KB Output is correct
9 Correct 3092 ms 340216 KB Output is correct
10 Correct 3478 ms 298088 KB Output is correct
11 Correct 3892 ms 287212 KB Output is correct
12 Correct 4024 ms 283904 KB Output is correct
13 Correct 1773 ms 280576 KB Output is correct
14 Correct 1756 ms 279388 KB Output is correct
15 Correct 1994 ms 281744 KB Output is correct
16 Correct 2259 ms 283312 KB Output is correct
17 Correct 2052 ms 281268 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 128592 KB Output is correct
2 Correct 113 ms 128684 KB Output is correct
3 Correct 77 ms 128580 KB Output is correct
4 Correct 78 ms 128684 KB Output is correct
5 Correct 83 ms 128696 KB Output is correct
6 Correct 94 ms 129096 KB Output is correct
7 Correct 76 ms 129120 KB Output is correct
8 Correct 80 ms 129228 KB Output is correct
9 Correct 85 ms 129144 KB Output is correct
10 Correct 80 ms 129120 KB Output is correct
11 Correct 80 ms 129088 KB Output is correct
12 Correct 81 ms 129072 KB Output is correct
13 Correct 78 ms 129060 KB Output is correct
14 Correct 82 ms 129028 KB Output is correct
15 Correct 74 ms 129124 KB Output is correct
16 Correct 83 ms 129188 KB Output is correct
17 Correct 89 ms 129112 KB Output is correct
18 Correct 86 ms 129328 KB Output is correct
19 Correct 74 ms 129172 KB Output is correct
20 Correct 112 ms 129192 KB Output is correct
21 Correct 83 ms 128840 KB Output is correct
22 Correct 93 ms 129108 KB Output is correct
23 Correct 76 ms 129236 KB Output is correct
24 Correct 79 ms 129232 KB Output is correct
25 Correct 96 ms 129192 KB Output is correct
26 Correct 89 ms 129124 KB Output is correct
27 Correct 79 ms 128964 KB Output is correct
28 Correct 78 ms 129044 KB Output is correct
29 Correct 77 ms 129172 KB Output is correct
30 Correct 132 ms 129044 KB Output is correct
31 Correct 2588 ms 242280 KB Output is correct
32 Correct 144 ms 134488 KB Output is correct
33 Correct 1886 ms 206744 KB Output is correct
34 Correct 2710 ms 242936 KB Output is correct
35 Correct 2356 ms 231660 KB Output is correct
36 Correct 2025 ms 206152 KB Output is correct
37 Correct 1524 ms 212072 KB Output is correct
38 Correct 1310 ms 196188 KB Output is correct
39 Correct 1040 ms 199172 KB Output is correct
40 Correct 939 ms 195708 KB Output is correct
41 Correct 2405 ms 205048 KB Output is correct
42 Correct 2620 ms 207972 KB Output is correct
43 Correct 150 ms 134516 KB Output is correct
44 Correct 2389 ms 203700 KB Output is correct
45 Correct 2320 ms 197088 KB Output is correct
46 Correct 1857 ms 193724 KB Output is correct
47 Correct 868 ms 198260 KB Output is correct
48 Correct 861 ms 197480 KB Output is correct
49 Correct 1046 ms 201756 KB Output is correct
50 Correct 1534 ms 212908 KB Output is correct
51 Correct 1065 ms 196556 KB Output is correct
52 Correct 1265 ms 215560 KB Output is correct
53 Correct 1316 ms 211152 KB Output is correct
54 Correct 1919 ms 232468 KB Output is correct
55 Correct 1966 ms 214588 KB Output is correct
56 Correct 1745 ms 214716 KB Output is correct
57 Correct 2248 ms 213864 KB Output is correct
58 Correct 1951 ms 215524 KB Output is correct
59 Correct 1779 ms 215040 KB Output is correct
60 Correct 2241 ms 215180 KB Output is correct
61 Correct 203 ms 151240 KB Output is correct
62 Correct 1255 ms 214932 KB Output is correct
63 Correct 1648 ms 225376 KB Output is correct
64 Correct 1816 ms 229428 KB Output is correct
65 Correct 2142 ms 230356 KB Output is correct
66 Correct 2472 ms 213568 KB Output is correct
67 Correct 769 ms 170680 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 128592 KB Output is correct
2 Correct 113 ms 128684 KB Output is correct
3 Correct 77 ms 128580 KB Output is correct
4 Correct 78 ms 128684 KB Output is correct
5 Correct 83 ms 128696 KB Output is correct
6 Correct 94 ms 129096 KB Output is correct
7 Correct 76 ms 129120 KB Output is correct
8 Correct 80 ms 129228 KB Output is correct
9 Correct 85 ms 129144 KB Output is correct
10 Correct 80 ms 129120 KB Output is correct
11 Correct 80 ms 129088 KB Output is correct
12 Correct 81 ms 129072 KB Output is correct
13 Correct 78 ms 129060 KB Output is correct
14 Correct 82 ms 129028 KB Output is correct
15 Correct 74 ms 129124 KB Output is correct
16 Correct 83 ms 129188 KB Output is correct
17 Correct 89 ms 129112 KB Output is correct
18 Correct 86 ms 129328 KB Output is correct
19 Correct 74 ms 129172 KB Output is correct
20 Correct 112 ms 129192 KB Output is correct
21 Correct 83 ms 128840 KB Output is correct
22 Correct 93 ms 129108 KB Output is correct
23 Correct 76 ms 129236 KB Output is correct
24 Correct 79 ms 129232 KB Output is correct
25 Correct 96 ms 129192 KB Output is correct
26 Correct 89 ms 129124 KB Output is correct
27 Correct 79 ms 128964 KB Output is correct
28 Correct 78 ms 129044 KB Output is correct
29 Correct 77 ms 129172 KB Output is correct
30 Correct 132 ms 129044 KB Output is correct
31 Correct 2588 ms 242280 KB Output is correct
32 Correct 144 ms 134488 KB Output is correct
33 Correct 1886 ms 206744 KB Output is correct
34 Correct 2710 ms 242936 KB Output is correct
35 Correct 2356 ms 231660 KB Output is correct
36 Correct 2025 ms 206152 KB Output is correct
37 Correct 1524 ms 212072 KB Output is correct
38 Correct 1310 ms 196188 KB Output is correct
39 Correct 1040 ms 199172 KB Output is correct
40 Correct 939 ms 195708 KB Output is correct
41 Correct 2405 ms 205048 KB Output is correct
42 Correct 2620 ms 207972 KB Output is correct
43 Correct 150 ms 134516 KB Output is correct
44 Correct 2389 ms 203700 KB Output is correct
45 Correct 2320 ms 197088 KB Output is correct
46 Correct 1857 ms 193724 KB Output is correct
47 Correct 868 ms 198260 KB Output is correct
48 Correct 861 ms 197480 KB Output is correct
49 Correct 1046 ms 201756 KB Output is correct
50 Correct 1534 ms 212908 KB Output is correct
51 Correct 1065 ms 196556 KB Output is correct
52 Correct 3490 ms 295000 KB Output is correct
53 Correct 2852 ms 282600 KB Output is correct
54 Correct 3128 ms 340388 KB Output is correct
55 Correct 3482 ms 302672 KB Output is correct
56 Correct 2838 ms 282204 KB Output is correct
57 Correct 2863 ms 282640 KB Output is correct
58 Correct 2923 ms 340240 KB Output is correct
59 Correct 3206 ms 302836 KB Output is correct
60 Correct 3415 ms 289148 KB Output is correct
61 Correct 3130 ms 282944 KB Output is correct
62 Correct 1790 ms 280816 KB Output is correct
63 Correct 1988 ms 282392 KB Output is correct
64 Correct 4451 ms 284368 KB Output is correct
65 Correct 451 ms 151520 KB Output is correct
66 Correct 4190 ms 282084 KB Output is correct
67 Correct 3334 ms 337660 KB Output is correct
68 Correct 3917 ms 292484 KB Output is correct
69 Correct 3804 ms 300112 KB Output is correct
70 Correct 4277 ms 282052 KB Output is correct
71 Correct 4094 ms 283388 KB Output is correct
72 Correct 3092 ms 340216 KB Output is correct
73 Correct 3478 ms 298088 KB Output is correct
74 Correct 3892 ms 287212 KB Output is correct
75 Correct 4024 ms 283904 KB Output is correct
76 Correct 1773 ms 280576 KB Output is correct
77 Correct 1756 ms 279388 KB Output is correct
78 Correct 1994 ms 281744 KB Output is correct
79 Correct 2259 ms 283312 KB Output is correct
80 Correct 2052 ms 281268 KB Output is correct
81 Correct 1265 ms 215560 KB Output is correct
82 Correct 1316 ms 211152 KB Output is correct
83 Correct 1919 ms 232468 KB Output is correct
84 Correct 1966 ms 214588 KB Output is correct
85 Correct 1745 ms 214716 KB Output is correct
86 Correct 2248 ms 213864 KB Output is correct
87 Correct 1951 ms 215524 KB Output is correct
88 Correct 1779 ms 215040 KB Output is correct
89 Correct 2241 ms 215180 KB Output is correct
90 Correct 203 ms 151240 KB Output is correct
91 Correct 1255 ms 214932 KB Output is correct
92 Correct 1648 ms 225376 KB Output is correct
93 Correct 1816 ms 229428 KB Output is correct
94 Correct 2142 ms 230356 KB Output is correct
95 Correct 2472 ms 213568 KB Output is correct
96 Correct 769 ms 170680 KB Output is correct
97 Execution timed out 5095 ms 528124 KB Time limit exceeded
98 Halted 0 ms 0 KB -