oj.uz

Submission #949437

# Submission time Handle Problem Language Result Execution time Memory
949437 2024-03-19T08:49:15 Z MilosMilutinovic IOI Fever (JOI21_fever) C++14
69 / 100
 4074 ms 137024 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 int long long
 
#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[10000005],rch[10000005],pos[4][400005];
ll x[400005],y[400005],dir[400005];
bool vis[400005];
pair<ll,int> mn[10000005][4],mx[10000005][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;
}
 
signed 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:212:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  212 |      if(p<ids3[d3[i]].size()){
      |         ~^~~~~~~~~~~~~~~~~~~
fever.cpp:296:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  296 |      if(p<ids4[d4[i]].size()){
      |         ~^~~~~~~~~~~~~~~~~~~
fever.cpp:350:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  350 |  printf("%d\n",ans);
      |          ~^    ~~~
      |           |    |
      |           int  long long int
      |          %lld

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37212 KB Output is correct
2 Correct 4 ms 37208 KB Output is correct
3 Correct 4 ms 33116 KB Output is correct
4 Correct 11 ms 33116 KB Output is correct
5 Correct 23 ms 35164 KB Output is correct
6 Correct 5 ms 37212 KB Output is correct
7 Correct 21 ms 33116 KB Output is correct
8 Correct 7 ms 37212 KB Output is correct
9 Correct 8 ms 37212 KB Output is correct
10 Correct 7 ms 37212 KB Output is correct
11 Correct 4 ms 35164 KB Output is correct
12 Correct 4 ms 33116 KB Output is correct
13 Correct 5 ms 29020 KB Output is correct
14 Correct 4 ms 29116 KB Output is correct
15 Correct 3 ms 26972 KB Output is correct
16 Correct 4 ms 29020 KB Output is correct
17 Correct 3 ms 27072 KB Output is correct
18 Correct 4 ms 29016 KB Output is correct
19 Correct 3 ms 26972 KB Output is correct
20 Correct 6 ms 37208 KB Output is correct
21 Correct 4 ms 37212 KB Output is correct
22 Correct 4 ms 37312 KB Output is correct
23 Correct 5 ms 37360 KB Output is correct
24 Correct 4 ms 33112 KB Output is correct
25 Correct 4 ms 33216 KB Output is correct
26 Correct 4 ms 33116 KB Output is correct
27 Correct 4 ms 33116 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 4 ms 33116 KB Output is correct
30 Correct 3 ms 29152 KB Output is correct
31 Correct 0 ms 604 KB Output is correct
32 Correct 4 ms 33116 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37212 KB Output is correct
2 Correct 4 ms 37208 KB Output is correct
3 Correct 4 ms 33116 KB Output is correct
4 Correct 11 ms 33116 KB Output is correct
5 Correct 23 ms 35164 KB Output is correct
6 Correct 5 ms 37212 KB Output is correct
7 Correct 21 ms 33116 KB Output is correct
8 Correct 7 ms 37212 KB Output is correct
9 Correct 8 ms 37212 KB Output is correct
10 Correct 7 ms 37212 KB Output is correct
11 Correct 4 ms 35164 KB Output is correct
12 Correct 4 ms 33116 KB Output is correct
13 Correct 5 ms 29020 KB Output is correct
14 Correct 4 ms 29116 KB Output is correct
15 Correct 3 ms 26972 KB Output is correct
16 Correct 4 ms 29020 KB Output is correct
17 Correct 3 ms 27072 KB Output is correct
18 Correct 4 ms 29016 KB Output is correct
19 Correct 3 ms 26972 KB Output is correct
20 Correct 6 ms 37208 KB Output is correct
21 Correct 4 ms 37212 KB Output is correct
22 Correct 4 ms 37312 KB Output is correct
23 Correct 5 ms 37360 KB Output is correct
24 Correct 4 ms 33112 KB Output is correct
25 Correct 4 ms 33216 KB Output is correct
26 Correct 4 ms 33116 KB Output is correct
27 Correct 4 ms 33116 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 4 ms 33116 KB Output is correct
30 Correct 3 ms 29152 KB Output is correct
31 Correct 0 ms 604 KB Output is correct
32 Correct 4 ms 33116 KB Output is correct
33 Correct 5 ms 35164 KB Output is correct
34 Correct 4 ms 33288 KB Output is correct
35 Correct 5 ms 37208 KB Output is correct
36 Correct 6 ms 37208 KB Output is correct
37 Correct 4 ms 33284 KB Output is correct
38 Correct 4 ms 33116 KB Output is correct
39 Correct 4 ms 33116 KB Output is correct
40 Correct 4 ms 33116 KB Output is correct
41 Correct 4 ms 35164 KB Output is correct
42 Correct 4 ms 33116 KB Output is correct
43 Correct 4 ms 33116 KB Output is correct
44 Correct 4 ms 33112 KB Output is correct
45 Correct 4 ms 33112 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 33372 KB Output is correct
2 Correct 4 ms 33116 KB Output is correct
3 Correct 5 ms 37316 KB Output is correct
4 Correct 5 ms 33112 KB Output is correct
5 Correct 5 ms 37212 KB Output is correct
6 Correct 4 ms 33112 KB Output is correct
7 Correct 5 ms 33624 KB Output is correct
8 Correct 5 ms 33116 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37212 KB Output is correct
2 Correct 4 ms 37208 KB Output is correct
3 Correct 4 ms 33116 KB Output is correct
4 Correct 11 ms 33116 KB Output is correct
5 Correct 23 ms 35164 KB Output is correct
6 Correct 5 ms 37212 KB Output is correct
7 Correct 21 ms 33116 KB Output is correct
8 Correct 7 ms 37212 KB Output is correct
9 Correct 8 ms 37212 KB Output is correct
10 Correct 7 ms 37212 KB Output is correct
11 Correct 4 ms 35164 KB Output is correct
12 Correct 4 ms 33116 KB Output is correct
13 Correct 5 ms 29020 KB Output is correct
14 Correct 4 ms 29116 KB Output is correct
15 Correct 3 ms 26972 KB Output is correct
16 Correct 4 ms 29020 KB Output is correct
17 Correct 3 ms 27072 KB Output is correct
18 Correct 4 ms 29016 KB Output is correct
19 Correct 3 ms 26972 KB Output is correct
20 Correct 6 ms 37208 KB Output is correct
21 Correct 4 ms 37212 KB Output is correct
22 Correct 4 ms 37312 KB Output is correct
23 Correct 5 ms 37360 KB Output is correct
24 Correct 4 ms 33112 KB Output is correct
25 Correct 4 ms 33216 KB Output is correct
26 Correct 4 ms 33116 KB Output is correct
27 Correct 4 ms 33116 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 4 ms 33116 KB Output is correct
30 Correct 3 ms 29152 KB Output is correct
31 Correct 0 ms 604 KB Output is correct
32 Correct 4 ms 33116 KB Output is correct
33 Correct 5 ms 35164 KB Output is correct
34 Correct 4 ms 33288 KB Output is correct
35 Correct 5 ms 37208 KB Output is correct
36 Correct 6 ms 37208 KB Output is correct
37 Correct 4 ms 33284 KB Output is correct
38 Correct 4 ms 33116 KB Output is correct
39 Correct 4 ms 33116 KB Output is correct
40 Correct 4 ms 33116 KB Output is correct
41 Correct 4 ms 35164 KB Output is correct
42 Correct 4 ms 33116 KB Output is correct
43 Correct 4 ms 33116 KB Output is correct
44 Correct 4 ms 33112 KB Output is correct
45 Correct 4 ms 33112 KB Output is correct
46 Correct 4 ms 33372 KB Output is correct
47 Correct 4 ms 33116 KB Output is correct
48 Correct 5 ms 37316 KB Output is correct
49 Correct 5 ms 33112 KB Output is correct
50 Correct 5 ms 37212 KB Output is correct
51 Correct 4 ms 33112 KB Output is correct
52 Correct 5 ms 33624 KB Output is correct
53 Correct 5 ms 33116 KB Output is correct
54 Correct 4 ms 37428 KB Output is correct
55 Correct 4 ms 33116 KB Output is correct
56 Correct 5 ms 37212 KB Output is correct
57 Correct 5 ms 37432 KB Output is correct
58 Correct 4 ms 33112 KB Output is correct
59 Correct 5 ms 33368 KB Output is correct
60 Correct 5 ms 33112 KB Output is correct
61 Correct 5 ms 35160 KB Output is correct
62 Correct 5 ms 33116 KB Output is correct
63 Correct 4 ms 33368 KB Output is correct
64 Correct 4 ms 33116 KB Output is correct
65 Correct 4 ms 33336 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37212 KB Output is correct
2 Correct 4 ms 37208 KB Output is correct
3 Correct 4 ms 33116 KB Output is correct
4 Correct 11 ms 33116 KB Output is correct
5 Correct 23 ms 35164 KB Output is correct
6 Correct 5 ms 37212 KB Output is correct
7 Correct 21 ms 33116 KB Output is correct
8 Correct 7 ms 37212 KB Output is correct
9 Correct 8 ms 37212 KB Output is correct
10 Correct 7 ms 37212 KB Output is correct
11 Correct 4 ms 35164 KB Output is correct
12 Correct 4 ms 33116 KB Output is correct
13 Correct 5 ms 29020 KB Output is correct
14 Correct 4 ms 29116 KB Output is correct
15 Correct 3 ms 26972 KB Output is correct
16 Correct 4 ms 29020 KB Output is correct
17 Correct 3 ms 27072 KB Output is correct
18 Correct 4 ms 29016 KB Output is correct
19 Correct 3 ms 26972 KB Output is correct
20 Correct 6 ms 37208 KB Output is correct
21 Correct 4 ms 37212 KB Output is correct
22 Correct 4 ms 37312 KB Output is correct
23 Correct 5 ms 37360 KB Output is correct
24 Correct 4 ms 33112 KB Output is correct
25 Correct 4 ms 33216 KB Output is correct
26 Correct 4 ms 33116 KB Output is correct
27 Correct 4 ms 33116 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 4 ms 33116 KB Output is correct
30 Correct 3 ms 29152 KB Output is correct
31 Correct 0 ms 604 KB Output is correct
32 Correct 4 ms 33116 KB Output is correct
33 Correct 5 ms 35164 KB Output is correct
34 Correct 4 ms 33288 KB Output is correct
35 Correct 5 ms 37208 KB Output is correct
36 Correct 6 ms 37208 KB Output is correct
37 Correct 4 ms 33284 KB Output is correct
38 Correct 4 ms 33116 KB Output is correct
39 Correct 4 ms 33116 KB Output is correct
40 Correct 4 ms 33116 KB Output is correct
41 Correct 4 ms 35164 KB Output is correct
42 Correct 4 ms 33116 KB Output is correct
43 Correct 4 ms 33116 KB Output is correct
44 Correct 4 ms 33112 KB Output is correct
45 Correct 4 ms 33112 KB Output is correct
46 Correct 4 ms 33372 KB Output is correct
47 Correct 4 ms 33116 KB Output is correct
48 Correct 5 ms 37316 KB Output is correct
49 Correct 5 ms 33112 KB Output is correct
50 Correct 5 ms 37212 KB Output is correct
51 Correct 4 ms 33112 KB Output is correct
52 Correct 5 ms 33624 KB Output is correct
53 Correct 5 ms 33116 KB Output is correct
54 Correct 4 ms 37428 KB Output is correct
55 Correct 4 ms 33116 KB Output is correct
56 Correct 5 ms 37212 KB Output is correct
57 Correct 5 ms 37432 KB Output is correct
58 Correct 4 ms 33112 KB Output is correct
59 Correct 5 ms 33368 KB Output is correct
60 Correct 5 ms 33112 KB Output is correct
61 Correct 5 ms 35160 KB Output is correct
62 Correct 5 ms 33116 KB Output is correct
63 Correct 4 ms 33368 KB Output is correct
64 Correct 4 ms 33116 KB Output is correct
65 Correct 4 ms 33336 KB Output is correct
66 Correct 10 ms 41052 KB Output is correct
67 Correct 10 ms 41080 KB Output is correct
68 Correct 12 ms 41308 KB Output is correct
69 Correct 44 ms 38492 KB Output is correct
70 Correct 17 ms 38492 KB Output is correct
71 Correct 11 ms 36440 KB Output is correct
72 Correct 10 ms 36688 KB Output is correct
73 Correct 11 ms 41308 KB Output is correct
74 Correct 11 ms 36956 KB Output is correct
75 Correct 14 ms 36956 KB Output is correct
76 Correct 12 ms 37056 KB Output is correct
77 Correct 11 ms 36956 KB Output is correct
78 Correct 11 ms 39004 KB Output is correct
79 Correct 10 ms 36956 KB Output is correct
80 Correct 9 ms 37300 KB Output is correct
81 Correct 11 ms 39260 KB Output is correct
82 Correct 15 ms 36956 KB Output is correct
83 Correct 13 ms 41108 KB Output is correct
84 Correct 8 ms 36444 KB Output is correct
85 Correct 8 ms 36084 KB Output is correct
86 Correct 13 ms 36168 KB Output is correct
87 Correct 8 ms 36192 KB Output is correct
88 Correct 10 ms 36820 KB Output is correct
89 Correct 11 ms 39264 KB Output is correct
90 Correct 11 ms 39252 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37212 KB Output is correct
2 Correct 4 ms 37208 KB Output is correct
3 Correct 4 ms 33116 KB Output is correct
4 Correct 11 ms 33116 KB Output is correct
5 Correct 23 ms 35164 KB Output is correct
6 Correct 5 ms 37212 KB Output is correct
7 Correct 21 ms 33116 KB Output is correct
8 Correct 7 ms 37212 KB Output is correct
9 Correct 8 ms 37212 KB Output is correct
10 Correct 7 ms 37212 KB Output is correct
11 Correct 4 ms 35164 KB Output is correct
12 Correct 4 ms 33116 KB Output is correct
13 Correct 5 ms 29020 KB Output is correct
14 Correct 4 ms 29116 KB Output is correct
15 Correct 3 ms 26972 KB Output is correct
16 Correct 4 ms 29020 KB Output is correct
17 Correct 3 ms 27072 KB Output is correct
18 Correct 4 ms 29016 KB Output is correct
19 Correct 3 ms 26972 KB Output is correct
20 Correct 6 ms 37208 KB Output is correct
21 Correct 4 ms 37212 KB Output is correct
22 Correct 4 ms 37312 KB Output is correct
23 Correct 5 ms 37360 KB Output is correct
24 Correct 4 ms 33112 KB Output is correct
25 Correct 4 ms 33216 KB Output is correct
26 Correct 4 ms 33116 KB Output is correct
27 Correct 4 ms 33116 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 4 ms 33116 KB Output is correct
30 Correct 3 ms 29152 KB Output is correct
31 Correct 0 ms 604 KB Output is correct
32 Correct 4 ms 33116 KB Output is correct
33 Correct 5 ms 35164 KB Output is correct
34 Correct 4 ms 33288 KB Output is correct
35 Correct 5 ms 37208 KB Output is correct
36 Correct 6 ms 37208 KB Output is correct
37 Correct 4 ms 33284 KB Output is correct
38 Correct 4 ms 33116 KB Output is correct
39 Correct 4 ms 33116 KB Output is correct
40 Correct 4 ms 33116 KB Output is correct
41 Correct 4 ms 35164 KB Output is correct
42 Correct 4 ms 33116 KB Output is correct
43 Correct 4 ms 33116 KB Output is correct
44 Correct 4 ms 33112 KB Output is correct
45 Correct 4 ms 33112 KB Output is correct
46 Correct 4 ms 33372 KB Output is correct
47 Correct 4 ms 33116 KB Output is correct
48 Correct 5 ms 37316 KB Output is correct
49 Correct 5 ms 33112 KB Output is correct
50 Correct 5 ms 37212 KB Output is correct
51 Correct 4 ms 33112 KB Output is correct
52 Correct 5 ms 33624 KB Output is correct
53 Correct 5 ms 33116 KB Output is correct
54 Correct 4 ms 37428 KB Output is correct
55 Correct 4 ms 33116 KB Output is correct
56 Correct 5 ms 37212 KB Output is correct
57 Correct 5 ms 37432 KB Output is correct
58 Correct 4 ms 33112 KB Output is correct
59 Correct 5 ms 33368 KB Output is correct
60 Correct 5 ms 33112 KB Output is correct
61 Correct 5 ms 35160 KB Output is correct
62 Correct 5 ms 33116 KB Output is correct
63 Correct 4 ms 33368 KB Output is correct
64 Correct 4 ms 33116 KB Output is correct
65 Correct 4 ms 33336 KB Output is correct
66 Correct 447 ms 86068 KB Output is correct
67 Correct 502 ms 97708 KB Output is correct
68 Correct 407 ms 107404 KB Output is correct
69 Correct 887 ms 93584 KB Output is correct
70 Correct 1016 ms 93928 KB Output is correct
71 Correct 477 ms 103292 KB Output is correct
72 Correct 502 ms 103060 KB Output is correct
73 Correct 776 ms 94152 KB Output is correct
74 Correct 473 ms 103332 KB Output is correct
75 Correct 485 ms 102708 KB Output is correct
76 Correct 719 ms 96216 KB Output is correct
77 Correct 463 ms 103328 KB Output is correct
78 Correct 687 ms 137024 KB Output is correct
79 Correct 616 ms 133592 KB Output is correct

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37212 KB Output is correct
2 Correct 4 ms 37208 KB Output is correct
3 Correct 4 ms 33116 KB Output is correct
4 Correct 11 ms 33116 KB Output is correct
5 Correct 23 ms 35164 KB Output is correct
6 Correct 5 ms 37212 KB Output is correct
7 Correct 21 ms 33116 KB Output is correct
8 Correct 7 ms 37212 KB Output is correct
9 Correct 8 ms 37212 KB Output is correct
10 Correct 7 ms 37212 KB Output is correct
11 Correct 4 ms 35164 KB Output is correct
12 Correct 4 ms 33116 KB Output is correct
13 Correct 5 ms 29020 KB Output is correct
14 Correct 4 ms 29116 KB Output is correct
15 Correct 3 ms 26972 KB Output is correct
16 Correct 4 ms 29020 KB Output is correct
17 Correct 3 ms 27072 KB Output is correct
18 Correct 4 ms 29016 KB Output is correct
19 Correct 3 ms 26972 KB Output is correct
20 Correct 6 ms 37208 KB Output is correct
21 Correct 4 ms 37212 KB Output is correct
22 Correct 4 ms 37312 KB Output is correct
23 Correct 5 ms 37360 KB Output is correct
24 Correct 4 ms 33112 KB Output is correct
25 Correct 4 ms 33216 KB Output is correct
26 Correct 4 ms 33116 KB Output is correct
27 Correct 4 ms 33116 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 4 ms 33116 KB Output is correct
30 Correct 3 ms 29152 KB Output is correct
31 Correct 0 ms 604 KB Output is correct
32 Correct 4 ms 33116 KB Output is correct
33 Correct 5 ms 35164 KB Output is correct
34 Correct 4 ms 33288 KB Output is correct
35 Correct 5 ms 37208 KB Output is correct
36 Correct 6 ms 37208 KB Output is correct
37 Correct 4 ms 33284 KB Output is correct
38 Correct 4 ms 33116 KB Output is correct
39 Correct 4 ms 33116 KB Output is correct
40 Correct 4 ms 33116 KB Output is correct
41 Correct 4 ms 35164 KB Output is correct
42 Correct 4 ms 33116 KB Output is correct
43 Correct 4 ms 33116 KB Output is correct
44 Correct 4 ms 33112 KB Output is correct
45 Correct 4 ms 33112 KB Output is correct
46 Correct 4 ms 33372 KB Output is correct
47 Correct 4 ms 33116 KB Output is correct
48 Correct 5 ms 37316 KB Output is correct
49 Correct 5 ms 33112 KB Output is correct
50 Correct 5 ms 37212 KB Output is correct
51 Correct 4 ms 33112 KB Output is correct
52 Correct 5 ms 33624 KB Output is correct
53 Correct 5 ms 33116 KB Output is correct
54 Correct 4 ms 37428 KB Output is correct
55 Correct 4 ms 33116 KB Output is correct
56 Correct 5 ms 37212 KB Output is correct
57 Correct 5 ms 37432 KB Output is correct
58 Correct 4 ms 33112 KB Output is correct
59 Correct 5 ms 33368 KB Output is correct
60 Correct 5 ms 33112 KB Output is correct
61 Correct 5 ms 35160 KB Output is correct
62 Correct 5 ms 33116 KB Output is correct
63 Correct 4 ms 33368 KB Output is correct
64 Correct 4 ms 33116 KB Output is correct
65 Correct 4 ms 33336 KB Output is correct
66 Correct 10 ms 41052 KB Output is correct
67 Correct 10 ms 41080 KB Output is correct
68 Correct 12 ms 41308 KB Output is correct
69 Correct 44 ms 38492 KB Output is correct
70 Correct 17 ms 38492 KB Output is correct
71 Correct 11 ms 36440 KB Output is correct
72 Correct 10 ms 36688 KB Output is correct
73 Correct 11 ms 41308 KB Output is correct
74 Correct 11 ms 36956 KB Output is correct
75 Correct 14 ms 36956 KB Output is correct
76 Correct 12 ms 37056 KB Output is correct
77 Correct 11 ms 36956 KB Output is correct
78 Correct 11 ms 39004 KB Output is correct
79 Correct 10 ms 36956 KB Output is correct
80 Correct 9 ms 37300 KB Output is correct
81 Correct 11 ms 39260 KB Output is correct
82 Correct 15 ms 36956 KB Output is correct
83 Correct 13 ms 41108 KB Output is correct
84 Correct 8 ms 36444 KB Output is correct
85 Correct 8 ms 36084 KB Output is correct
86 Correct 13 ms 36168 KB Output is correct
87 Correct 8 ms 36192 KB Output is correct
88 Correct 10 ms 36820 KB Output is correct
89 Correct 11 ms 39264 KB Output is correct
90 Correct 11 ms 39252 KB Output is correct
91 Correct 447 ms 86068 KB Output is correct
92 Correct 502 ms 97708 KB Output is correct
93 Correct 407 ms 107404 KB Output is correct
94 Correct 887 ms 93584 KB Output is correct
95 Correct 1016 ms 93928 KB Output is correct
96 Correct 477 ms 103292 KB Output is correct
97 Correct 502 ms 103060 KB Output is correct
98 Correct 776 ms 94152 KB Output is correct
99 Correct 473 ms 103332 KB Output is correct
100 Correct 485 ms 102708 KB Output is correct
101 Correct 719 ms 96216 KB Output is correct
102 Correct 463 ms 103328 KB Output is correct
103 Correct 687 ms 137024 KB Output is correct
104 Correct 616 ms 133592 KB Output is correct
105 Correct 1716 ms 67300 KB Output is correct
106 Correct 2307 ms 74496 KB Output is correct
107 Correct 4074 ms 82776 KB Output is correct
108 Correct 2716 ms 78276 KB Output is correct
109 Correct 578 ms 74148 KB Output is correct
110 Correct 507 ms 91252 KB Output is correct
111 Correct 436 ms 107960 KB Output is correct
112 Correct 462 ms 100264 KB Output is correct
113 Correct 508 ms 100396 KB Output is correct
114 Incorrect 2037 ms 105416 KB Output isn't correct
115 Halted 0 ms 0 KB -