Submission #2245636
Source Code Expand
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define pr1(a) (#a)<<"="<<(a)
#define pr2(a,b) pr1(a)<<", "<<pr1(b)
#define pr3(a,b,c) pr2(a,b)<<", "<<pr1(c)
#define pr4(a,b,c,d) pr3(a,b,c)<<", "<<pr1(d)
#define pr5(a,b,c,d,e) pr4(a,b,c,d)<<", "<<pr1(e)
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<60;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}
signed main(){
int n;
cin>>n;
vector<P> A(n);
cin>>A;
for(auto &a:A) a = P(min(a.first,a.second),max(a.first,a.second));
for(auto &a:A) a = P(a.first,-a.second);
sort(A.begin(),A.end()),greater<P>();
for(auto &a:A) a.second *= -1;
vector<P> num;
for(int i=0;i<n;i++){
int a,b; tie(a,b) = A[i];
num.push_back(P(a,-(i+1)));
num.push_back(P(b,(i+1)));
}
sort(num.begin(),num.end(),greater<P>());
set<P> R,B;
set<P> RB;
auto top=[](set<P>&S){return *S.begin();};
auto back=[](set<P> &S){return *(--S.end());};
auto toptop=[](set<P> &S){return *(++S.begin());};
auto backback=[](set<P>&S){return *(--(--S.end()));};
auto calc=[](int a,int b,int c,int d){return (a-b)*(c-d);};
int ans = INF;
int cnt = 0;
for(int i=0;i<2*n;i++){
int idx = abs(num[i].second) - 1;
if(num[i].second > 0){
cnt++;
R.insert(P(A[idx].second,idx));
B.insert(P(A[idx].first,idx));
}
if(num[i].second < 0 && idx != n-1){
R.erase(P(A[idx].second,idx));
B.erase(P(A[idx].first,idx));
RB.insert(P(A[idx].first,(-idx-1)));
RB.insert(P(A[idx].second,(idx+1)));
}
//cout<<endl;
//cout<<"R: "; prArr(R);
//cout<<"B: "; prArr(B);
//cout<<"RB: ";prArr(RB);
if(cnt < n) continue;
if(num[i].second < 0 && idx != n-1){
R.insert(P(A[idx].first,idx));
B.insert(P(A[idx].second,idx));
RB.erase(P(A[idx].first,(-idx-1)));
RB.erase(P(A[idx].second,(idx+1)));
}
auto del=[&](){
if(num[i].second < 0 && idx != n-1){
R.erase(P(A[idx].first,idx));
B.erase(P(A[idx].second,idx));
RB.insert(P(A[idx].first,(-idx-1)));
RB.insert(P(A[idx].second,(idx+1)));
}
};
int a = back(R).first;
int b = top(R).first;
int c = back(B).first;
int d = top(B).first;
Min(ans,calc(a,b,c,d));
if((int)RB.size() < 2) {del();continue;}
if(top(RB).second != -back(RB).second){
Min(ans,calc(a,b, max(c,top(RB).first), min(d,back(RB).first)));
}
else if((int)RB.size() >= 4){
Min(ans, calc(a,b, max(c, top(RB).first), min(d, backback(RB).first)));
Min(ans, calc(a,b, max(c, toptop(RB).first), min(d, back(RB).first)));
}
del();
}
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Ball Coloring |
User |
haji |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3547 Byte |
Status |
WA |
Exec Time |
1379 ms |
Memory |
36456 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 |
597 ms |
35048 KB |
div21 |
WA |
614 ms |
34664 KB |
div22 |
WA |
591 ms |
35304 KB |
div23 |
WA |
590 ms |
35304 KB |
div24 |
WA |
625 ms |
35816 KB |
example0 |
AC |
1 ms |
256 KB |
example1 |
AC |
1 ms |
256 KB |
example2 |
AC |
1 ms |
256 KB |
maxrand0 |
WA |
615 ms |
34664 KB |
maxrand1 |
WA |
599 ms |
35944 KB |
maxrand2 |
WA |
618 ms |
35176 KB |
maxrand20 |
WA |
560 ms |
35048 KB |
maxrand21 |
WA |
602 ms |
35688 KB |
maxrand210 |
AC |
1379 ms |
35816 KB |
maxrand211 |
WA |
589 ms |
36072 KB |
maxrand22 |
WA |
615 ms |
36328 KB |
maxrand23 |
WA |
681 ms |
36200 KB |
maxrand24 |
WA |
744 ms |
35816 KB |
maxrand25 |
WA |
603 ms |
34792 KB |
maxrand26 |
WA |
564 ms |
36456 KB |
maxrand27 |
WA |
670 ms |
34664 KB |
maxrand28 |
WA |
724 ms |
35176 KB |
maxrand29 |
WA |
698 ms |
35176 KB |
maxrand3 |
WA |
600 ms |
35432 KB |
maxrand4 |
WA |
607 ms |
35944 KB |
smallrand0 |
WA |
1 ms |
256 KB |
smallrand1 |
AC |
1 ms |
256 KB |
smallrand2 |
WA |
1 ms |
256 KB |
smallrand3 |
AC |
1 ms |
256 KB |
smallrand4 |
WA |
1 ms |
256 KB |
sparse0 |
WA |
455 ms |
35688 KB |
sparse1 |
WA |
455 ms |
34920 KB |
sparse2 |
WA |
448 ms |
35688 KB |
sparse3 |
WA |
446 ms |
35560 KB |
sparse4 |
WA |
447 ms |
34664 KB |