Submission #1519409


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

            if (y[i] < bmin) {
                bmin = y[i];
            } else if (bmax < x[i]) {
                bmax = x[i];
            } else if (x[i] < bmin && bmax < y[i]) {
                // assert(false);
            }
        }

        // 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 0
Code Size 6410 Byte
Status WA
Exec Time 46 ms
Memory 3456 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 2
WA × 1
AC × 15
WA × 20
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 WA 44 ms 3456 KB
div21 WA 44 ms 3456 KB
div22 AC 44 ms 3328 KB
div23 AC 45 ms 3328 KB
div24 AC 45 ms 3456 KB
example0 WA 1 ms 256 KB
example1 AC 1 ms 256 KB
example2 AC 1 ms 256 KB
maxrand0 AC 46 ms 3456 KB
maxrand1 WA 44 ms 3456 KB
maxrand2 AC 44 ms 3456 KB
maxrand20 WA 44 ms 3328 KB
maxrand21 WA 44 ms 3328 KB
maxrand210 WA 44 ms 3328 KB
maxrand211 WA 44 ms 3456 KB
maxrand22 WA 44 ms 3456 KB
maxrand23 WA 44 ms 3328 KB
maxrand24 WA 44 ms 3456 KB
maxrand25 WA 44 ms 3328 KB
maxrand26 WA 44 ms 3456 KB
maxrand27 WA 44 ms 3456 KB
maxrand28 WA 44 ms 3456 KB
maxrand29 WA 44 ms 3456 KB
maxrand3 AC 44 ms 3328 KB
maxrand4 AC 44 ms 3328 KB
smallrand0 AC 1 ms 256 KB
smallrand1 WA 1 ms 256 KB
smallrand2 WA 1 ms 256 KB
smallrand3 WA 1 ms 256 KB
smallrand4 WA 1 ms 256 KB
sparse0 AC 44 ms 3328 KB
sparse1 AC 44 ms 3328 KB
sparse2 AC 44 ms 3328 KB
sparse3 AC 44 ms 3456 KB
sparse4 AC 45 ms 3328 KB