Submission #1259798
Source Code Expand
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,a,n) for(int i=a;i<n;i++)
#define REP(i,n) for(int i=0;i<=n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define mp(a,b) make_pair(a,b)
#define fst first
#define scn second
const ll inf = (ll)1e9 + 7;
const ll mod = (ll)1e9 + 7;
const ld eps = 1e-9;
class segtree {
public:
vint big, sml;
int N=1;
segtree(int n,vint dat) {
while (N < n) N <<= 1;
big.resize(2 * N); sml.resize(2 * N);
rep(i, 2 * N) {
big[i] = 0;
sml[i] = inf;
}
rep(i, n) big[N - 1 + i] = sml[N - 1 + i] = dat[i];
rrep(i, N - 1) {
big[i] = max(big[2 * i + 1], big[2 * i + 2]);
sml[i] = min(sml[2 * i + 1], sml[2 * i + 2]);
}
}
int getmin(int l, int r, int a, int b, int k) {
if (r <= a || b <= l) return inf;
if (a <= l&&r <= b) return sml[k];
return min(this->getmin(l, (l + r) / 2, a, b, 2 * k + 1), this->getmin((l + r) / 2, r, a, b, 2 * k + 2));
}
int getmax(int l, int r, int a, int b, int k) {
if (r <= a || b <= l) return 0;
if (a <= l&&r <= b) return big[k];
return max(this->getmax(l, (l + r) / 2, a, b, 2 * k + 1), this->getmax((l + r) / 2, r, a, b, 2 * k + 2));
}
};
int x[200010], y[200010];
int n;
ll solve1() {//different colored
vint r(n,0), b(n,0);
rep(i, n) {
r[i]=max(x[i], y[i]);
b[i]=min(x[i], y[i]);
}
sort(r.begin(), r.end());
sort(b.begin(), b.end());
return (ll)(r[n - 1] - r[0])*(b[n - 1] - b[0]);
}
ll solve2() {//same colored
vector<pii> dat(n);
rep(i, n) dat[i] = mp(min(x[i], y[i]), max(x[i], y[i]));
sort(dat.begin(), dat.end());
vint r(n), b(n);
rep(i, n) r[i] = dat[i].fst, b[i] = dat[i].scn;
segtree red(n, r), blue(n, b);
ll ret = 1e18;
rep(i, n) {//[0,i)をreverseする
ll rbig = max(red.getmax(0, red.N, 0, i, 0), blue.getmax(0, blue.N, i, n, 0));
ll rsml = min(red.getmin(0, red.N, 0, i, 0), blue.getmin(0, blue.N, i, n, 0));
ll bbig = max(blue.getmax(0, blue.N, 0, i, 0), red.getmax(0, red.N, i, n, 0));
ll bsml = min(blue.getmin(0, blue.N, 0, i, 0), red.getmin(0, red.N, i, n, 0));
ret = min(ret, (bbig - bsml)*(rbig - rsml));
}
return ret;
}
int main() {
cin >> n;
rep(i, n) cin >> x[i] >> y[i];
ll ret1 = solve1();
ll ret2 = solve2();
cout << min(ret1,ret2) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Ball Coloring |
User |
fiord |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2722 Byte |
Status |
AC |
Exec Time |
429 ms |
Memory |
13920 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 |
416 ms |
13920 KB |
div21 |
AC |
416 ms |
13920 KB |
div22 |
AC |
417 ms |
13920 KB |
div23 |
AC |
417 ms |
13920 KB |
div24 |
AC |
417 ms |
13920 KB |
example0 |
AC |
1 ms |
256 KB |
example1 |
AC |
1 ms |
256 KB |
example2 |
AC |
1 ms |
256 KB |
maxrand0 |
AC |
418 ms |
13920 KB |
maxrand1 |
AC |
415 ms |
13920 KB |
maxrand2 |
AC |
418 ms |
13920 KB |
maxrand20 |
AC |
408 ms |
13920 KB |
maxrand21 |
AC |
414 ms |
13920 KB |
maxrand210 |
AC |
416 ms |
13920 KB |
maxrand211 |
AC |
414 ms |
13920 KB |
maxrand22 |
AC |
415 ms |
13920 KB |
maxrand23 |
AC |
418 ms |
13920 KB |
maxrand24 |
AC |
418 ms |
13920 KB |
maxrand25 |
AC |
412 ms |
13920 KB |
maxrand26 |
AC |
413 ms |
13920 KB |
maxrand27 |
AC |
417 ms |
13920 KB |
maxrand28 |
AC |
429 ms |
13920 KB |
maxrand29 |
AC |
420 ms |
13920 KB |
maxrand3 |
AC |
417 ms |
13920 KB |
maxrand4 |
AC |
416 ms |
13920 KB |
smallrand0 |
AC |
1 ms |
256 KB |
smallrand1 |
AC |
1 ms |
256 KB |
smallrand2 |
AC |
1 ms |
256 KB |
smallrand3 |
AC |
1 ms |
256 KB |
smallrand4 |
AC |
1 ms |
256 KB |
sparse0 |
AC |
402 ms |
13920 KB |
sparse1 |
AC |
403 ms |
13920 KB |
sparse2 |
AC |
407 ms |
13920 KB |
sparse3 |
AC |
407 ms |
13920 KB |
sparse4 |
AC |
405 ms |
13920 KB |