oj.uz

Submission #804310

# Submission time Handle Problem Language Result Execution time Memory
804310 2023-08-03T07:57:24 Z kshitij_sodani Radio Towers (IOI22_towers) C++17
60 / 100
 4000 ms 84684 KB 
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#include "towers.h"

#include <vector>
int st=0;
int n;
vector<int> it;
int tree[4*210001][2];

void build(int no,int l,int r){
	if(l==r){
		tree[no][0]=it[l];
		tree[no][1]=it[l];
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no][0]=min(tree[no*2+1][0],tree[no*2+2][0]);
		tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
	}
}
int query(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return 1e9+1;
	}
	if(aa<=l and r<=bb){
		return tree[no][0];
	}
	int mid=(l+r)/2;
	return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
int query2(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return -1;
	}
	if(aa<=l and r<=bb){
		return tree[no][1];
	}
	int mid=(l+r)/2;
	return max(query2(no*2+1,l,mid,aa,bb),query2(no*2+2,mid+1,r,aa,bb));
}
vector<int> mm;

void init(int nn, vector<int> ita) {
	n=nn;
	it=ita;
	st=0;
	build(0,0,n-1);
	
}
int le[110001];
int re2[110001];
int cc[110001][20];
int dd[110001][20];
int val[110001];
int tree2[4*200001];
int tree3[4*200001];

void build2(int no,int l,int r){
	if(l==r){
		tree2[no]=le[l];
		tree3[no]=re2[l];
	}
	else{
		int mid=(l+r)/2;
		build2(no*2+1,l,mid);
		build2(no*2+2,mid+1,r);
		tree2[no]=min(tree2[no*2+1],tree2[no*2+2]);
		tree3[no]=max(tree3[no*2+1],tree3[no*2+2]);
	}
}
int find(int no,int l,int r,int aa,int bb,int x){
	//find first with val less than x
	if(r<aa or l>bb or aa>bb){
		return -1;
	}
	if(l==r){
		if(tree2[no]<x){
			return l;
		}
		return -1;
	}
	if(tree2[no]>=x){
		return -1;
	}
	int mid=(l+r)/2;
	int xx=find(no*2+1,l,mid,aa,bb,x);
	if(xx>=0){
		return xx;
	}
	return find(no*2+2,mid+1,r,aa,bb,x);
}
int find2(int no,int l,int r,int aa,int bb,int x){
	//find first with val less than x
	if(r<aa or l>bb or aa>bb){
		return -1;
	}
	if(l==r){
		if(tree3[no]>x){
			return l;
		}
		return -1;
	}
	if(tree3[no]<=x){
		return -1;
	}
	int mid=(l+r)/2;
	int xx=find2(no*2+2,mid+1,r,aa,bb,x);
	if(xx>=0){
		return xx;
	}
	return find2(no*2+1,l,mid,aa,bb,x);
}
vector<int> adj[110001];
set<int> xa;
vector<pair<int,int>> yy;
int cot[110001*500];
int ll[110001*500];
int rr[110001*500];
int ba[110001];
int ne=0;
int update(int no,int l,int r,int i,int x){
	if(l==r){
		int sta=ne;
		ne++;
		ll[sta]=-1;
		rr[sta]=-1;
		cot[sta]=cot[no]+x;
		return sta;
	}
	else{
		int mid=(l+r)/2;
		int sta=ne;
		ne++;
		if(i<=mid){
			rr[sta]=rr[no];
			if(ll[no]==-1){
				ll[no]=ne;
				ne++;
				ll[ll[no]]=-1;
				rr[ll[no]]=-1;
				cot[ll[no]]=0;
			}
			ll[sta]=update(ll[no],l,mid,i,x);
		}
		else{
			ll[sta]=ll[no];

			if(rr[no]==-1){
				rr[no]=ne;
				ne++;
				rr[rr[no]]=-1;
				ll[rr[no]]=-1;
				cot[rr[no]]=0;
			}
			rr[sta]=update(rr[no],mid+1,r,i,x);
		}
		cot[sta]=0;
		if(ll[sta]>=0){
			cot[sta]+=cot[ll[sta]];
		}
		if(rr[sta]>=0){
			cot[sta]+=cot[rr[sta]];
		}
		return sta;
	}
}
int query5(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return 0;
	}
	if(aa<=l and r<=bb){
		return cot[no];
	}
	int mid=(l+r)/2;
	int su=0;
	if(ll[no]>=0){
		su+=query5(ll[no],l,mid,aa,bb);
	}
	if(rr[no]>=0){
		su+=query5(rr[no],mid+1,r,aa,bb);
	}
	return su;
}	
void dfs(int no,int par=-1){
	if(par==-1){
		par=ne;
		ll[ne]=-1;
		rr[ne]=-1;
		ne++;
	}
	else{
	}
	if(par!=-1){
		ba[no]=update(par,0,n-1,val[no],1);
	}
	else{
		ba[no]=par;

	}
	for(auto j:adj[no]){
		dfs(j,ba[no]);
	}
}
vector<int> adj2[110001];
int ba2[110001];
void dfs2(int no,int par=-1){
	if(par==-1){
		par=ne;
		ll[ne]=-1;
		rr[ne]=-1;
		ne++;
	}
	else{
	}
	if(par!=-1){
		ba2[no]=update(par,0,n-1,val[no],1);
	}
	else{
		ba2[no]=par;
	}
	for(auto j:adj2[no]){
		dfs2(j,ba2[no]);
	}
}
void rec(int l,int r){
	mm.clear();
	vector<pair<llo,llo>> ss;
	for(int i=r;i>=l;i--){
		while(ss.size()){
			if(ss.back().a<=it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		re2[i]=n;
		if(ss.size()){
			re2[i]=ss.back().b;
		}
		ss.pb({it[i],i});
	}
	ss.clear();
	for(int i=l;i<=r;i++){
		while(ss.size()){
			if(ss.back().a<it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		le[i]=-1;
		if(ss.size()){
			le[i]=ss.back().b;
		}
		ss.pb({it[i],i});
	}
	for(int i=0;i<n;i++){
		int x=it[i]-query(0,0,n-1,le[i]+1,i);
		int y=it[i]-query(0,0,n-1,i,re2[i]-1);
		val[i]=min(x,y);
		xa.insert(val[i]);
		mm.pb(min(x,y));
	}
	int ind7=0;
	map<int,int> kk;
	for(auto j:xa){
		kk[j]=ind7;
		yy.pb({j,ind7});
		ind7++;
	}
	for(int i=0;i<n;i++){
		val[i]=kk[val[i]];
	}

	for(int i=0;i<n;i++){
		cc[i][0]=le[i];
		dd[i][0]=re2[i];
		adj[dd[i][0]].pb(i);
		if(cc[i][0]==-1){
			adj2[n].pb(i);
		}
		else{
			adj2[cc[i][0]].pb(i);
		}
	//	cout<<i<<":"<<le[i]<<endl;
	//	cout<<i<<":"<<re2[i]<<endl;
		if(re2[i]==n){
			dd[i][0]=-1;
		}
	}
	dfs(n);
	dfs2(n);

	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(cc[i][j-1]==-1){
				cc[i][j]=-1;
			}
			else{
				cc[i][j]=cc[cc[i][j-1]][j-1];
			}
		}
	}
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(dd[i][j-1]==-1){
				dd[i][j]=-1;
			}
			else{
				dd[i][j]=dd[dd[i][j-1]][j-1];
			}
		}
	}
	build2(0,0,n-1);
	sort(mm.begin(),mm.end());

}

int max_towers(int l, int r, int d) {
	if(st==0){
		rec(0,n-1);
		st=1;
	}
	int de=yy.size();
	for(int j=19;j>=0;j--){
		if(de-(1<<j)>=0){
			if(yy[de-(1<<j)].a>=d){
				de-=(1<<j);
			}
		}	
	}
	if(de==yy.size()){
		return 1;
	}
	llo low=mm.size();
	llo su=0;
	for(int i=l;i<=r;i++){
		if(val[i]>=de){
			su++;
		}
	}
	int ind=find(0,0,n-1,l,r,l);
	int ind2=ind;
	for(int j=19;j>=0;j--){
		if(dd[ind2][j]<=r and dd[ind2][j]>=0){
			ind2=dd[ind2][j];
		}
	}
	//vector<llo> ss;
	int ind3=-1;
	if(query(0,0,n-1,l,ind-1)>it[ind]-d){
		ind3=ind;
		for(int j=19;j>=0;j--){
			if(dd[ind][j]<=r and dd[ind][j]>=0){
				if(query(0,0,n-1,l,dd[ind][j]-1)>it[dd[ind][j]]-d){
					ind=dd[ind][j];
				}
			}
		}		
		llo zot=query5(ba[ind3],0,n-1,de,n-1);
		zot-=query5(ba[re2[ind]],0,n-1,de,n-1);
		su-=zot;
		//ss.pb(ind);

	}
	pair<int,int> ll={ind3,ind};
	//from ind3 to ind
	ind=-1;
	ind=find2(0,0,n-1,l,r,r);

	ind3=-1;
	if(query(0,0,n-1,ind+1,r)<=it[ind]-d){
	}
	else{
		ind3=ind;
		for(int j=19;j>=0;j--){
			if(cc[ind][j]>=l){
				if(query(0,0,n-1,cc[ind][j]+1,r)>it[cc[ind][j]]-d){
					ind=cc[ind][j];
				}
			}
		}
		llo zot=query5(ba2[ind3],0,n-1,de,n-1);
		if(cc[ind][0]==-1){
			zot-=query5(ba2[n],0,n-1,de,n-1);
		}
		else{
			zot-=query5(ba2[cc[ind][0]],0,n-1,de,n-1);
		}
		su-=zot;

	}
	pair<int,int> rr={ind3,ind};
	if(ll.a>=0 and rr.a>=0){
		if(rr.b==ind2 and ll.b==ind2){
			if(val[rr.b]>=de){
				su++;
			}
		}
	}
	su++;
	return su;
}

Compilation message

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:341:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  341 |  if(de==yy.size()){
      |     ~~^~~~~~~~~~~
towers.cpp:344:6: warning: unused variable 'low' [-Wunused-variable]
  344 |  llo low=mm.size();
      |      ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1295 ms 47716 KB Output is correct
2 Correct 3761 ms 80140 KB Output is correct
3 Correct 3588 ms 80212 KB Output is correct
4 Correct 829 ms 80448 KB Output is correct
5 Correct 743 ms 80464 KB Output is correct
6 Correct 3581 ms 80440 KB Output is correct
7 Correct 613 ms 80468 KB Output is correct
8 Correct 2 ms 5456 KB Output is correct
9 Correct 4 ms 6608 KB Output is correct
10 Correct 4 ms 6736 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5760 KB Output is correct
2 Correct 6 ms 6608 KB Output is correct
3 Correct 5 ms 6608 KB Output is correct
4 Correct 4 ms 6736 KB Output is correct
5 Correct 4 ms 6924 KB Output is correct
6 Correct 4 ms 6736 KB Output is correct
7 Correct 7 ms 6864 KB Output is correct
8 Correct 4 ms 6756 KB Output is correct
9 Correct 4 ms 6736 KB Output is correct
10 Correct 4 ms 6608 KB Output is correct
11 Correct 4 ms 6608 KB Output is correct
12 Correct 3 ms 5456 KB Output is correct
13 Correct 4 ms 6608 KB Output is correct
14 Correct 5 ms 6736 KB Output is correct
15 Correct 4 ms 6608 KB Output is correct
16 Correct 4 ms 6736 KB Output is correct
17 Correct 5 ms 6736 KB Output is correct
18 Correct 4 ms 6736 KB Output is correct
19 Correct 4 ms 6608 KB Output is correct
20 Correct 4 ms 6608 KB Output is correct
21 Correct 4 ms 6736 KB Output is correct
22 Correct 5 ms 6748 KB Output is correct
23 Correct 4 ms 6736 KB Output is correct
24 Correct 4 ms 6608 KB Output is correct
25 Correct 3 ms 5968 KB Output is correct
26 Correct 4 ms 6736 KB Output is correct
27 Correct 5 ms 6608 KB Output is correct
28 Correct 4 ms 6736 KB Output is correct
29 Correct 4 ms 6736 KB Output is correct
30 Correct 5 ms 6736 KB Output is correct
31 Correct 4 ms 6736 KB Output is correct
32 Correct 4 ms 6664 KB Output is correct
33 Correct 4 ms 6736 KB Output is correct
34 Correct 4 ms 6608 KB Output is correct
35 Correct 4 ms 6736 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5760 KB Output is correct
2 Correct 6 ms 6608 KB Output is correct
3 Correct 5 ms 6608 KB Output is correct
4 Correct 4 ms 6736 KB Output is correct
5 Correct 4 ms 6924 KB Output is correct
6 Correct 4 ms 6736 KB Output is correct
7 Correct 7 ms 6864 KB Output is correct
8 Correct 4 ms 6756 KB Output is correct
9 Correct 4 ms 6736 KB Output is correct
10 Correct 4 ms 6608 KB Output is correct
11 Correct 4 ms 6608 KB Output is correct
12 Correct 3 ms 5456 KB Output is correct
13 Correct 4 ms 6608 KB Output is correct
14 Correct 5 ms 6736 KB Output is correct
15 Correct 4 ms 6608 KB Output is correct
16 Correct 4 ms 6736 KB Output is correct
17 Correct 5 ms 6736 KB Output is correct
18 Correct 4 ms 6736 KB Output is correct
19 Correct 4 ms 6608 KB Output is correct
20 Correct 4 ms 6608 KB Output is correct
21 Correct 4 ms 6736 KB Output is correct
22 Correct 5 ms 6748 KB Output is correct
23 Correct 4 ms 6736 KB Output is correct
24 Correct 4 ms 6608 KB Output is correct
25 Correct 3 ms 5968 KB Output is correct
26 Correct 4 ms 6736 KB Output is correct
27 Correct 5 ms 6608 KB Output is correct
28 Correct 4 ms 6736 KB Output is correct
29 Correct 4 ms 6736 KB Output is correct
30 Correct 5 ms 6736 KB Output is correct
31 Correct 4 ms 6736 KB Output is correct
32 Correct 4 ms 6664 KB Output is correct
33 Correct 4 ms 6736 KB Output is correct
34 Correct 4 ms 6608 KB Output is correct
35 Correct 4 ms 6736 KB Output is correct
36 Correct 95 ms 51688 KB Output is correct
37 Correct 159 ms 79676 KB Output is correct
38 Correct 148 ms 79440 KB Output is correct
39 Correct 164 ms 84112 KB Output is correct
40 Correct 178 ms 84232 KB Output is correct
41 Correct 162 ms 84072 KB Output is correct
42 Correct 187 ms 84012 KB Output is correct
43 Correct 109 ms 80476 KB Output is correct
44 Correct 100 ms 80496 KB Output is correct
45 Correct 99 ms 78712 KB Output is correct
46 Correct 101 ms 78076 KB Output is correct
47 Correct 165 ms 79592 KB Output is correct
48 Correct 162 ms 84196 KB Output is correct
49 Correct 160 ms 84036 KB Output is correct
50 Correct 106 ms 80456 KB Output is correct
51 Correct 98 ms 80260 KB Output is correct
52 Correct 161 ms 79452 KB Output is correct
53 Correct 162 ms 83944 KB Output is correct
54 Correct 177 ms 83988 KB Output is correct
55 Correct 106 ms 80484 KB Output is correct
56 Correct 98 ms 79812 KB Output is correct
57 Correct 144 ms 77084 KB Output is correct
58 Correct 140 ms 79460 KB Output is correct
59 Correct 150 ms 79584 KB Output is correct
60 Correct 155 ms 84184 KB Output is correct
61 Correct 154 ms 84252 KB Output is correct
62 Correct 192 ms 84068 KB Output is correct
63 Correct 158 ms 84316 KB Output is correct
64 Correct 98 ms 80488 KB Output is correct
65 Correct 94 ms 80440 KB Output is correct
66 Correct 98 ms 78088 KB Output is correct
67 Correct 96 ms 80112 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2326 ms 78992 KB Output is correct
2 Correct 3508 ms 79700 KB Output is correct
3 Correct 3421 ms 79388 KB Output is correct
4 Correct 3597 ms 84032 KB Output is correct
5 Correct 3564 ms 84280 KB Output is correct
6 Correct 3460 ms 84068 KB Output is correct
7 Correct 3566 ms 84684 KB Output is correct
8 Correct 735 ms 80476 KB Output is correct
9 Correct 863 ms 80488 KB Output is correct
10 Correct 3373 ms 79180 KB Output is correct
11 Correct 3336 ms 78904 KB Output is correct
12 Correct 3558 ms 80336 KB Output is correct
13 Correct 510 ms 80476 KB Output is correct
14 Correct 3 ms 5456 KB Output is correct
15 Correct 4 ms 6608 KB Output is correct
16 Correct 5 ms 6736 KB Output is correct
17 Correct 140 ms 79596 KB Output is correct
18 Correct 169 ms 84096 KB Output is correct
19 Correct 165 ms 84004 KB Output is correct
20 Correct 97 ms 80484 KB Output is correct
21 Correct 100 ms 80300 KB Output is correct
22 Correct 143 ms 79548 KB Output is correct
23 Correct 157 ms 83912 KB Output is correct
24 Correct 169 ms 84088 KB Output is correct
25 Correct 96 ms 80372 KB Output is correct
26 Correct 101 ms 79860 KB Output is correct
27 Correct 4 ms 6608 KB Output is correct
28 Correct 4 ms 6736 KB Output is correct
29 Correct 5 ms 6736 KB Output is correct
30 Correct 4 ms 6676 KB Output is correct
31 Correct 4 ms 6608 KB Output is correct
32 Correct 4 ms 6608 KB Output is correct
33 Correct 4 ms 6736 KB Output is correct
34 Correct 4 ms 6736 KB Output is correct
35 Correct 4 ms 6736 KB Output is correct
36 Correct 5 ms 6608 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 820 ms 22056 KB Output is correct
2 Execution timed out 4083 ms 79552 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5760 KB Output is correct
2 Correct 6 ms 6608 KB Output is correct
3 Correct 5 ms 6608 KB Output is correct
4 Correct 4 ms 6736 KB Output is correct
5 Correct 4 ms 6924 KB Output is correct
6 Correct 4 ms 6736 KB Output is correct
7 Correct 7 ms 6864 KB Output is correct
8 Correct 4 ms 6756 KB Output is correct
9 Correct 4 ms 6736 KB Output is correct
10 Correct 4 ms 6608 KB Output is correct
11 Correct 4 ms 6608 KB Output is correct
12 Correct 3 ms 5456 KB Output is correct
13 Correct 4 ms 6608 KB Output is correct
14 Correct 5 ms 6736 KB Output is correct
15 Correct 4 ms 6608 KB Output is correct
16 Correct 4 ms 6736 KB Output is correct
17 Correct 5 ms 6736 KB Output is correct
18 Correct 4 ms 6736 KB Output is correct
19 Correct 4 ms 6608 KB Output is correct
20 Correct 4 ms 6608 KB Output is correct
21 Correct 4 ms 6736 KB Output is correct
22 Correct 5 ms 6748 KB Output is correct
23 Correct 4 ms 6736 KB Output is correct
24 Correct 4 ms 6608 KB Output is correct
25 Correct 3 ms 5968 KB Output is correct
26 Correct 4 ms 6736 KB Output is correct
27 Correct 5 ms 6608 KB Output is correct
28 Correct 4 ms 6736 KB Output is correct
29 Correct 4 ms 6736 KB Output is correct
30 Correct 5 ms 6736 KB Output is correct
31 Correct 4 ms 6736 KB Output is correct
32 Correct 4 ms 6664 KB Output is correct
33 Correct 4 ms 6736 KB Output is correct
34 Correct 4 ms 6608 KB Output is correct
35 Correct 4 ms 6736 KB Output is correct
36 Correct 95 ms 51688 KB Output is correct
37 Correct 159 ms 79676 KB Output is correct
38 Correct 148 ms 79440 KB Output is correct
39 Correct 164 ms 84112 KB Output is correct
40 Correct 178 ms 84232 KB Output is correct
41 Correct 162 ms 84072 KB Output is correct
42 Correct 187 ms 84012 KB Output is correct
43 Correct 109 ms 80476 KB Output is correct
44 Correct 100 ms 80496 KB Output is correct
45 Correct 99 ms 78712 KB Output is correct
46 Correct 101 ms 78076 KB Output is correct
47 Correct 165 ms 79592 KB Output is correct
48 Correct 162 ms 84196 KB Output is correct
49 Correct 160 ms 84036 KB Output is correct
50 Correct 106 ms 80456 KB Output is correct
51 Correct 98 ms 80260 KB Output is correct
52 Correct 161 ms 79452 KB Output is correct
53 Correct 162 ms 83944 KB Output is correct
54 Correct 177 ms 83988 KB Output is correct
55 Correct 106 ms 80484 KB Output is correct
56 Correct 98 ms 79812 KB Output is correct
57 Correct 144 ms 77084 KB Output is correct
58 Correct 140 ms 79460 KB Output is correct
59 Correct 150 ms 79584 KB Output is correct
60 Correct 155 ms 84184 KB Output is correct
61 Correct 154 ms 84252 KB Output is correct
62 Correct 192 ms 84068 KB Output is correct
63 Correct 158 ms 84316 KB Output is correct
64 Correct 98 ms 80488 KB Output is correct
65 Correct 94 ms 80440 KB Output is correct
66 Correct 98 ms 78088 KB Output is correct
67 Correct 96 ms 80112 KB Output is correct
68 Correct 2326 ms 78992 KB Output is correct
69 Correct 3508 ms 79700 KB Output is correct
70 Correct 3421 ms 79388 KB Output is correct
71 Correct 3597 ms 84032 KB Output is correct
72 Correct 3564 ms 84280 KB Output is correct
73 Correct 3460 ms 84068 KB Output is correct
74 Correct 3566 ms 84684 KB Output is correct
75 Correct 735 ms 80476 KB Output is correct
76 Correct 863 ms 80488 KB Output is correct
77 Correct 3373 ms 79180 KB Output is correct
78 Correct 3336 ms 78904 KB Output is correct
79 Correct 3558 ms 80336 KB Output is correct
80 Correct 510 ms 80476 KB Output is correct
81 Correct 3 ms 5456 KB Output is correct
82 Correct 4 ms 6608 KB Output is correct
83 Correct 5 ms 6736 KB Output is correct
84 Correct 140 ms 79596 KB Output is correct
85 Correct 169 ms 84096 KB Output is correct
86 Correct 165 ms 84004 KB Output is correct
87 Correct 97 ms 80484 KB Output is correct
88 Correct 100 ms 80300 KB Output is correct
89 Correct 143 ms 79548 KB Output is correct
90 Correct 157 ms 83912 KB Output is correct
91 Correct 169 ms 84088 KB Output is correct
92 Correct 96 ms 80372 KB Output is correct
93 Correct 101 ms 79860 KB Output is correct
94 Correct 4 ms 6608 KB Output is correct
95 Correct 4 ms 6736 KB Output is correct
96 Correct 5 ms 6736 KB Output is correct
97 Correct 4 ms 6676 KB Output is correct
98 Correct 4 ms 6608 KB Output is correct
99 Correct 4 ms 6608 KB Output is correct
100 Correct 4 ms 6736 KB Output is correct
101 Correct 4 ms 6736 KB Output is correct
102 Correct 4 ms 6736 KB Output is correct
103 Correct 5 ms 6608 KB Output is correct
104 Correct 2432 ms 71488 KB Output is correct
105 Correct 3421 ms 79368 KB Output is correct
106 Correct 3256 ms 79500 KB Output is correct
107 Correct 3553 ms 84160 KB Output is correct
108 Correct 3909 ms 84148 KB Output is correct
109 Correct 3470 ms 84136 KB Output is correct
110 Correct 3598 ms 84340 KB Output is correct
111 Correct 757 ms 80468 KB Output is correct
112 Correct 878 ms 80480 KB Output is correct
113 Correct 3484 ms 79080 KB Output is correct
114 Correct 3333 ms 77156 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1295 ms 47716 KB Output is correct
2 Correct 3761 ms 80140 KB Output is correct
3 Correct 3588 ms 80212 KB Output is correct
4 Correct 829 ms 80448 KB Output is correct
5 Correct 743 ms 80464 KB Output is correct
6 Correct 3581 ms 80440 KB Output is correct
7 Correct 613 ms 80468 KB Output is correct
8 Correct 2 ms 5456 KB Output is correct
9 Correct 4 ms 6608 KB Output is correct
10 Correct 4 ms 6736 KB Output is correct
11 Correct 3 ms 5760 KB Output is correct
12 Correct 6 ms 6608 KB Output is correct
13 Correct 5 ms 6608 KB Output is correct
14 Correct 4 ms 6736 KB Output is correct
15 Correct 4 ms 6924 KB Output is correct
16 Correct 4 ms 6736 KB Output is correct
17 Correct 7 ms 6864 KB Output is correct
18 Correct 4 ms 6756 KB Output is correct
19 Correct 4 ms 6736 KB Output is correct
20 Correct 4 ms 6608 KB Output is correct
21 Correct 4 ms 6608 KB Output is correct
22 Correct 3 ms 5456 KB Output is correct
23 Correct 4 ms 6608 KB Output is correct
24 Correct 5 ms 6736 KB Output is correct
25 Correct 4 ms 6608 KB Output is correct
26 Correct 4 ms 6736 KB Output is correct
27 Correct 5 ms 6736 KB Output is correct
28 Correct 4 ms 6736 KB Output is correct
29 Correct 4 ms 6608 KB Output is correct
30 Correct 4 ms 6608 KB Output is correct
31 Correct 4 ms 6736 KB Output is correct
32 Correct 5 ms 6748 KB Output is correct
33 Correct 4 ms 6736 KB Output is correct
34 Correct 4 ms 6608 KB Output is correct
35 Correct 3 ms 5968 KB Output is correct
36 Correct 4 ms 6736 KB Output is correct
37 Correct 5 ms 6608 KB Output is correct
38 Correct 4 ms 6736 KB Output is correct
39 Correct 4 ms 6736 KB Output is correct
40 Correct 5 ms 6736 KB Output is correct
41 Correct 4 ms 6736 KB Output is correct
42 Correct 4 ms 6664 KB Output is correct
43 Correct 4 ms 6736 KB Output is correct
44 Correct 4 ms 6608 KB Output is correct
45 Correct 4 ms 6736 KB Output is correct
46 Correct 95 ms 51688 KB Output is correct
47 Correct 159 ms 79676 KB Output is correct
48 Correct 148 ms 79440 KB Output is correct
49 Correct 164 ms 84112 KB Output is correct
50 Correct 178 ms 84232 KB Output is correct
51 Correct 162 ms 84072 KB Output is correct
52 Correct 187 ms 84012 KB Output is correct
53 Correct 109 ms 80476 KB Output is correct
54 Correct 100 ms 80496 KB Output is correct
55 Correct 99 ms 78712 KB Output is correct
56 Correct 101 ms 78076 KB Output is correct
57 Correct 165 ms 79592 KB Output is correct
58 Correct 162 ms 84196 KB Output is correct
59 Correct 160 ms 84036 KB Output is correct
60 Correct 106 ms 80456 KB Output is correct
61 Correct 98 ms 80260 KB Output is correct
62 Correct 161 ms 79452 KB Output is correct
63 Correct 162 ms 83944 KB Output is correct
64 Correct 177 ms 83988 KB Output is correct
65 Correct 106 ms 80484 KB Output is correct
66 Correct 98 ms 79812 KB Output is correct
67 Correct 144 ms 77084 KB Output is correct
68 Correct 140 ms 79460 KB Output is correct
69 Correct 150 ms 79584 KB Output is correct
70 Correct 155 ms 84184 KB Output is correct
71 Correct 154 ms 84252 KB Output is correct
72 Correct 192 ms 84068 KB Output is correct
73 Correct 158 ms 84316 KB Output is correct
74 Correct 98 ms 80488 KB Output is correct
75 Correct 94 ms 80440 KB Output is correct
76 Correct 98 ms 78088 KB Output is correct
77 Correct 96 ms 80112 KB Output is correct
78 Correct 2326 ms 78992 KB Output is correct
79 Correct 3508 ms 79700 KB Output is correct
80 Correct 3421 ms 79388 KB Output is correct
81 Correct 3597 ms 84032 KB Output is correct
82 Correct 3564 ms 84280 KB Output is correct
83 Correct 3460 ms 84068 KB Output is correct
84 Correct 3566 ms 84684 KB Output is correct
85 Correct 735 ms 80476 KB Output is correct
86 Correct 863 ms 80488 KB Output is correct
87 Correct 3373 ms 79180 KB Output is correct
88 Correct 3336 ms 78904 KB Output is correct
89 Correct 3558 ms 80336 KB Output is correct
90 Correct 510 ms 80476 KB Output is correct
91 Correct 3 ms 5456 KB Output is correct
92 Correct 4 ms 6608 KB Output is correct
93 Correct 5 ms 6736 KB Output is correct
94 Correct 140 ms 79596 KB Output is correct
95 Correct 169 ms 84096 KB Output is correct
96 Correct 165 ms 84004 KB Output is correct
97 Correct 97 ms 80484 KB Output is correct
98 Correct 100 ms 80300 KB Output is correct
99 Correct 143 ms 79548 KB Output is correct
100 Correct 157 ms 83912 KB Output is correct
101 Correct 169 ms 84088 KB Output is correct
102 Correct 96 ms 80372 KB Output is correct
103 Correct 101 ms 79860 KB Output is correct
104 Correct 4 ms 6608 KB Output is correct
105 Correct 4 ms 6736 KB Output is correct
106 Correct 5 ms 6736 KB Output is correct
107 Correct 4 ms 6676 KB Output is correct
108 Correct 4 ms 6608 KB Output is correct
109 Correct 4 ms 6608 KB Output is correct
110 Correct 4 ms 6736 KB Output is correct
111 Correct 4 ms 6736 KB Output is correct
112 Correct 4 ms 6736 KB Output is correct
113 Correct 5 ms 6608 KB Output is correct
114 Correct 820 ms 22056 KB Output is correct
115 Execution timed out 4083 ms 79552 KB Time limit exceeded
116 Halted 0 ms 0 KB -