Cell Shell Solution Codechef

by

Cell Shell Solution February Challenge 2021

There is a checkered field with 105105 rows (numbered 11 through 105105) and 105105 columns (numbered 11 through 105105). NN different cells in this field (numbered 11 through NN) are marked; for each valid ii, the coordinates of the ii-th marked cell are (xi,yi)(xi,yi).

Also See: February Long Challenge 2021 Solutions

A set of cells is suitable if it meets the following conditions:

  • All marked cells belong to this set.
  • For any two cells aa and bb belonging to this set, there is a path between them with length |xa−xb|+|ya−yb||xa−xb|+|ya−yb| which only visits cells in this set. Each pair of consecutive cells in a path must have a common side.

You need to find the smallest possible size of a suitable set of cells, as well as the number of sets with this smallest size. Since the number of sets may be very large, compute it modulo 109+7109+7.

Input

  • The first line of the input contains two space-separated integers NN and TT.
  • NN lines follow. For each valid ii, the ii-th of these lines contains two space-separated integers xixi and yiyi.

Output

  • If T=0T=0, print a single line containing one integer ― the smallest size of a suitable set.
  • If T=1T=1, print a single line containing two space-separated integers ― the smallest size of a suitable set and the number of sets with this size modulo 109+7109+7.

Constraints

  • 1≤N≤1051≤N≤105
  • 0≤T≤10≤T≤1
  • 1≤xi,yi≤1051≤xi,yi≤105 for each valid ii

Subtasks

Subtask #1 (10 points):

  • T=1T=1
  • xi≤5xi≤5 for each valid ii
  • yi≤4yi≤4 for each valid ii

Subtask #2 (30 points): T=0T=0

Subtask #3 (60 points): original constraints

Example Input

6 1
3 3
4 3
1 1
5 4
5 2
2 2

Example Output

10 2

Explanation

The two suitable sets with the smallest size 1010 are

Cell Shell Solution Codechef
Cell Shell Solution Codechef

Follow us on telegram for quick update an abundance of free knowledge: Click Here

Solution

Program C++:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int MAXN = 200010;
const int INF = 2147483600;
const int MAX = 100001;
const LL Mod = 1e9+7;

int N,T; int L[MAXN+1],R[MAXN+1],fa[MAXN+1];
struct data{ int x,y; data(int xx=0,int yy=0){x=xx; y=yy;} }mn[MAXN+1],mx[MAXN+1],q[MAXN*2+1];
bool cmpx(data a,data b){ return a.x<b.x; }
inline data Max(data a,data b){ return data(max(a.x,b.x),max(a.y,b.y)); }
inline data Min(data a,data b){ return data(min(a.x,b.x),min(a.y,b.y)); }
inline int find(int x){ return (fa[x]==x?x:(fa[x]=find(fa[x]))); }
inline void merge(int x,int y){
	x=find(x),y=find(y);
	//cout<<"mgt:"<<x<<" "<<y<<endl;
	if(x==y) return ; fa[y]=x; 
	mx[x]=Max(mx[x],mx[y]);
	mn[x]=Min(mn[x],mn[y]); return ;
}
inline void mergeX(int l,int r){
	//cout<<"mergeX:"<<l<<" "<<r<<endl;
	for(int i=l,last;i<r;i=last+1){
		last=mx[find(i)].x;
		if(last<r) merge(last,last+1);
	} return ;
}
inline void mergeY(int l,int r){
	//cout<<"mergeY:"<<l<<" "<<r<<endl;
	for(int i=l,last;i<r;i=last+1){
		last=mx[find(i+MAX)].y;
		if(last<r) merge(last+MAX,last+1+MAX);
	} return ;
}
int top,sta[MAXN+1];
inline void Merge(){
	for(int i=1;i<=2*MAX;i++) fa[i]=i;
	for(int i=1;i<=MAX;i++) mn[i]=data(i,INF),mx[i]=data(i,-INF);
	for(int i=1;i<=MAX;i++) mn[i+MAX]=data(INF,i),mx[i+MAX]=data(-INF,i);
	for(int i=1;i<=MAX;i++) L[i]=INF,R[i]=-INF;
	for(int i=1;i<=N;i++) L[q[i].x]=min(L[q[i].x],q[i].y),R[q[i].x]=max(R[q[i].x],q[i].y); top=0;
	for(int i=1;i<=MAX;i++){
		if(L[i]<=R[i]){
			//cout<<"sq:"<<L[i]<<" "<<R[i]<<endl;
			int l=1,r=top,pos=top+1;
			while(l<=r){
				int mid=(l+r)>>1;
				if(L[i]<=mx[find(sta[mid])].y) pos=mid,r=mid-1;
				else l=mid+1;
			} if(pos>top){
				mergeY(L[i],R[i]);
				merge(L[i]+MAX,i);
				sta[++top]=i;
			} else{
				while(top>pos){
					data A=mn[find(sta[top-1])],B=mx[find(sta[top])];
					mergeX(A.x,B.x); mergeY(A.y,B.y); --top;
				}
				int lt=mn[find(sta[top])].y,rt=mx[find(sta[top])].y;
				int b=mn[find(sta[top])].x;
				mergeX(b,i); mergeY(min(lt,L[i]),max(rt,R[i]));
			}
		}
	} return ;
} LL ans,ans2;
int L2[MAXN+1],R2[MAXN+1];
LL inv[MAXN+1],ifac[MAXN+1],fac[MAXN+1];
inline void Count(int l,int r){
	//cout<<"count:"<<l<<" "<<r<<endl;
	L2[r]=L[r]; R2[r]=R[r];
	for(int i=r-1;i>=l;i--) L2[i]=min(L2[i+1],L[i]),R2[i]=max(R2[i+1],R[i]);
	for(int i=l+1;i<=r;i++) L[i]=min(L[i-1],L[i]),R[i]=max(R[i-1],R[i]);
	for(int i=l;i<=r;i++){ ans+=min(R[i],R2[i])-max(L[i],L2[i])+1; //cout<<"x "<<i<<": "<<max(L[i],L2[i])<<" "<<min(R[i],R2[i])<<endl; 
	}
	return ;
}
inline LL C(LL n,LL m){ if(n<m) return 0; return fac[n]*ifac[m]%Mod*ifac[n-m]%Mod; }
inline LL calc(data a,data b){
	return C(abs(a.x-b.x)+abs(a.y-b.y),abs(a.x-b.x));
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	inv[1]=ifac[0]=fac[0]=1;
	for(int i=2;i<=2*MAX;i++) inv[i]=(Mod-(Mod/i)*inv[Mod%i]%Mod)%Mod;
	for(int i=1;i<=2*MAX;i++) ifac[i]=ifac[i-1]*inv[i]%Mod,fac[i]=fac[i-1]*i%Mod;
	N=read(),T=read();
	for(int i=1;i<=N;i++){
		q[i].x=read(),q[i].y=read();
	} sort(q+1,q+N+1,cmpx);
	if(q[1].y>q[N].y){
		for(int i=1;i<=N;i++)
			q[i].y=MAX-q[i].y+1;
	} Merge(); 
	//return 0;
	ans=0,ans2=1;
	for(int i=1;i<top;i++){
		data A=mx[find(sta[i])],B=mn[find(sta[i+1])];
		ans+=abs(A.x-B.x)+abs(A.y-B.y)-1;
		ans2=ans2*calc(A,B)%Mod;
		q[++N].x=A.x; q[N].y=A.y;
		q[++N].x=B.x; q[N].y=B.y;
	} top=0; sort(q+1,q+N+1,cmpx); Merge();
	//cout<<"q:\n";
	//for(int i=1;i<=N;i++) cout<<q[i].x<<" "<<q[i].y<<endl;
	for(int i=1;i<=top;i++) Count(mn[find(sta[i])].x,mx[find(sta[i])].x);
	if(T) printf("%lld %lld\n",ans,ans2);
	else printf("%lld\n",ans);
	return 0;
}

Program Python:

n = int(input())
i=10
while n%i!=0:
    i=i-1
print(i)

Codechef Long Challenges

September Long Challenge 2021 Solution

February Long Challenge 2021

Leave a Comment

20 + 1 =