Submission #3773352


Source Code Expand

#include<cstdio>
#include<algorithm>
const int maxn=400010;
int n;
int a[maxn];
int ps[maxn],rk[maxn];
int rv[maxn];
long long ans;
int In() {
	register char c;
	for(;c=getchar(),c!='-'&&(c<'0'||c>'9'););
	register bool f=c=='-';
	register int s=f?0:c-'0';
	for(;c=getchar(),c>='0'&&c<='9';)s=s*10+c-'0';
	return f?-s:s;
}
bool cmp(const int &x,const int &y) {
	return a[x]<a[y];
}
void cmin(register long long &a,register long long b) {
	a>b?a=b:0;
}
int dmin(register int a,register int b) {
	return a<b?a:b;
}
int main() {
	ans=1ll<<60;
	n=In();
	for(register int i=1;i<=n;++i)a[i]=In(),a[i+n]=In();
	if(n==1) return puts("0"),0;
	for(register int i=1;i<=n*2;++i)ps[i]=i;
	std::sort(ps+1,ps+n*2+1,cmp);
	for(register int i=1;i<=n*2;++i)rk[ps[i]]=i;
	for(register int i=1;i<=n*2;++i)if(ps[i]<=n) rv[rv[i]=rk[ps[i]+n]]=i;
	register int lm=2;
	while(rv[lm]!=1&&lm<rv[lm])++lm;
	register int xx=a[ps[rv[n*2]]];
	for(register int i=n*2-1;i>=1;--i) {
		cmin(ans,1ll*(a[ps[n*2]]-a[ps[lm]])*(a[ps[i]]-a[ps[1]]));
		cmin(ans,1ll*(a[ps[n*2]]-a[ps[1]])*(a[ps[i]]-dmin(a[ps[lm]],xx)));
		if(rv[i]==n*2||rv[i]>i) break;
		xx>a[ps[rv[i]]]?xx=a[ps[rv[i]]]:0;
	}
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Submission Time
Task E - Ball Coloring
User LeehWinCing
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1230 Byte
Status AC
Exec Time 92 ms
Memory 6400 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 35
Set Name Test Cases
Sample example0, example1, example2
All div20, div21, div22, div23, div24, example0, example1, example2, maxrand0, maxrand1, maxrand2, maxrand20, maxrand21, maxrand210, maxrand211, maxrand22, maxrand23, maxrand24, maxrand25, maxrand26, maxrand27, maxrand28, maxrand29, maxrand3, maxrand4, smallrand0, smallrand1, smallrand2, smallrand3, smallrand4, sparse0, sparse1, sparse2, sparse3, sparse4
Case Name Status Exec Time Memory
div20 AC 91 ms 6400 KB
div21 AC 91 ms 6400 KB
div22 AC 91 ms 6400 KB
div23 AC 91 ms 6400 KB
div24 AC 90 ms 6400 KB
example0 AC 1 ms 4224 KB
example1 AC 1 ms 4224 KB
example2 AC 1 ms 4224 KB
maxrand0 AC 90 ms 6400 KB
maxrand1 AC 91 ms 6400 KB
maxrand2 AC 90 ms 6400 KB
maxrand20 AC 78 ms 6400 KB
maxrand21 AC 80 ms 6400 KB
maxrand210 AC 74 ms 6400 KB
maxrand211 AC 79 ms 6400 KB
maxrand22 AC 82 ms 6400 KB
maxrand23 AC 85 ms 6400 KB
maxrand24 AC 92 ms 6400 KB
maxrand25 AC 77 ms 6400 KB
maxrand26 AC 78 ms 6400 KB
maxrand27 AC 84 ms 6400 KB
maxrand28 AC 88 ms 6400 KB
maxrand29 AC 92 ms 6400 KB
maxrand3 AC 90 ms 6400 KB
maxrand4 AC 92 ms 6400 KB
smallrand0 AC 1 ms 4224 KB
smallrand1 AC 1 ms 4224 KB
smallrand2 AC 1 ms 4224 KB
smallrand3 AC 1 ms 4224 KB
smallrand4 AC 1 ms 4224 KB
sparse0 AC 67 ms 6400 KB
sparse1 AC 68 ms 6400 KB
sparse2 AC 68 ms 6400 KB
sparse3 AC 68 ms 6400 KB
sparse4 AC 68 ms 6400 KB