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