AtCoder Regular Contest 073

Submission #1259798

Source codeソースコード

#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

Task問題 E - Ball Coloring
User nameユーザ名 fiord
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 2722 Byte
File nameファイル名
Exec time実行時間 429 ms
Memory usageメモリ使用量 13920 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0,example1,example2
All 700 / 700 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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