Submission #1519424


Source Code Expand

/*** Template Begin ***/

#define USING_BOOST
#define USING_NAMESPACE

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

auto init_ = [] {
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed;
    return 0;
}();

template <typename T>
inline T in() {
    T x;
    std::cin >> x;
    return x;
}

template <typename T>
inline void in(T &x) {
    std::cin >> x;
}

template <typename T, typename... Ts>
inline void in(T &t, Ts &... ts) {
    std::cin >> t;
    in(ts...);
}

template <typename T, typename U = std::vector<T>>
inline U vin(int n) {
    U v(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> v[i];
    }
    return v;
}

template <typename T, typename U = std::vector<T>, typename V = std::vector<U>>
inline V vin(int h, int w) {
    V vv(h, U(w));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            std::cin >> vv[i][j];
        }
    }
    return vv;
}

template <typename T>
inline void out(const T &x) {
    std::cout << x << std::endl;
}

template <char delimiter = ' ', typename T, typename... Ts>
inline void out(const T &t, const Ts &... ts) {
    std::cout << t << delimiter;
    out(ts...);
}

template <char delimiter = ' ', typename T>
inline void vout(const T &v, int n) {
    for (int i = 0; i < n; ++i) {
        if (i) std::cout << delimiter;
        std::cout << v[i];
    }
    std::cout << std::endl;
}

template <char delimiter = ' ', typename T>
inline void vout(const T &v, int h, int w) {
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (j) std::cout << delimiter;
            std::cout << v[i][j];
        }
        std::cout << std::endl;
    }
}

template <typename T, size_t D>
struct multi_vector_type {
    using type = std::vector<typename multi_vector_type<T, D - 1>::type>;
};

template <typename T>
struct multi_vector_type<T, 1> {
    using type = std::vector<T>;
};

template <typename T>
struct multi_vector_type<T, 0> {
    using type = T;
};

template <typename T, size_t D>
using multi_vector = typename multi_vector_type<T, D>::type;

template <typename T, size_t D, class = typename std::enable_if<D == 0>::type>
T make_vector(const T &val = T()) {
    return val;
}

template <typename T, size_t D = 1, typename... Ts,
          class = typename std::enable_if<D != 0>::type>
multi_vector<T, D> make_vector(size_t n, Ts &&... args) {
    return multi_vector<T, D>(n, make_vector<T, D - 1>(args...));
}

namespace detail {

template <typename F>
struct Debug {
    const char *delim_ = "\n";
    F fun;

    Debug(F f) : fun(f) {}

    ~Debug() { fun(delim_); }

    Debug &delim(const char *d) {
        delim_ = d;
        return *this;
    }
};

std::deque<std::string> split(const std::string &s, char c) {
    std::deque<std::string> v;
    std::stringstream ss(s);
    std::string x;
    while (std::getline(ss, x, c)) v.emplace_back(x);
    return v;
}

template <typename T>
void deb(const char *delim, std::deque<std::string> v, T a) {
    std::cerr << v[0].substr(v[0][0] == ' ', v[0].length()) << " = " << a
              << '\n';
    std::cerr << std::flush;
}

template <typename T, typename... Args>
void deb(const char *delim, std::deque<std::string> v, T a, Args... args) {
    std::cerr << v[0].substr(v[0][0] == ' ', v[0].length()) << " = " << a
              << delim;
    v.pop_front();
    deb(delim, std::move(v), args...);
}

template <typename... Args>
auto wrap(std::deque<std::string> v, Args... args) {
    auto f = [=](const char *delim = "\n") { deb(delim, v, args...); };

    return Debug<decltype(f)>(f);
}
}

#define debug(args...) ::detail::wrap(::detail::split(#args, ','), args)

#ifdef USING_BOOST

#include <boost/math/common_factor.hpp>
#include <boost/range.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/algorithm_ext.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/numeric.hpp>

inline auto rep(int begin, int end) {
    if (begin > end) {
        return boost::irange(0, 0);
    } else {
        return boost::irange(begin, end);
    }
}

inline auto rep(int begin, int end, int step) {
    if ((step > 0 && begin > end) || (step < 0 && begin < end)) {
        return boost::irange(0, 0, step);
    } else {
        return boost::irange(begin, end, step);
    }
}

#endif

#ifdef USING_NAMESPACE
using namespace std;

#ifdef USING_BOOST
using namespace boost;
using namespace boost::adaptors;
#endif
#endif

/*** Template End ***/

int main() {
    int64_t n;
    in(n);

    vector<int64_t> x(n), y(n);
    for (int i : rep(0, n)) {
        in(x[i], y[i]);

        if (x[i] > y[i]) {
            swap(x[i], y[i]);
        }
    }

    int j = min_element(x) - x.begin();
    int k = max_element(y) - y.begin();

    int64_t ans = 1LL << 61;

    if (j != k) {
        int64_t rmin = x[j], rmax = y[k], bmin = min(y[j], x[k]),
                bmax = max(y[j], x[k]);

        for (int i : rep(0, n)) {
            if (i == j || i == k) {
                continue;
            }

            bmin = min(bmin, y[i]);
            bmax = max(bmax, x[i]);
        }

        vector<pair<int64_t, int64_t>> ps;

        ps.emplace_back(bmin, bmax);

        for (int i : rep(0, n)) {
            if (i == j || i == k) {
                continue;
            }

            if (x[i] < bmin && bmax < y[i]) {
                ps.emplace_back(x[i], y[i]);
            }
        }

        sort(ps);
        priority_queue<int64_t> que;
        for (int i : rep(0, ps.size())) {
            bmin = ps[i].first;
            que.push(ps[i].second);

            bmax = que.top();

            ans = min(ans, (rmax - rmin) * (bmax - bmin));
        }

        sort(ps, [](auto x, auto y) {
            return std::tie(x.second, x.first) < std::tie(y.second, y.first);
        });
        priority_queue<int64_t, vector<int64_t>, greater<int64_t>> que2;
        for (int i : rep(0, ps.size()) | reversed) {
            bmax = ps[i].second;
            que2.push(ps[i].first);

            bmin = que2.top();

            ans = min(ans, (rmax - rmin) * (bmax - bmin));
        }
    }

    {
        int64_t rmin = x[j], rmax = x[k], bmin = y[j], bmax = y[k];

        for (int i : rep(0, n)) {
            if (i == j || i == k) {
                continue;
            }

            rmax = max(rmax, x[i]);
            bmin = min(bmin, y[i]);
        }

        ans = min(ans, (rmax - rmin) * (bmax - bmin));
    }

    out(ans);
}

Submission Info

Submission Time
Task E - Ball Coloring
User mino
Language C++14 (GCC 5.4.1)
Score 700
Code Size 7228 Byte
Status AC
Exec Time 48 ms
Memory 3456 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 45 ms 3328 KB
div21 AC 45 ms 3328 KB
div22 AC 45 ms 3328 KB
div23 AC 45 ms 3328 KB
div24 AC 45 ms 3456 KB
example0 AC 1 ms 256 KB
example1 AC 1 ms 256 KB
example2 AC 1 ms 256 KB
maxrand0 AC 45 ms 3456 KB
maxrand1 AC 45 ms 3328 KB
maxrand2 AC 45 ms 3456 KB
maxrand20 AC 45 ms 3328 KB
maxrand21 AC 45 ms 3328 KB
maxrand210 AC 45 ms 3328 KB
maxrand211 AC 45 ms 3328 KB
maxrand22 AC 45 ms 3456 KB
maxrand23 AC 45 ms 3328 KB
maxrand24 AC 46 ms 3328 KB
maxrand25 AC 45 ms 3328 KB
maxrand26 AC 45 ms 3328 KB
maxrand27 AC 46 ms 3456 KB
maxrand28 AC 46 ms 3456 KB
maxrand29 AC 45 ms 3328 KB
maxrand3 AC 45 ms 3328 KB
maxrand4 AC 45 ms 3328 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 45 ms 3456 KB
sparse1 AC 45 ms 3456 KB
sparse2 AC 45 ms 3456 KB
sparse3 AC 45 ms 3456 KB
sparse4 AC 48 ms 3456 KB