結果
| 問題 | No.2543 Many Meetings |
| ユーザー |
 zjsdut
|
| 提出日時 | 2023-12-19 17:37:18 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 139 ms / 2,000 ms |
| コード長 | 26,958 bytes |
| コンパイル時間 | 1,571 ms |
| コンパイル使用メモリ | 136,976 KB |
| 実行使用メモリ | 23,652 KB |
| 最終ジャッジ日時 | 2023-12-19 17:37:24 |
| 合計ジャッジ時間 | 5,808 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,676 KB |
| testcase_01 | AC | 2 ms
6,676 KB |
| testcase_02 | AC | 2 ms
6,676 KB |
| testcase_03 | AC | 112 ms
23,652 KB |
| testcase_04 | AC | 112 ms
23,652 KB |
| testcase_05 | AC | 111 ms
23,652 KB |
| testcase_06 | AC | 111 ms
23,652 KB |
| testcase_07 | AC | 112 ms
23,652 KB |
| testcase_08 | AC | 139 ms
23,652 KB |
| testcase_09 | AC | 115 ms
23,652 KB |
| testcase_10 | AC | 116 ms
23,652 KB |
| testcase_11 | AC | 116 ms
23,652 KB |
| testcase_12 | AC | 116 ms
23,652 KB |
| testcase_13 | AC | 84 ms
19,468 KB |
| testcase_14 | AC | 47 ms
12,156 KB |
| testcase_15 | AC | 46 ms
11,880 KB |
| testcase_16 | AC | 69 ms
16,096 KB |
| testcase_17 | AC | 80 ms
18,644 KB |
| testcase_18 | AC | 83 ms
20,484 KB |
| testcase_19 | AC | 76 ms
18,988 KB |
| testcase_20 | AC | 76 ms
19,140 KB |
| testcase_21 | AC | 89 ms
21,660 KB |
| testcase_22 | AC | 74 ms
18,644 KB |
| testcase_23 | AC | 2 ms
6,676 KB |
| testcase_24 | AC | 2 ms
6,676 KB |
| testcase_25 | AC | 2 ms
6,676 KB |
| testcase_26 | AC | 2 ms
6,676 KB |
| testcase_27 | AC | 2 ms
6,676 KB |
| testcase_28 | AC | 86 ms
18,316 KB |
| testcase_29 | AC | 28 ms
7,976 KB |
| testcase_30 | AC | 28 ms
8,116 KB |
| testcase_31 | AC | 23 ms
7,244 KB |
| testcase_32 | AC | 77 ms
17,308 KB |
| testcase_33 | AC | 2 ms
6,676 KB |
| testcase_34 | AC | 2 ms
6,676 KB |
| testcase_35 | AC | 2 ms
6,676 KB |
| testcase_36 | AC | 2 ms
6,676 KB |
| testcase_37 | AC | 2 ms
6,676 KB |
| testcase_38 | AC | 2 ms
6,676 KB |
| testcase_39 | AC | 1 ms
6,676 KB |
| testcase_40 | AC | 2 ms
6,676 KB |
| testcase_41 | AC | 1 ms
6,676 KB |
| testcase_42 | AC | 2 ms
6,676 KB |
ソースコード
/**
* code generated by JHelperX
* More info: https://github.com/GoBigorGoHome/JHelperX
* @author zjs
*/
#if not defined LOCAL and not defined NDEBUG
#define NDEBUG
#endif
#define debug(...)
#define show(...)
extern const bool show_all_failed_tests = false;
extern const bool compare_real_numbers = false;
// #define INTERACTIVE_MODE //对于交互题，取消此行注释。
//
// Created by zjsdu on 5/28/2020.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_
#include <string>
#include <cassert>
#include <queue>
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_
#include <iostream>
#include <vector>
#include <tuple>
//
// Created by zjsdu on 10/22/2020.
//
#ifndef JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_
#define JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_
#include <type_traits>
#if __cplusplus >= 201703L
template<typename T> T type();// no definition
template<typename Container> auto value_type_of_() {
if constexpr (std::is_array_v<Container>)
return type<std::remove_extent_t<Container>>();
else
return type<typename Container::value_type>();
}
template<typename Container>
using value_type_of =
decltype(value_type_of_<std::remove_reference_t<Container>>());
#else
template <typename Container>
struct value_type_of_impl // default, non-array
{
using type = typename Container::value_type;
};
template <typename T, std::size_t N>
struct value_type_of_impl<T[N]> // arrays
{
using type = T;
};
template <typename Container>
using value_type_of = typename value_type_of_impl<Container>::type;
#endif
// Source: https://foonathan.net/2020/10/iife-metaprogramming/
#if __cplusplus >= 201703L
namespace is_iterable_impl {
using std::begin;
using std::end;
template<typename T>
using check_specs = std::void_t<
std::enable_if_t<
std::is_same<decltype(begin(std::declval<T &>())),// has begin()
decltype(end(std::declval<T &>())) // has end()
>::value>,// ... begin() and end() are the same type ...
decltype(*begin(std::declval<T &>()))>;// ... which can be dereferenced
template<typename, typename = void> struct is_iterable : std::false_type {};
// specialization
template<class T> struct is_iterable<T, check_specs<T>> : std::true_type {};
}// namespace is_iterable_impl
template<class T> using is_iterable = is_iterable_impl::is_iterable<T>;
template<typename T> constexpr bool is_iterable_v = is_iterable<T>::value;
// Source: https://stackoverflow.com/a/53429396/6793559
template<typename T>
using is_string =
std::disjunction<std::is_same<char *, typename std::decay_t<T>>,
std::is_same<const char *, typename std::decay_t<T>>,
std::is_same<std::string, typename std::decay_t<T>>>;
template<typename T> constexpr bool is_string_v = is_string<T>::value;
// Source: https://stackoverflow.com/a/57812868/6793559
template<template<typename...> typename Target, typename Aux, typename... Ts>
struct is_specialized_for_impl : std::false_type {};
template<template<typename...> typename Target, typename... Args>
struct is_specialized_for_impl<Target, decltype(sizeof(Target<Args...>)),
Args...> : std::true_type {};
template<template<typename...> typename Target, typename... Args>
using is_specialized_for =
is_specialized_for_impl<Target, std::size_t, Args...>;
template<template<typename...> typename Target, typename... Args>
constexpr bool is_specialized_for_v =
is_specialized_for<Target, Args...>::value;
template<typename T>
using is_tuple_like = is_specialized_for<std::tuple_size, T>;
template<typename T> constexpr bool is_tuple_like_v = is_tuple_like<T>::value;
template<typename T, typename = void> struct remove_all_extents_ {
typedef std::remove_reference_t<T> type;
};
template<typename T>
struct remove_all_extents_<T, std::void_t<decltype(std::declval<T>()[0])>> {
typedef
typename remove_all_extents_<decltype(std::declval<T>()[0])>::type type;
};
template<typename T, typename = void>
struct rank_ : public std::integral_constant<std::size_t, 0> {};
template<typename T>
struct rank_<T, std::void_t<decltype(std::declval<T>()[0])>>
: public std::integral_constant<
std::size_t, rank_<decltype(std::declval<T>()[0])>::value + 1> {};
#endif
#endif// JHELPER_EXAMPLE_PROJECT_TASKS_TYPE_TRAITS_HPP_
struct fast_ios {
fast_ios() {
#ifndef INTERACTIVE_MODE
std::cin.tie(nullptr);
#endif
std::ios::sync_with_stdio(false);
std::cout.precision(15);
std::cout << std::fixed;
};
} const fast_ios_;
namespace io {
template<typename T, typename U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &p);
template<typename... Ts>
std::istream &operator>>(std::istream &in, std::tuple<Ts...> &t);
template<typename... Ts>
std::ostream &operator<<(std::ostream &, const std::tuple<Ts...> &);
template<typename T, typename U>
std::istream &operator>>(std::istream &in, std::pair<T, U> &p) {
in >> p.first >> p.second;
return in;
}
template<typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &vec) {
for (auto &x : vec)
stream >> x;
return stream;
}
#if __cplusplus >= 201703L
template<typename... Ts>
std::istream &operator>>(std::istream &in, std::tuple<Ts...> &t) {
std::apply([&in](auto &...args) { ((in >> args), ...); }, t);
return in;
}
template<class... Args> void scan(Args &...args) {
((std::cin >> args), ...);
}
template<typename Container,
typename = std::enable_if_t<std::conjunction_v<
is_iterable<Container>, std::negation<is_string<Container>>>>>
std::ostream &operator<<(std::ostream &out, const Container &container) {
using std::begin;
using value_type =
std::remove_reference_t<decltype(*begin(std::declval<Container &>()))>;
constexpr char delimiter =
is_iterable_v<value_type> or is_tuple_like_v<value_type> ? '\n' : ' ';
bool first = true;
for (auto &element : container) {
if (first)
first = false;
else
out << delimiter;
out << element;
}
return out;
}
// Source: https://en.cppreference.com/w/cpp/utility/apply
template<typename... Ts>
std::ostream &operator<<(std::ostream &out, const std::tuple<Ts...> &theTuple) {
std::apply(
[&out](Ts const &...tupleArgs) {
std::size_t n{0};
((out << tupleArgs << (++n != sizeof...(Ts) ? " " : "")), ...);
},
theTuple);
return out;
}
#endif
template<typename T, typename U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &p) {
out << p.first << ' ' << p.second;
return out;
}
template<typename T>
std::ostream &operator<<(std::ostream &out,
const std::vector<std::vector<T>> &t) {
bool is_first = true;
for (const auto &row : t) {
if (is_first)
is_first = false;
else
out << '\n';
out << row;
}
return out;
}
std::ostream &operator<<(std::ostream &os, __int128 n) {
if (n < 0) {
n = -n;
os << '-';
}
std::string s;
while (n > 0) {
s += char('0' + n % 10);
n /= 10;
}
for (int i = (int) s.size() - 1; i >= 0; i--)
os << s[i];
return os;
}
#if __cplusplus >= 201703L
template<typename... Args> void pt(Args &&...args) {
((std::cout << args << ' '), ...);
}
template<typename First, typename... Args>
void pl(const First &first, const Args &...args) {
std::cout << first;
((std::cout << ' ' << args), ...);
std::cout << '\n';
}
template<typename... Args> void pn(const Args &...args) {
((std::cout << args << '\n'), ...);
}
#endif
}// namespace io
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_IO_HPP_
//
// Created by zjsdu on 10/26/2020.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_
template<typename T, unsigned Dimension> struct ndvec {
using type = std::vector<typename ndvec<T, Dimension - 1>::type>;
};
template<typename T> struct ndvec<T, 0> { using type = T; };
// arbitrary-dimensional array that allows non-constexpr extents.
// Usage: ndarray<dimension, value_type> arr(extents..., init_value);
// An initial value for all array items can be specified if all extensions are
// specified.
// Examples:
// ndarray<2, int> a(2, 3, -1);
// ndarray<3, int> b(2, 3, 4);
// ndarray<3, int> c(2, 3);
template<unsigned dimension, typename T>
class ndarray : public ndvec<T, dimension>::type {
using base_type = typename ndvec<T, dimension>::type;
using value_type = typename base_type::value_type;
using base_type::base_type;
public:
template<typename... Args>
ndarray(unsigned d, Args... args)
: std::vector<value_type>(d, ndarray<dimension - 1, T>(args...)) {}
};
template<typename T> class ndarray<1, T> : public std::vector<T> {
using std::vector<T>::vector;
};
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_NDARRAY_HPP_
//
// Created by zjsdu on 2/9/2021.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_
#define CALL_WITH_EXPANDED_ARGS(function, ...) function(__VA_ARGS__)
#define JOIN_IMPL(arg1, arg2) arg1##arg2
#define JOIN(arg1, arg2) JOIN_IMPL(arg1, arg2)
#define EXPAND_1(...) __VA_ARGS__
#define EXPAND_4(...) EXPAND_1(EXPAND_1(EXPAND_1(__VA_ARGS__)))
#define EXPAND_13(...) EXPAND_4(EXPAND_4(EXPAND_4(__VA_ARGS__)))
#define PAUSE
#define COMMA() ,
#define TERMINATE(...)
#define SELECT_SECOND_ARG(arg1, arg2, ...) arg2
#define CONDITIONAL(peek, arg1, arg2) \
CALL_WITH_EXPANDED_ARGS(SELECT_SECOND_ARG, COMMA peek arg1, arg2)
#define TERMINATE_OR(peek, arg) CONDITIONAL(peek, TERMINATE, arg)
#define FOR_EACH_2_IMPL0(function, arg1, arg2, peek, ...) \
function(arg1, arg2) TERMINATE_OR(peek, FOR_EACH_2_IMPL1) \
PAUSE(function, peek, __VA_ARGS__)
#define FOR_EACH_2_IMPL1(function, arg1, arg2, peek, ...) \
function(arg1, arg2) TERMINATE_OR(peek, FOR_EACH_2_IMPL0) \
PAUSE(function, peek, __VA_ARGS__)
#define FOR_EACH_2(function, ...) \
EXPAND_13(FOR_EACH_2_IMPL0(function, __VA_ARGS__, ()))
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_MACROS_H_
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using vl = std::vector<ll>;
using vb = std::vector<bool>;
using vi = std::vector<int>;
using vs = std::vector<std::string>;
using pii = std::pair<int, int>;
using pli = std::pair<ll, int>;
using pil = std::pair<int, ll>;
using pll = std::pair<ll, ll>;
using vii = std::vector<pii>;
template<typename T>
using pq = std::priority_queue<T>;
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template<typename... Ts> using vt = std::vector<std::tuple<Ts...>>;
template<typename T> using vv = ndarray<2, T>;
template<typename T> struct range_tuple {
const T &ref = beg;
T beg;
const T end;
range_tuple(T b, T e) : beg(b), end(e) {}
};
#define rng4(i, a, b, c) \
for (auto &&[i, JOIN(iter_, __LINE__), JOIN(end_, __LINE__)] = \
range_tuple<std::common_type<decltype(a), decltype(b)>::type>(a, \
b); \
i < JOIN(end_, __LINE__); JOIN(iter_, __LINE__) += c)
#define rng3(i, a, b) rng4(i, a, b, 1)
#define rng2(i, n) rng3(i, 0, n)
#define GET4(_1, _2, _3, _4, NAME, ...) NAME
#define rng(...) GET4(__VA_ARGS__, rng4, rng3, rng2)(__VA_ARGS__)
#define up4(i, a, b, c) rng (i, a, b + 1, c)
#define up3(i, a, b) up4(i, a, b, 1)
#define up(...) GET4(__VA_ARGS__, up4, up3, NO_IMPL)(__VA_ARGS__)
#define down4(i, b, a, c) \
for (auto &&[i, JOIN(iter_, __LINE__), JOIN(end_, __LINE__)] = \
range_tuple<std::common_type<decltype(a), decltype(b)>::type>(b, \
a); \
i >= JOIN(end_, __LINE__); JOIN(iter_, __LINE__) -= c)
#define down3(i, b, a) down4(i, b, a, 1)
#define down(...) GET4(__VA_ARGS__, down4, down3, NO_IMPL)(__VA_ARGS__)
#define rep(n) \
for (auto JOIN(_iter_, __LINE__) = n; JOIN(_iter_, __LINE__) > 0; \
--JOIN(_iter_, __LINE__))
#define FOR_LAST_OPERATION_IMPL(arg1, arg2) arg1] : arg2
#define FOR_NORMAL_OPERATION_IMPL(arg1, arg2) arg1,
#define FOR_IMPL0(arg1, arg2, peek, ...) \
CONDITIONAL(peek, FOR_LAST_OPERATION_IMPL, FOR_NORMAL_OPERATION_IMPL) \
(arg1, arg2) TERMINATE_OR(peek, FOR_IMPL1) PAUSE(arg2, peek, __VA_ARGS__)
#define FOR_IMPL1(arg1, arg2, peek, ...) \
CONDITIONAL(peek, FOR_LAST_OPERATION_IMPL, FOR_NORMAL_OPERATION_IMPL) \
(arg1, arg2) TERMINATE_OR(peek, FOR_IMPL0) PAUSE(arg2, peek, __VA_ARGS__)
#define FOR_IMPL3(arg1, arg2, peek, ...) \
CONDITIONAL(peek, for (auto && arg1 : arg2), \
for (auto && [EXPAND_13(FOR_IMPL0(arg1, arg2, peek, __VA_ARGS__))))
#define FOR(...) FOR_IMPL3(__VA_ARGS__, ())
#define ALL(x) std::begin(x), std::end(x)
// hat off to 300iq
#define RALL(x) std::rbegin(x), std::rend(x)
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define ep emplace
#define SZ(x) (int) (x).size()
#define rp(...) return pl(__VA_ARGS__)
#define rpn(...) return pn(__VA_ARGS__)
#define adv(i, n) \
for (auto JOIN(_n_, __LINE__) = n; i < JOIN(_n_, __LINE__); ++i)
#define radv(i, n) \
for (auto JOIN(_n_, __LINE__) = n; i > JOIN(_n_, __LINE__); --i)
#define INT(...) \
int __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define LL(...) \
long long __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define STR(...) \
std::string __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
io::scan(__VA_ARGS__)
#define NL \
[] { \
std::cout << '\n'; \
}()
#define RI \
([] { \
int x; \
std::cin >> x; \
return x; \
})()
#define READ_VI(NAME, LEN) \
std::vector<int> NAME(LEN); \
io::scan(NAME);
#define VI(...) FOR_EACH_2(READ_VI, __VA_ARGS__)
#define READ_VII(NAME, LEN) \
std::vector<std::pair<int, int>> NAME(LEN); \
io::scan(NAME);
#define VII(...) FOR_EACH_2(READ_VII, __VA_ARGS__)
#define READ_VL(NAME, LEN) \
std::vector<long long> NAME(LEN); \
io::scan(NAME);
#define VL(...) FOR_EACH_2(READ_VL, __VA_ARGS__)
#define READ_VS(NAME, LEN) \
std::vector<std::string> NAME(LEN); \
io::scan(NAME);
#define VS(...) FOR_EACH_2(READ_VS, __VA_ARGS__)
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_ALIAS_HPP_
#ifndef CP_UTILS
#define CP_UTILS
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <map>
#include <unordered_map>
#include <numeric>
#include <set>
#include <random>
#include <chrono>
inline void Yn(bool p) {
std::cout << (p ? "Yes\n" : "No\n");
}
inline void YN(bool p) {
std::cout << (p ? "YES\n" : "NO\n");
}
inline void yn(bool p) {
std::cout << (p ? "yes\n" : "no\n");
}
template<typename Container> Container inc(Container &&c) {
for (auto &e : c)
++e;
return std::forward<Container>(c);
}
template<typename Container> Container dec(Container &&c) {
for (auto &e : c)
--e;
return std::forward<Container>(c);
}
template<typename A, typename B>
bool chkmin(A& a, const B& b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename A, typename B>
bool chkmax(A& a, const B& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#if __cplusplus >= 201703L
template<typename A, typename B, typename... C>
bool chkmin(A& a, const B& b, const C&... c) {
if (B res = std::min<B>({b, c...}); res < a) {
a = res;
return true;
}
return false;
}
template<typename A, typename B, typename... C>
bool chkmax(A& a, const B& b, const C&... c) {
if (B res = std::max<B>({b, c...}); res > a) {
a = res;
return true;
}
return false;
}
#endif
template<typename T, typename U>
void append(T &container1, const U &container2) {
container1.insert(container1.end(), container2.begin(), container2.end());
}
template<typename T> int argmin(const std::vector<T> &a) {
return (int) (std::min_element(a.begin(), a.end()) - a.begin());
}
template<typename T> int argmax(const std::vector<T> &a) {
return (int) (std::max_element(a.begin(), a.end()) - a.begin());
}
template<typename Container> Container reverse(Container &&c) {
std::reverse(std::begin(c), std::end(c));
return std::forward<Container>(c);
}
template<typename Sequence> Sequence rev_copy(Sequence a) {
std::reverse(std::begin(a), std::end(a));
return a;
}
template<typename Sequence> Sequence uniq(Sequence &&s) {
std::sort(std::begin(s), std::end(s));
s.erase(std::unique(std::begin(s), std::end(s)), std::end(s));
return std::forward<Sequence>(s);
}
template<typename Container> auto max(const Container &c) {
assert(c.size() > 0);
return *std::max_element(std::begin(c), std::end(c));
}
template<typename Container> auto min(const Container &c) {
assert(c.size() > 0);
return *std::min_element(std::begin(c), std::end(c));
}
template<typename Array> int maxi(const Array &a) {
assert(a.size() > 0);
return int(std::max_element(std::begin(a), std::end(a)) - std::begin(a));
}
template<typename Array> int mini(const Array &a) {
assert(a.size() > 0);
return int(std::min_element(std::begin(a), std::end(a)) - std::begin(a));
}
template<typename Array, typename Value> auto lb(const Array &a, Value v) {
return std::lower_bound(std::begin(a), std::end(a), v);
}
template<typename Array, typename Value> auto ub(const Array &a, Value v) {
return std::upper_bound(std::begin(a), std::end(a), v);
}
template<typename Array, typename Value, typename Compare>
auto lb(const Array &a, Value v, Compare compare) {
return std::lower_bound(std::begin(a), std::end(a), v, compare);
}
template<typename Array, typename Value, typename Compare>
auto ub(const Array &a, Value v, Compare compare) {
return std::upper_bound(std::begin(a), std::end(a), v, compare);
}
template<typename Array, typename Value> int lbi(const Array &a, Value v) {
return int(lb(a, v) - std::begin(a));
}
template<typename Iter, typename Value> int lbi(Iter beg, int count, Value v) {
assert(count > 0);
return int(std::lower_bound(beg, beg + count, v) - beg);
}
template<typename Iter, typename Value> int ubi(Iter beg, int count, Value v) {
assert(count > 0);
return int(std::upper_bound(beg, beg + count, v) - beg);
}
template<typename Array, typename Value> int ubi(const Array &a, Value v) {
return int(ub(a, v) - std::begin(a));
}
template<typename Container>
Container iota(Container &&c, value_type_of<Container> v) {
std::iota(std::begin(c), std::end(c), v);
return std::forward<Container>(c);
}
template<typename T, typename Comp>
std::vector<int> argsort(const std::vector<T> &array, Comp comp) {
std::vector<int> res(array.size());
std::iota(res.begin(), res.end(), 0);
std::stable_sort(res.begin(), res.end(), [&array, comp](int i, int j) {
return comp(array[i], array[j]);
});
return res;
}
template<typename T> std::vector<int> argsort(const std::vector<T>& array) {
std::vector<int> res(array.size());
std::iota(res.begin(), res.end(), 0);
std::stable_sort(res.begin(), res.end(),
[&array](int i, int j) { return array[i] < array[j]; });
return res;
}
template<typename T> std::vector<int> order(const std::vector<T>& array) {
int n = (int) array.size();
std::vector<int> I(n);
std::iota(I.begin(), I.end(), 0);
std::sort(I.begin(), I.end(),
[&array](int i, int j) { return array[i] < array[j]; });
std::vector<int> order(n);
for (int i = 1; i < n; i++)
order[I[i]] = order[I[i - 1]] + (array[I[i - 1]] < array[I[i]]);
return order;
}
#if __cplusplus >=201703L
template<typename Container, typename Compare = void *>
Container sort(Container &&c, Compare comp = nullptr) {
if constexpr (std::is_same_v<Compare, void *>)
std::sort(std::begin(c), std::end(c));
else
std::sort(std::begin(c), std::end(c), comp);
return std::forward<Container>(c);
}
#endif
template<typename T> struct reversion_wrapper { T &iterable; };
template<typename T> auto begin(reversion_wrapper<T> w) {
using std::rbegin;
return rbegin(w.iterable);
}
template<typename T> auto end(reversion_wrapper<T> w) {
using std::rend;
return rend(w.iterable);
}
template<typename T> reversion_wrapper<T> rev_view(T &&iterable) {
return {std::forward<T>(iterable)};
}
/// @return nearest integer not less than the quotient x/y.
template<typename T, typename U> T qceil(T x, U y) {
assert(y > 0);
T q = x / y;
return q + (q * y < x);
}
/// @return nearest integer not greater than the quotient x/y.
template<typename T, typename U> T qfloor(T x, U y) {
assert(y > 0);
T q = x / y;
return q - (q * y > x);
}
template<typename T, typename U> std::pair<T, U> divmod(T x, U y) {
assert(y > 0);
T q = qfloor(x, y);
return {q, x - q * y};
};
/// @return nearest multiple of y not less than x.
template<typename T, typename U> T mceil(T x, U y) {
assert(y > 0);
return qceil(x, y) * y;
}
/// @return nearest multiple of y not greater than x.
template<typename T, typename U> T mfloor(T x, U y) {
assert(y > 0);
return qfloor(x, y) * y;
}
#if __cplusplus >= 201703L
template<class...> struct typelist {};
template<class T, class... Ts>
constexpr bool any_same = (std::is_same<T, Ts>::value || ...);
template<class F> struct y_combinator {
template<class... TLs> struct ref {
y_combinator &self;
template<class... Args> decltype(auto) operator()(Args &&...args) const {
using G = std::conditional_t<any_same<typelist<Args...>, TLs...>,
ref<TLs...>, ref<TLs..., typelist<Args...>>>;
return self.f(G{self}, std::forward<Args>(args)...);
}
};
F f;
template<class... Args> decltype(auto) operator()(Args &&...args) {
return ref<>{*this}(std::forward<Args>(args)...);
}
};
template<class F> y_combinator(F) -> y_combinator<F>;
#endif
template<typename T> constexpr T INF = std::numeric_limits<T>::max() / 2;
/// @brief Usage: acc\<type_of_sum\>(array)
template<typename T, typename U> T acc(const U& array) {
return std::accumulate(std::begin(array), std::end(array), T(0));
}
template <typename T> T acc(const std::vector<T>& array) {
return std::accumulate(array.begin(), array.end(), T(0));
}
// maps values of a into 0, 1, 2, ..., preserving order.
template<typename T> std::vector<int> normalize(const std::vector<T> &a) {
assert(not a.empty());
int n = (int) a.size();
std::vector<int> I = argsort(a);
std::vector<int> b(a.size());
b[I[0]] = 0;
for (int i = 1; i < n; i++)
b[I[i]] = b[I[i - 1]] + (a[I[i - 1]] < a[I[i]]);
return b;
}
template<typename F, typename Int>
Int binary_search(F check, Int ok, Int ng, bool check_ok = true) {
if (check_ok)
assert(check(ok));
while (std::abs(ok - ng) > 1) {
Int x = ng + (ok - ng) / 2;
(check(x) ? ok : ng) = x;
}
return ok;
}
template<typename T, typename Int> int bit(T a, Int i) {
return a >> i & 1;
}
#define popcnt(x) __builtin_popcountll((x))
// sign used in principle of inclusion-exclusion
int pie_sign(int s) {
assert(s >= 0);
return popcnt(s) & 1 ? -1 : 1;
}
#endif// CP_UTILS
//
// Created by zjs on 12/19/23.
//
#ifndef JHELPER_EXAMPLE_PROJECT_LIBRARY_LEVEL_ANCESTOR_HPP_
#define JHELPER_EXAMPLE_PROJECT_LIBRARY_LEVEL_ANCESTOR_HPP_
// also known as doubling technique, jump pointers
class level_ancestor {
int n;
int log;
std::vector<std::vector<int>> a;
public:
explicit level_ancestor(const std::vector<int> &parent)
: n((int) parent.size()) {
log = 0;
int t = 1;
while (t < n) {
log++;
t *= 2;
}
a.assign(log, std::vector<int>(n, -1));
if (log) {
a[0] = parent;
for (int i = 1; i < log; i++)
for (int j = 0; j < n; j++)
if (a[i - 1][j] != -1)
a[i][j] = a[i - 1][a[i - 1][j]];
}
}
int ancestor(int u, int k) const {
if (k >= n)
return -1;
int v = u;
for (int i = 0; i < log; i++)
if (k >> i & 1) {
v = a[i][v];
if (v == -1)
break;
}
return v;
}
};
#endif// JHELPER_EXAMPLE_PROJECT_LIBRARY_LEVEL_ANCESTOR_HPP_
using namespace io;
using namespace std;
void solve() {
// 树形结构
INT(n, k);
vii a(n);
scan(a);
sort(a);
debug(a);
vi pa(n);
vector<pii> b;
rng (i, n) {
auto [l, r] = a[i];
b.pb({r, i});
b.pb({l, i + n});
}
sort(b);
int pre = -1;
FOR (x, i, b) {
if (i >= n)
pa[i - n] = pre;
else if (pre == -1 || a[i].first > a[pre].first)
pre = i;
}
debug(pa);
level_ancestor la(pa);
int ans = INT_MAX;
rng (i, n) {
int j = la.ancestor(i, k - 1);
debug(j);
if (j != -1) {
chkmin(ans, a[i].second - a[j].first);
}
}
if (ans == INT_MAX)
ans = -1;
pl(ans);
}
#include <iostream>
int main() {
#if defined FILE_IO and not defined LOCAL
freopen(FILE_IO ".in", "r", stdin);
freopen(FILE_IO ".out", "w", stdout);
#endif
solve();
return 0;
}