oj.uz

Submission #949443

# Submission time Handle Problem Language Result Execution time Memory
949443 2024-03-19T08:50:41 Z MilosMilutinovic IOI Fever (JOI21_fever) C++14
69 / 100
 3227 ms 125356 KB 
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
    ll x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
#define info pair<pair<ll,int>,pair<ll,int>>

int n,tot;
int d1[400005],d2[400005],d3[400005],d4[400005],root[4][400005],lch[15000005],rch[15000005],pos[4][400005];
ll x[400005],y[400005],dir[400005];
bool vis[400005];
pair<ll,int> mn[15000005][4],mx[15000005][4];
 
void change(int&id,int t,int l,int r,int ql,int qr,info v){
	if(!id) id=++tot,mn[id][t]=mp((ll)1e18,0),mx[id][t]=mp((ll)-1e18,0);
	if(ql<=l&&r<=qr){
		mn[id][t]=min(mn[id][t],v.fi);
		mx[id][t]=max(mx[id][t],v.se);
		return;
	}
	int mid=(l+r)/2;
	if(qr<=mid) change(lch[id],t,l,mid,ql,qr,v);
	else if(ql>mid) change(rch[id],t,mid+1,r,ql,qr,v);
	else change(lch[id],t,l,mid,ql,qr,v),change(rch[id],t,mid+1,r,ql,qr,v);
}
 
pair<ll,int> query(int id,int t,int l,int r,int i,int v){
	if(!id) return mp((ll)1e18,0);
	if(l==r) return min(mp(mn[id][t].fi-v,mn[id][t].se),mp(v-mx[id][t].fi,mx[id][t].se));
	int mid=(l+r)/2;
	pair<ll,int> bst;
	if(i<=mid) bst=query(lch[id],t,l,mid,i,v);
	else bst=query(rch[id],t,mid+1,r,i,v);
	bst=min(bst,min(mp(mn[id][t].fi-v,mn[id][t].se),mp(v-mx[id][t].fi,mx[id][t].se)));
	return bst;
}
 
int main(){
	n=readint();
	for(int i=1;i<=n;i++) x[i]=readint(),y[i]=readint(),x[i]*=2,y[i]*=2;
	vector<int> xs1,xs2,xs3,xs4;
	for(int i=1;i<=n;i++){
		xs1.pb(x[i]+y[i]);
		xs2.pb(x[i]-y[i]);
		xs3.pb(x[i]);
		xs4.pb(y[i]);
	}
	sort(xs1.begin(),xs1.end());
	xs1.erase(unique(xs1.begin(),xs1.end()),xs1.end());
	sort(xs2.begin(),xs2.end());
	xs2.erase(unique(xs2.begin(),xs2.end()),xs2.end());
	sort(xs3.begin(),xs3.end());
	xs3.erase(unique(xs3.begin(),xs3.end()),xs3.end());
	sort(xs4.begin(),xs4.end());
	xs4.erase(unique(xs4.begin(),xs4.end()),xs4.end());
	int sz1=(int)xs1.size(),sz2=(int)xs2.size(),sz3=(int)xs3.size(),sz4=(int)xs4.size();
	vector<set<pii>> st1(sz1),st2(sz2),st3(sz3),st4(sz4);
	vector<vector<int>> ids1(sz1),ids2(sz2),ids3(sz3),ids4(sz4);
	for(int i=1;i<=n;i++){
		d1[i]=(int)(lower_bound(xs1.begin(),xs1.end(),x[i]+y[i])-xs1.begin());
		d2[i]=(int)(lower_bound(xs2.begin(),xs2.end(),x[i]-y[i])-xs2.begin());
		d3[i]=(int)(lower_bound(xs3.begin(),xs3.end(),x[i])-xs3.begin());
		d4[i]=(int)(lower_bound(xs4.begin(),xs4.end(),y[i])-xs4.begin());
		st1[d1[i]].emplace(x[i],i);
		st2[d2[i]].emplace(x[i],i);
		st3[d3[i]].emplace(y[i],i);
		st4[d4[i]].emplace(x[i],i);
		ids1[d1[i]].pb(i);
		ids2[d2[i]].pb(i);
		ids3[d3[i]].pb(i);
		ids4[d4[i]].pb(i);
	}
	for(int i=0;i<sz1;i++){
		sort(ids1[i].begin(),ids1[i].end(),[&](int i,int j){return x[i]<x[j];});
		for(int j=0;j<(int)ids1[i].size();j++){
			pos[0][ids1[i][j]]=j;
		}
	}
	for(int i=0;i<sz2;i++){
		sort(ids2[i].begin(),ids2[i].end(),[&](int i,int j){return x[i]<x[j];});
		for(int j=0;j<(int)ids2[i].size();j++){
			pos[1][ids2[i][j]]=j;
		}
	}
	for(int i=0;i<sz3;i++){
		sort(ids3[i].begin(),ids3[i].end(),[&](int i,int j){return y[i]<y[j];});
		for(int j=0;j<(int)ids3[i].size();j++){
			pos[2][ids3[i][j]]=j;
		}
	}
	for(int i=0;i<sz4;i++){
		sort(ids4[i].begin(),ids4[i].end(),[&](int i,int j){return x[i]<x[j];});
		for(int j=0;j<(int)ids4[i].size();j++){
			pos[3][ids4[i][j]]=j;
		}
	}
	int ans=0;
	for(int d=0;d<4;d++){
		for(int i=1;i<=n;i++) vis[i]=false;
		dir[1]=d;
		priority_queue<pair<ll,pii>> pq;
		pq.push(mp(0,mp(1,d)));
		for(int i=1;i<=n;i++){
			st1[d1[i]].emplace(x[i],i);
			st2[d2[i]].emplace(x[i],i);
			st3[d3[i]].emplace(y[i],i);
			st4[d4[i]].emplace(x[i],i);
		}
		while(tot){
			for(int j=0;j<4;j++){
				mn[tot][j]=mp((ll)1e18,0);
				mx[tot][j]=mp((ll)-1e18,0);
			}
			lch[tot]=0;
			rch[tot]=0;
			tot--;
		}
		for(int j=0;j<4;j++){
			for(int i=0;i<sz1;i++) root[j][i]=0;
			for(int i=0;i<sz2;i++) root[j][i]=0;
		}
		auto upd=[&](int idx){
			if(vis[idx]) return;
			pair<ll,int> bst=min(query(root[0][d1[idx]],0,0,ids1[d1[idx]].size()-1,pos[0][idx],x[idx]),query(root[1][d2[idx]],1,0,ids2[d2[idx]].size()-1,pos[1][idx],x[idx]));
			bst=min({bst,query(root[2][d3[idx]],2,0,ids3[d3[idx]].size()-1,pos[2][idx],y[idx]/2),query(root[3][d4[idx]],3,0,ids4[d4[idx]].size()-1,pos[3][idx],x[idx]/2)});
			if(bst.fi<(ll)1e17){
				pq.push(mp(-bst.fi,mp(idx,bst.se)));
			}
			return;
		};
		while(!pq.empty()){
			ll t=-pq.top().fi;
			int i=pq.top().se.fi;
			int dd=pq.top().se.se;
			pq.pop();
			if(vis[i]) continue;
			dir[i]=dd;
			vis[i]=true;
			auto it1=st1[d1[i]].lower_bound(mp(x[i],i));
			if(it1!=st1[d1[i]].begin()) upd(prev(it1)->se);
			if(it1!=prev(st1[d1[i]].end())) upd(next(it1)->se);
			st1[d1[i]].erase(it1);
			auto it2=st2[d2[i]].lower_bound(mp(x[i],i));
			if(it2!=st2[d2[i]].begin()) upd(prev(it2)->se);
			if(it2!=prev(st2[d2[i]].end())) upd(next(it2)->se);
			st2[d2[i]].erase(it2);
			auto it3=st3[d3[i]].lower_bound(mp(y[i],i));
			if(it3!=st3[d3[i]].begin()) upd(prev(it3)->se);
			if(it3!=prev(st3[d3[i]].end())) upd(next(it3)->se);
			st3[d3[i]].erase(it3);
			auto it4=st4[d4[i]].lower_bound(mp(x[i],i));
			if(it4!=st4[d4[i]].begin()) upd(prev(it4)->se);
			if(it4!=prev(st4[d4[i]].end())) upd(next(it4)->se);
			st4[d4[i]].erase(it4);
			if(dir[i]==0){
				// up
				{
					int low=0,high=ids1[d1[i]].size()-1,p=-1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[i]-x[ids1[d1[i]][mid]]>=t) p=mid,low=mid+1;
						else high=mid-1;
					}
					if(p!=-1){
						change(root[0][d1[i]],0,0,ids1[d1[i]].size()-1,0,p,mp(mp(x[i],2),mp((ll)-1e18,0)));
						auto it=st1[d1[i]].lower_bound(mp(x[ids1[d1[i]][p]],ids1[d1[i]][p]+1));
						if(it!=st1[d1[i]].begin()) upd(prev(it)->se);
					}
				}
				{
					int low=0,high=ids2[d2[i]].size()-1,p=high+1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[ids2[d2[i]][mid]]-x[i]>=t) p=mid,high=mid-1; 
						else low=mid+1;
					}
					if(p<(int)ids2[d2[i]].size()){
						change(root[1][d2[i]],1,0,ids2[d2[i]].size()-1,p,ids2[d2[i]].size()-1,mp(mp((ll)1e18,0),mp(x[i],3)));
						auto it=st2[d2[i]].lower_bound(mp(x[ids2[d2[i]][p]],ids2[d2[i]][p]));
						if(it!=st2[d2[i]].end()) upd(it->se);
					}
				}
				{
					int low=0,high=ids3[d3[i]].size()-1,p=high+1;
					while(low<=high){
						int mid=(low+high)/2;
						if((y[ids3[d3[i]][mid]]-y[i])/2>=t) p=mid,high=mid-1;
						else low=mid+1;
					}
					if(p<ids3[d3[i]].size()){
						change(root[2][d3[i]],2,0,ids3[d3[i]].size()-1,p,ids3[d3[i]].size()-1,mp(mp((ll)1e18,0),mp(y[i]/2,1)));
						auto it=st3[d3[i]].lower_bound(mp(y[ids3[d3[i]][p]],ids3[d3[i]][p]));
						if(it!=st3[d3[i]].end()) upd(it->se);
					}
				}
			}
			if(dir[i]==1){
				// down
				{
					int low=0,high=ids1[d1[i]].size()-1,p=high+1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[ids1[d1[i]][mid]]-x[i]>=t) p=mid,high=mid-1;
						else low=mid+1;
					}
					if(p<(int)ids1[d1[i]].size()){
						change(root[0][d1[i]],0,0,ids1[d1[i]].size()-1,p,ids1[d1[i]].size()-1,mp(mp((ll)1e18,2),mp(x[i],3)));
						auto it=st1[d1[i]].lower_bound(mp(x[ids1[d1[i]][p]],ids1[d1[i]][p]));
						if(it!=st1[d1[i]].end()) upd(it->se);
					}
				}
				{
					int low=0,high=ids2[d2[i]].size()-1,p=-1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[i]-x[ids2[d2[i]][mid]]>=t) p=mid,low=mid+1; 
						else high=mid-1;
					}
					if(p!=-1){
						change(root[1][d2[i]],1,0,ids2[d2[i]].size()-1,0,p,mp(mp(x[i],2),mp((ll)-1e18,3)));
						auto it=st2[d2[i]].lower_bound(mp(x[ids2[d2[i]][p]],ids2[d2[i]][p]+1));
						if(it!=st2[d2[i]].begin()) upd(prev(it)->se);
					}
				}
				{
					int low=0,high=ids3[d3[i]].size()-1,p=-1;
					while(low<=high){
						int mid=(low+high)/2;
						if((y[i]-y[ids3[d3[i]][mid]])/2>=t) p=mid,low=mid+1;
						else high=mid-1;
					}
					if(p!=-1){
						change(root[2][d3[i]],2,0,ids3[d3[i]].size()-1,0,p,mp(mp(y[i]/2,0),mp(-(ll)1e18,1)));
						auto it=st3[d3[i]].lower_bound(mp(y[ids3[d3[i]][p]],ids3[d3[i]][p]+1));
						if(it!=st3[d3[i]].begin()) upd(prev(it)->se);
					}
				}
			}
			if(dir[i]==2){
				// right
				{
					int low=0,high=ids1[d1[i]].size()-1,p=high+1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[ids1[d1[i]][mid]]-x[i]>=t) p=mid,high=mid-1;
						else low=mid+1;
					}
					if(p<(int)ids1[d1[i]].size()){
						change(root[0][d1[i]],0,0,ids1[d1[i]].size()-1,p,ids1[d1[i]].size()-1,mp(mp((ll)1e18,2),mp(x[i],0)));
						auto it=st1[d1[i]].lower_bound(mp(x[ids1[d1[i]][p]],ids1[d1[i]][p]));
						if(it!=st1[d1[i]].end()) upd(it->se);
					}
				}
				{
					int low=0,high=ids2[d2[i]].size()-1,p=high+1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[ids2[d2[i]][mid]]-x[i]>=t) p=mid,high=mid-1;
						else low=mid+1;
					}
					if(p<(int)ids2[d2[i]].size()){
						change(root[1][d2[i]],1,0,ids2[d2[i]].size()-1,p,ids2[d2[i]].size()-1,mp(mp((ll)1e18,0),mp(x[i],1)));
						auto it=st2[d2[i]].lower_bound(mp(x[ids2[d2[i]][p]],ids2[d2[i]][p]));
						if(it!=st2[d2[i]].end()) upd(it->se);
					}
				}
				{
					int low=0,high=ids4[d4[i]].size()-1,p=high+1;
					while(low<=high){
						int mid=(low+high)/2;
						if((x[ids4[d4[i]][mid]]-x[i])/2>=t) p=mid,high=mid-1;
						else low=mid+1;
					}
					if(p<ids4[d4[i]].size()){
						change(root[3][d4[i]],3,0,ids4[d4[i]].size()-1,p,ids4[d4[i]].size()-1,mp(mp((ll)1e18,0),mp(x[i]/2,3)));
						auto it=st4[d4[i]].lower_bound(mp(x[ids4[d4[i]][p]],ids4[d4[i]][p]));
						if(it!=st4[d4[i]].end()) upd(it->se);
					} 
				}
			}
			if(dir[i]==3){
				// left
				{
					int low=0,high=ids1[d1[i]].size()-1,p=-1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[i]-x[ids1[d1[i]][mid]]>=t) p=mid,low=mid+1;
						else high=mid-1;
					}
					if(p!=-1){
						change(root[0][d1[i]],0,0,ids1[d1[i]].size()-1,0,p,mp(mp(x[i],1),mp((ll)-1e18,0)));
						auto it=st1[d1[i]].lower_bound(mp(x[ids1[d1[i]][p]],ids1[d1[i]][p]+1));
						if(it!=st1[d1[i]].begin()) upd(prev(it)->se);
					}
				}
				{
					int low=0,high=ids2[d2[i]].size()-1,p=-1;
					while(low<=high){
						int mid=(low+high)/2;
						if(x[i]-x[ids2[d2[i]][mid]]>=t) p=mid,low=mid+1;
						else high=mid-1;
					}
					if(p!=-1){
						change(root[1][d2[i]],1,0,ids2[d2[i]].size()-1,0,p,mp(mp(x[i],0),mp((ll)-1e18,3)));
						auto it=st2[d2[i]].lower_bound(mp(x[ids2[d2[i]][p]],ids2[d2[i]][p]+1));
						if(it!=st2[d2[i]].begin()) upd(prev(it)->se);
					}
				}
				{
					int low=0,high=ids4[d4[i]].size()-1,p=-1;
					while(low<=high){
						int mid=(low+high)/2;
						if((x[i]-x[ids4[d4[i]][mid]])/2>=t) p=mid,low=mid+1;
						else high=mid-1;
					}
					if(p!=-1){
						change(root[3][d4[i]],3,0,ids4[d4[i]].size()-1,0,p,mp(mp(x[i]/2,2),mp((ll)-1e18,3)));
						auto it=st4[d4[i]].lower_bound(mp(x[ids4[d4[i]][p]],ids4[d4[i]][p]+1));
						if(it!=st4[d4[i]].begin()) upd(prev(it)->se);
					} 
				}
			}
		}
		int cnt=0;
		for(int i=1;i<=n;i++) cnt+=vis[i];
		ans=max(ans,cnt);
	}
	printf("%d\n",ans);
}

Compilation message

fever.cpp: In function 'int main()':
fever.cpp:210:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |      if(p<ids3[d3[i]].size()){
      |         ~^~~~~~~~~~~~~~~~~~~
fever.cpp:294:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  294 |      if(p<ids4[d4[i]].size()){
      |         ~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 29020 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 27108 KB Output is correct
8 Correct 4 ms 31064 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 4 ms 31068 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 4 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 4 ms 29020 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 26972 KB Output is correct
17 Correct 3 ms 26972 KB Output is correct
18 Correct 4 ms 31068 KB Output is correct
19 Correct 4 ms 31068 KB Output is correct
20 Correct 4 ms 31068 KB Output is correct
21 Correct 4 ms 31064 KB Output is correct
22 Correct 4 ms 31068 KB Output is correct
23 Correct 4 ms 31068 KB Output is correct
24 Correct 3 ms 26972 KB Output is correct
25 Correct 3 ms 26972 KB Output is correct
26 Correct 3 ms 27072 KB Output is correct
27 Correct 3 ms 26972 KB Output is correct
28 Correct 3 ms 27224 KB Output is correct
29 Correct 3 ms 26972 KB Output is correct
30 Correct 3 ms 26972 KB Output is correct
31 Correct 3 ms 26972 KB Output is correct
32 Correct 3 ms 26968 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 29020 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 27108 KB Output is correct
8 Correct 4 ms 31064 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 4 ms 31068 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 4 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 4 ms 29020 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 26972 KB Output is correct
17 Correct 3 ms 26972 KB Output is correct
18 Correct 4 ms 31068 KB Output is correct
19 Correct 4 ms 31068 KB Output is correct
20 Correct 4 ms 31068 KB Output is correct
21 Correct 4 ms 31064 KB Output is correct
22 Correct 4 ms 31068 KB Output is correct
23 Correct 4 ms 31068 KB Output is correct
24 Correct 3 ms 26972 KB Output is correct
25 Correct 3 ms 26972 KB Output is correct
26 Correct 3 ms 27072 KB Output is correct
27 Correct 3 ms 26972 KB Output is correct
28 Correct 3 ms 27224 KB Output is correct
29 Correct 3 ms 26972 KB Output is correct
30 Correct 3 ms 26972 KB Output is correct
31 Correct 3 ms 26972 KB Output is correct
32 Correct 3 ms 26968 KB Output is correct
33 Correct 3 ms 29016 KB Output is correct
34 Correct 4 ms 27104 KB Output is correct
35 Correct 4 ms 31220 KB Output is correct
36 Correct 4 ms 31068 KB Output is correct
37 Correct 3 ms 26972 KB Output is correct
38 Correct 4 ms 26972 KB Output is correct
39 Correct 3 ms 27228 KB Output is correct
40 Correct 3 ms 27080 KB Output is correct
41 Correct 4 ms 29020 KB Output is correct
42 Correct 3 ms 26972 KB Output is correct
43 Correct 4 ms 27068 KB Output is correct
44 Correct 3 ms 26972 KB Output is correct
45 Correct 3 ms 26972 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 26972 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 31256 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 4 ms 31068 KB Output is correct
6 Correct 3 ms 27188 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 3 ms 26968 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 29020 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 27108 KB Output is correct
8 Correct 4 ms 31064 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 4 ms 31068 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 4 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 4 ms 29020 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 26972 KB Output is correct
17 Correct 3 ms 26972 KB Output is correct
18 Correct 4 ms 31068 KB Output is correct
19 Correct 4 ms 31068 KB Output is correct
20 Correct 4 ms 31068 KB Output is correct
21 Correct 4 ms 31064 KB Output is correct
22 Correct 4 ms 31068 KB Output is correct
23 Correct 4 ms 31068 KB Output is correct
24 Correct 3 ms 26972 KB Output is correct
25 Correct 3 ms 26972 KB Output is correct
26 Correct 3 ms 27072 KB Output is correct
27 Correct 3 ms 26972 KB Output is correct
28 Correct 3 ms 27224 KB Output is correct
29 Correct 3 ms 26972 KB Output is correct
30 Correct 3 ms 26972 KB Output is correct
31 Correct 3 ms 26972 KB Output is correct
32 Correct 3 ms 26968 KB Output is correct
33 Correct 3 ms 29016 KB Output is correct
34 Correct 4 ms 27104 KB Output is correct
35 Correct 4 ms 31220 KB Output is correct
36 Correct 4 ms 31068 KB Output is correct
37 Correct 3 ms 26972 KB Output is correct
38 Correct 4 ms 26972 KB Output is correct
39 Correct 3 ms 27228 KB Output is correct
40 Correct 3 ms 27080 KB Output is correct
41 Correct 4 ms 29020 KB Output is correct
42 Correct 3 ms 26972 KB Output is correct
43 Correct 4 ms 27068 KB Output is correct
44 Correct 3 ms 26972 KB Output is correct
45 Correct 3 ms 26972 KB Output is correct
46 Correct 3 ms 26972 KB Output is correct
47 Correct 3 ms 26972 KB Output is correct
48 Correct 3 ms 31256 KB Output is correct
49 Correct 4 ms 26972 KB Output is correct
50 Correct 4 ms 31068 KB Output is correct
51 Correct 3 ms 27188 KB Output is correct
52 Correct 4 ms 26972 KB Output is correct
53 Correct 3 ms 26968 KB Output is correct
54 Correct 4 ms 31068 KB Output is correct
55 Correct 3 ms 26972 KB Output is correct
56 Correct 4 ms 31176 KB Output is correct
57 Correct 5 ms 31068 KB Output is correct
58 Correct 4 ms 27156 KB Output is correct
59 Correct 4 ms 27224 KB Output is correct
60 Correct 4 ms 27224 KB Output is correct
61 Correct 4 ms 29020 KB Output is correct
62 Correct 4 ms 27156 KB Output is correct
63 Correct 3 ms 27072 KB Output is correct
64 Correct 4 ms 26972 KB Output is correct
65 Correct 4 ms 26968 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 29020 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 27108 KB Output is correct
8 Correct 4 ms 31064 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 4 ms 31068 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 4 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 4 ms 29020 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 26972 KB Output is correct
17 Correct 3 ms 26972 KB Output is correct
18 Correct 4 ms 31068 KB Output is correct
19 Correct 4 ms 31068 KB Output is correct
20 Correct 4 ms 31068 KB Output is correct
21 Correct 4 ms 31064 KB Output is correct
22 Correct 4 ms 31068 KB Output is correct
23 Correct 4 ms 31068 KB Output is correct
24 Correct 3 ms 26972 KB Output is correct
25 Correct 3 ms 26972 KB Output is correct
26 Correct 3 ms 27072 KB Output is correct
27 Correct 3 ms 26972 KB Output is correct
28 Correct 3 ms 27224 KB Output is correct
29 Correct 3 ms 26972 KB Output is correct
30 Correct 3 ms 26972 KB Output is correct
31 Correct 3 ms 26972 KB Output is correct
32 Correct 3 ms 26968 KB Output is correct
33 Correct 3 ms 29016 KB Output is correct
34 Correct 4 ms 27104 KB Output is correct
35 Correct 4 ms 31220 KB Output is correct
36 Correct 4 ms 31068 KB Output is correct
37 Correct 3 ms 26972 KB Output is correct
38 Correct 4 ms 26972 KB Output is correct
39 Correct 3 ms 27228 KB Output is correct
40 Correct 3 ms 27080 KB Output is correct
41 Correct 4 ms 29020 KB Output is correct
42 Correct 3 ms 26972 KB Output is correct
43 Correct 4 ms 27068 KB Output is correct
44 Correct 3 ms 26972 KB Output is correct
45 Correct 3 ms 26972 KB Output is correct
46 Correct 3 ms 26972 KB Output is correct
47 Correct 3 ms 26972 KB Output is correct
48 Correct 3 ms 31256 KB Output is correct
49 Correct 4 ms 26972 KB Output is correct
50 Correct 4 ms 31068 KB Output is correct
51 Correct 3 ms 27188 KB Output is correct
52 Correct 4 ms 26972 KB Output is correct
53 Correct 3 ms 26968 KB Output is correct
54 Correct 4 ms 31068 KB Output is correct
55 Correct 3 ms 26972 KB Output is correct
56 Correct 4 ms 31176 KB Output is correct
57 Correct 5 ms 31068 KB Output is correct
58 Correct 4 ms 27156 KB Output is correct
59 Correct 4 ms 27224 KB Output is correct
60 Correct 4 ms 27224 KB Output is correct
61 Correct 4 ms 29020 KB Output is correct
62 Correct 4 ms 27156 KB Output is correct
63 Correct 3 ms 27072 KB Output is correct
64 Correct 4 ms 26972 KB Output is correct
65 Correct 4 ms 26968 KB Output is correct
66 Correct 9 ms 32856 KB Output is correct
67 Correct 9 ms 32860 KB Output is correct
68 Correct 8 ms 32968 KB Output is correct
69 Correct 44 ms 30224 KB Output is correct
70 Correct 20 ms 30152 KB Output is correct
71 Correct 10 ms 27996 KB Output is correct
72 Correct 9 ms 28508 KB Output is correct
73 Correct 9 ms 33168 KB Output is correct
74 Correct 11 ms 28528 KB Output is correct
75 Correct 13 ms 28760 KB Output is correct
76 Correct 9 ms 28764 KB Output is correct
77 Correct 10 ms 28772 KB Output is correct
78 Correct 9 ms 30812 KB Output is correct
79 Correct 9 ms 28764 KB Output is correct
80 Correct 8 ms 29020 KB Output is correct
81 Correct 9 ms 31068 KB Output is correct
82 Correct 11 ms 28764 KB Output is correct
83 Correct 13 ms 32860 KB Output is correct
84 Correct 7 ms 28252 KB Output is correct
85 Correct 7 ms 27900 KB Output is correct
86 Correct 9 ms 27736 KB Output is correct
87 Correct 7 ms 27996 KB Output is correct
88 Correct 9 ms 28620 KB Output is correct
89 Correct 10 ms 30812 KB Output is correct
90 Correct 10 ms 30816 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 29020 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 27108 KB Output is correct
8 Correct 4 ms 31064 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 4 ms 31068 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 4 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 4 ms 29020 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 26972 KB Output is correct
17 Correct 3 ms 26972 KB Output is correct
18 Correct 4 ms 31068 KB Output is correct
19 Correct 4 ms 31068 KB Output is correct
20 Correct 4 ms 31068 KB Output is correct
21 Correct 4 ms 31064 KB Output is correct
22 Correct 4 ms 31068 KB Output is correct
23 Correct 4 ms 31068 KB Output is correct
24 Correct 3 ms 26972 KB Output is correct
25 Correct 3 ms 26972 KB Output is correct
26 Correct 3 ms 27072 KB Output is correct
27 Correct 3 ms 26972 KB Output is correct
28 Correct 3 ms 27224 KB Output is correct
29 Correct 3 ms 26972 KB Output is correct
30 Correct 3 ms 26972 KB Output is correct
31 Correct 3 ms 26972 KB Output is correct
32 Correct 3 ms 26968 KB Output is correct
33 Correct 3 ms 29016 KB Output is correct
34 Correct 4 ms 27104 KB Output is correct
35 Correct 4 ms 31220 KB Output is correct
36 Correct 4 ms 31068 KB Output is correct
37 Correct 3 ms 26972 KB Output is correct
38 Correct 4 ms 26972 KB Output is correct
39 Correct 3 ms 27228 KB Output is correct
40 Correct 3 ms 27080 KB Output is correct
41 Correct 4 ms 29020 KB Output is correct
42 Correct 3 ms 26972 KB Output is correct
43 Correct 4 ms 27068 KB Output is correct
44 Correct 3 ms 26972 KB Output is correct
45 Correct 3 ms 26972 KB Output is correct
46 Correct 3 ms 26972 KB Output is correct
47 Correct 3 ms 26972 KB Output is correct
48 Correct 3 ms 31256 KB Output is correct
49 Correct 4 ms 26972 KB Output is correct
50 Correct 4 ms 31068 KB Output is correct
51 Correct 3 ms 27188 KB Output is correct
52 Correct 4 ms 26972 KB Output is correct
53 Correct 3 ms 26968 KB Output is correct
54 Correct 4 ms 31068 KB Output is correct
55 Correct 3 ms 26972 KB Output is correct
56 Correct 4 ms 31176 KB Output is correct
57 Correct 5 ms 31068 KB Output is correct
58 Correct 4 ms 27156 KB Output is correct
59 Correct 4 ms 27224 KB Output is correct
60 Correct 4 ms 27224 KB Output is correct
61 Correct 4 ms 29020 KB Output is correct
62 Correct 4 ms 27156 KB Output is correct
63 Correct 3 ms 27072 KB Output is correct
64 Correct 4 ms 26972 KB Output is correct
65 Correct 4 ms 26968 KB Output is correct
66 Correct 354 ms 74532 KB Output is correct
67 Correct 451 ms 85852 KB Output is correct
68 Correct 428 ms 95780 KB Output is correct
69 Correct 684 ms 83592 KB Output is correct
70 Correct 924 ms 83840 KB Output is correct
71 Correct 403 ms 93568 KB Output is correct
72 Correct 423 ms 93312 KB Output is correct
73 Correct 589 ms 83960 KB Output is correct
74 Correct 431 ms 93624 KB Output is correct
75 Correct 461 ms 93028 KB Output is correct
76 Correct 607 ms 86280 KB Output is correct
77 Correct 467 ms 93880 KB Output is correct
78 Correct 569 ms 125112 KB Output is correct
79 Correct 581 ms 125356 KB Output is correct

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 29020 KB Output is correct
6 Correct 4 ms 31068 KB Output is correct
7 Correct 4 ms 27108 KB Output is correct
8 Correct 4 ms 31064 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 4 ms 31068 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 4 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 4 ms 29020 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 26972 KB Output is correct
17 Correct 3 ms 26972 KB Output is correct
18 Correct 4 ms 31068 KB Output is correct
19 Correct 4 ms 31068 KB Output is correct
20 Correct 4 ms 31068 KB Output is correct
21 Correct 4 ms 31064 KB Output is correct
22 Correct 4 ms 31068 KB Output is correct
23 Correct 4 ms 31068 KB Output is correct
24 Correct 3 ms 26972 KB Output is correct
25 Correct 3 ms 26972 KB Output is correct
26 Correct 3 ms 27072 KB Output is correct
27 Correct 3 ms 26972 KB Output is correct
28 Correct 3 ms 27224 KB Output is correct
29 Correct 3 ms 26972 KB Output is correct
30 Correct 3 ms 26972 KB Output is correct
31 Correct 3 ms 26972 KB Output is correct
32 Correct 3 ms 26968 KB Output is correct
33 Correct 3 ms 29016 KB Output is correct
34 Correct 4 ms 27104 KB Output is correct
35 Correct 4 ms 31220 KB Output is correct
36 Correct 4 ms 31068 KB Output is correct
37 Correct 3 ms 26972 KB Output is correct
38 Correct 4 ms 26972 KB Output is correct
39 Correct 3 ms 27228 KB Output is correct
40 Correct 3 ms 27080 KB Output is correct
41 Correct 4 ms 29020 KB Output is correct
42 Correct 3 ms 26972 KB Output is correct
43 Correct 4 ms 27068 KB Output is correct
44 Correct 3 ms 26972 KB Output is correct
45 Correct 3 ms 26972 KB Output is correct
46 Correct 3 ms 26972 KB Output is correct
47 Correct 3 ms 26972 KB Output is correct
48 Correct 3 ms 31256 KB Output is correct
49 Correct 4 ms 26972 KB Output is correct
50 Correct 4 ms 31068 KB Output is correct
51 Correct 3 ms 27188 KB Output is correct
52 Correct 4 ms 26972 KB Output is correct
53 Correct 3 ms 26968 KB Output is correct
54 Correct 4 ms 31068 KB Output is correct
55 Correct 3 ms 26972 KB Output is correct
56 Correct 4 ms 31176 KB Output is correct
57 Correct 5 ms 31068 KB Output is correct
58 Correct 4 ms 27156 KB Output is correct
59 Correct 4 ms 27224 KB Output is correct
60 Correct 4 ms 27224 KB Output is correct
61 Correct 4 ms 29020 KB Output is correct
62 Correct 4 ms 27156 KB Output is correct
63 Correct 3 ms 27072 KB Output is correct
64 Correct 4 ms 26972 KB Output is correct
65 Correct 4 ms 26968 KB Output is correct
66 Correct 9 ms 32856 KB Output is correct
67 Correct 9 ms 32860 KB Output is correct
68 Correct 8 ms 32968 KB Output is correct
69 Correct 44 ms 30224 KB Output is correct
70 Correct 20 ms 30152 KB Output is correct
71 Correct 10 ms 27996 KB Output is correct
72 Correct 9 ms 28508 KB Output is correct
73 Correct 9 ms 33168 KB Output is correct
74 Correct 11 ms 28528 KB Output is correct
75 Correct 13 ms 28760 KB Output is correct
76 Correct 9 ms 28764 KB Output is correct
77 Correct 10 ms 28772 KB Output is correct
78 Correct 9 ms 30812 KB Output is correct
79 Correct 9 ms 28764 KB Output is correct
80 Correct 8 ms 29020 KB Output is correct
81 Correct 9 ms 31068 KB Output is correct
82 Correct 11 ms 28764 KB Output is correct
83 Correct 13 ms 32860 KB Output is correct
84 Correct 7 ms 28252 KB Output is correct
85 Correct 7 ms 27900 KB Output is correct
86 Correct 9 ms 27736 KB Output is correct
87 Correct 7 ms 27996 KB Output is correct
88 Correct 9 ms 28620 KB Output is correct
89 Correct 10 ms 30812 KB Output is correct
90 Correct 10 ms 30816 KB Output is correct
91 Correct 354 ms 74532 KB Output is correct
92 Correct 451 ms 85852 KB Output is correct
93 Correct 428 ms 95780 KB Output is correct
94 Correct 684 ms 83592 KB Output is correct
95 Correct 924 ms 83840 KB Output is correct
96 Correct 403 ms 93568 KB Output is correct
97 Correct 423 ms 93312 KB Output is correct
98 Correct 589 ms 83960 KB Output is correct
99 Correct 431 ms 93624 KB Output is correct
100 Correct 461 ms 93028 KB Output is correct
101 Correct 607 ms 86280 KB Output is correct
102 Correct 467 ms 93880 KB Output is correct
103 Correct 569 ms 125112 KB Output is correct
104 Correct 581 ms 125356 KB Output is correct
105 Correct 1473 ms 55320 KB Output is correct
106 Correct 2063 ms 63636 KB Output is correct
107 Correct 3227 ms 73036 KB Output is correct
108 Correct 2122 ms 68784 KB Output is correct
109 Correct 568 ms 61368 KB Output is correct
110 Correct 478 ms 77608 KB Output is correct
111 Correct 413 ms 94140 KB Output is correct
112 Correct 404 ms 89020 KB Output is correct
113 Correct 435 ms 89060 KB Output is correct
114 Incorrect 1887 ms 92592 KB Output isn't correct
115 Halted 0 ms 0 KB -