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