Submission #1689830
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int,int> pa;
#define w1 first
#define w2 second
#define ls (x<<1)
#define rs (x<<1|1)
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) ((x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
num=0;T f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
num*=f;
}
int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=1ll*x*x%p)if(k&1)res=1ll*res*x%p;return res;}
const int maxn=2e5+5;
int n;
int maxis[maxn],minip[maxn],maxip[maxn],minis[maxn];
pa w[maxn];
bool cmp(pa a,pa b){return a.w2<b.w2;}
int main(){
read(n);
// srand(20);
// n=3;
if(n==1)return puts("0"),0;
rep(i,1,n){
read(w[i].w1),read(w[i].w2);
// w[i].w1=rand()%100;
// w[i].w2=rand()%100;
// cerr<<w[i].w1<<" "<<w[i].w2<<endl;
if(w[i].w1>w[i].w2)swap(w[i].w1,w[i].w2);
}
sort(w+1,w+n+1);
int dlt=w[n].w1-w[1].w1,last=w[n].w1;
sort(w+2,w+n+1,cmp);
rep(i,1,n)maxip[i]=max(maxip[i-1],w[i].w2);
minip[0]=1e9+10;rep(i,1,n)minip[i]=min(minip[i-1],w[i].w2);
per(i,n,1)maxis[i]=max(maxis[i+1],w[i].w2);
minis[n+1]=1e9+10;per(i,n,1)minis[i]=min(minis[i+1],w[i].w2);
ll ans=1ll*dlt*(maxip[n]-minip[n]);
rep(i,2,n-1)if(w[i].w2>=last){
int maxi=max(max(maxip[i-1],maxis[i+1]),w[i].w1);
int mini=min(min(minip[i-1],minis[i+1]),w[i].w1);
ans=min(ans,1ll*(w[i].w2-w[1].w1)*(maxi-mini));
}
int mini=w[n].w1,maxi=w[n].w1;
per(i,n-1,2){
if(w[i].w2>=min(mini,minip[i-1]))
ans=min(ans,1ll*(w[n].w2-w[1].w1)*(w[i].w2-min(mini,minip[i-1])));
mini=min(mini,w[i].w1);
maxi=max(maxi,w[i].w1);
}
mini=min(mini,w[1].w2);
maxi=max(maxi,w[1].w2);
ans=min(ans,1ll*(maxi-mini)*(w[n].w2-w[1].w1));
printf("%lld\n",ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Ball Coloring |
User |
Vegetable |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2102 Byte |
Status |
WA |
Exec Time |
73 ms |
Memory |
4992 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
WA |
70 ms |
4992 KB |
div21 |
WA |
70 ms |
4992 KB |
div22 |
WA |
70 ms |
4864 KB |
div23 |
WA |
70 ms |
4864 KB |
div24 |
WA |
70 ms |
4864 KB |
example0 |
WA |
2 ms |
2304 KB |
example1 |
AC |
2 ms |
2304 KB |
example2 |
AC |
2 ms |
2304 KB |
maxrand0 |
WA |
70 ms |
4992 KB |
maxrand1 |
WA |
70 ms |
4992 KB |
maxrand2 |
WA |
70 ms |
4864 KB |
maxrand20 |
AC |
67 ms |
4864 KB |
maxrand21 |
AC |
67 ms |
4864 KB |
maxrand210 |
AC |
63 ms |
4864 KB |
maxrand211 |
AC |
69 ms |
4864 KB |
maxrand22 |
AC |
70 ms |
4864 KB |
maxrand23 |
AC |
71 ms |
4992 KB |
maxrand24 |
WA |
71 ms |
4864 KB |
maxrand25 |
AC |
68 ms |
4992 KB |
maxrand26 |
AC |
68 ms |
4992 KB |
maxrand27 |
AC |
71 ms |
4864 KB |
maxrand28 |
AC |
73 ms |
4992 KB |
maxrand29 |
AC |
72 ms |
4864 KB |
maxrand3 |
WA |
70 ms |
4864 KB |
maxrand4 |
WA |
71 ms |
4864 KB |
smallrand0 |
WA |
2 ms |
2304 KB |
smallrand1 |
WA |
2 ms |
2304 KB |
smallrand2 |
WA |
2 ms |
2304 KB |
smallrand3 |
WA |
2 ms |
2304 KB |
smallrand4 |
AC |
2 ms |
2304 KB |
sparse0 |
WA |
60 ms |
4864 KB |
sparse1 |
WA |
60 ms |
4992 KB |
sparse2 |
WA |
60 ms |
4992 KB |
sparse3 |
WA |
60 ms |
4992 KB |
sparse4 |
WA |
61 ms |
4864 KB |