Submission #3194446
Source Code Expand
#include <string> #include <vector> #include <sstream> #include <iostream> #include <algorithm> #include <map> #include <list> #include <set> #include <numeric> #include <queue> #include <stack> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <cstring> #include <climits> #include <cfloat> #include <ctime> #include <complex> #include <cassert> #include <array> #include <bitset> #include <unordered_map> #include <random> using namespace std; typedef long long LL; typedef pair<int,int> P; const int L=200*1000; P bs[L]; int N; int main() { cin >> N; for(int i=0;i<N;i++){ int x,y; cin >> x >> y; if(x>y){ swap(x,y); } bs[i]=P(x,y); } sort(bs,bs+N); int r0,r1,b0,b1; r0=bs[0].first; r1=bs[N-1].first; b0=b1=bs[0].second; for(int i=1;i<N;i++){ b0=min(b0,bs[i].second); b1=max(b1,bs[i].second); } LL ret=(r1-r0)*(LL)(b1-b0); //cerr << ret << endl; r1=b1; int m0,m1; m0=m1=bs[0].second; //cerr << r0 << ", " << r1 << endl; for(int i=1;i<N;i++){ b0=min(bs[i].first,m0); b1=max(bs[N-1].first,m1); //cerr << b0 << ": " << b1 << endl; ret=min(ret,(r1-r0)*(LL)(b1-b0)); m0=min(m0,bs[i].second); m1=max(m1,bs[i].second); } cout << ret << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Ball Coloring |
User | yukuai |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1302 Byte |
Status | AC |
Exec Time | 234 ms |
Memory | 1792 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 | 224 ms | 1792 KB |
div21 | AC | 228 ms | 1792 KB |
div22 | AC | 224 ms | 1792 KB |
div23 | AC | 227 ms | 1792 KB |
div24 | AC | 228 ms | 1792 KB |
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
maxrand0 | AC | 227 ms | 1792 KB |
maxrand1 | AC | 222 ms | 1792 KB |
maxrand2 | AC | 226 ms | 1792 KB |
maxrand20 | AC | 218 ms | 1792 KB |
maxrand21 | AC | 229 ms | 1792 KB |
maxrand210 | AC | 225 ms | 1792 KB |
maxrand211 | AC | 230 ms | 1792 KB |
maxrand22 | AC | 227 ms | 1792 KB |
maxrand23 | AC | 233 ms | 1792 KB |
maxrand24 | AC | 226 ms | 1792 KB |
maxrand25 | AC | 230 ms | 1792 KB |
maxrand26 | AC | 230 ms | 1792 KB |
maxrand27 | AC | 226 ms | 1792 KB |
maxrand28 | AC | 234 ms | 1792 KB |
maxrand29 | AC | 229 ms | 1792 KB |
maxrand3 | AC | 223 ms | 1792 KB |
maxrand4 | AC | 226 ms | 1792 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 | 226 ms | 1792 KB |
sparse1 | AC | 222 ms | 1792 KB |
sparse2 | AC | 232 ms | 1792 KB |
sparse3 | AC | 225 ms | 1792 KB |
sparse4 | AC | 228 ms | 1792 KB |