Submission #2234921


Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)

int n;

i64 x[202020][2];

int main(){
	cin >> n;
	rep(i,1,n) cin >> x[i][0] >> x[i][1];
	rep(i,1,n) if(x[i][0] < x[i][1]) swap(x[i][0] , x[i][1]);
	x[0][0] = 0;
	x[0][1] = 1e9;
	int MAX = 0;
	int MIN = 0;
	rep(i,1,n){
		if(x[MAX][0] < x[i][0]) MAX = i;
		if(x[MIN][1] > x[i][1]) MIN = i;
	}
	i64 result = 1e18;
	//patten 1. Rmax = MAX , Rmin = MIN
	if(MAX != MIN){
		i64 RMAX = x[MAX][0];
		i64 BMIN = x[MIN][1];
		i64 RMIN = 1e9;
		i64 BMAX = 0;
		rep(i,1,n){
				RMIN = min(RMIN,x[i][0]);
				BMAX = max(BMAX,x[i][1]);
		}
		result = (RMAX - RMIN) * (BMAX - BMIN);
	}

	//patten2 . Rmax = MAX,Rmin = MIN
	{
		i64 RDIF = x[MAX][0] - x[MIN][1];
		set<P> st;
		rep(i,1,n) st.insert({x[i][0],i});
		while(true){
			i64 BDIF = (st.rbegin()->first) - (st.begin()->first);
			result = min(result , RDIF * BDIF);

			P p = *st.rbegin();
			st.erase(*st.rbegin());
			if(p.second == -1) break;
			st.insert({x[p.second][1] , -1});
		}
	}

	cout << result << endl;
}

Submission Info

Submission Time
Task E - Ball Coloring
User niuez
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1306 Byte
Status AC
Exec Time 315 ms
Memory 15872 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 234 ms 15872 KB
div21 AC 234 ms 15872 KB
div22 AC 233 ms 15872 KB
div23 AC 234 ms 15872 KB
div24 AC 234 ms 15872 KB
example0 AC 1 ms 256 KB
example1 AC 1 ms 256 KB
example2 AC 1 ms 256 KB
maxrand0 AC 233 ms 15872 KB
maxrand1 AC 233 ms 15872 KB
maxrand2 AC 235 ms 15872 KB
maxrand20 AC 272 ms 15872 KB
maxrand21 AC 286 ms 15872 KB
maxrand210 AC 262 ms 15872 KB
maxrand211 AC 282 ms 15872 KB
maxrand22 AC 296 ms 15872 KB
maxrand23 AC 305 ms 15872 KB
maxrand24 AC 301 ms 15872 KB
maxrand25 AC 289 ms 15872 KB
maxrand26 AC 271 ms 15872 KB
maxrand27 AC 307 ms 15872 KB
maxrand28 AC 306 ms 15872 KB
maxrand29 AC 315 ms 15872 KB
maxrand3 AC 233 ms 15872 KB
maxrand4 AC 234 ms 15872 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 222 ms 15872 KB
sparse1 AC 219 ms 15872 KB
sparse2 AC 220 ms 15872 KB
sparse3 AC 223 ms 15872 KB
sparse4 AC 220 ms 15872 KB