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