Page Contents
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


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
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield
February Long Challenge 2021
- Frog Sort Solution Codechef
- Chef and Meetings Solution Codechef
- Maximise Function Solution Codechef
- Highest Divisor Solution Codechef
- Cut the Cake Challenge Solution Codechef
- Dream and the Multiverse Solution Codechef
- Cell Shell Solution Codechef
- Multiple Games Solution Codechef
- Another Tree with Number Theory Solution Codechef
- XOR Sums Solution Codechef
- Prime Game Solution CodeChef
- Team Name Solution Codechef
- Bash Matrix Solution CodeChef