結果
問題 | No.1715 Dinner 2 |
ユーザー | keijak |
提出日時 | 2021-10-22 22:58:45 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,757 bytes |
コンパイル時間 | 3,533 ms |
コンパイル使用メモリ | 276,176 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-23 06:50:44 |
合計ジャッジ時間 | 4,697 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | WA | - |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | WA | - |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | WA | - |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | WA | - |
testcase_11 | AC | 10 ms
5,376 KB |
testcase_12 | AC | 11 ms
5,376 KB |
testcase_13 | AC | 8 ms
5,376 KB |
testcase_14 | AC | 9 ms
5,376 KB |
testcase_15 | AC | 9 ms
5,376 KB |
testcase_16 | AC | 12 ms
5,376 KB |
testcase_17 | AC | 8 ms
5,376 KB |
testcase_18 | AC | 4 ms
5,376 KB |
testcase_19 | AC | 6 ms
5,376 KB |
testcase_20 | AC | 6 ms
5,376 KB |
testcase_21 | AC | 4 ms
5,376 KB |
testcase_22 | AC | 5 ms
5,376 KB |
testcase_23 | AC | 5 ms
5,376 KB |
testcase_24 | WA | - |
testcase_25 | AC | 7 ms
5,376 KB |
testcase_26 | AC | 5 ms
5,376 KB |
testcase_27 | AC | 7 ms
5,376 KB |
testcase_28 | AC | 8 ms
5,376 KB |
testcase_29 | AC | 10 ms
5,376 KB |
testcase_30 | AC | 8 ms
5,376 KB |
testcase_31 | AC | 10 ms
5,376 KB |
testcase_32 | AC | 17 ms
5,376 KB |
testcase_33 | AC | 15 ms
5,376 KB |
testcase_34 | AC | 15 ms
5,376 KB |
testcase_35 | AC | 12 ms
5,376 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | WA | - |
testcase_38 | WA | - |
ソースコード
#include <bits/stdc++.h> #define REP_(i, a_, b_, a, b, ...) \ for (int i = (a), END_##i = (b); i < END_##i; ++i) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define ALL(x) std::begin(x), std::end(x) using Int = long long; using Real = long double; template<typename T, typename U> inline bool chmax(T &a, U b) { return a < b and ((a = std::move(b)), true); } template<typename T, typename U> inline bool chmin(T &a, U b) { return a > b and ((a = std::move(b)), true); } template<typename T> inline int ssize(const T &a) { return (int) a.size(); } inline void check(bool cond, const char *message = "!ERROR!") { if (not cond) { std::cout.flush(), std::cerr.flush(); throw std::runtime_error(message); } } template<class T> inline std::ostream &print_one(const T &x, char endc) { if constexpr (std::is_same_v<T, bool>) { return std::cout << (x ? "Yes" : "No") << endc; } else { return std::cout << x << endc; } } template<class T> inline std::ostream &print(const T &x) { return print_one(x, '\n'); } template<typename T, typename... Ts> std::ostream &print(const T &head, Ts... tail) { return print_one(head, ' '), print(tail...); } inline std::ostream &print() { return std::cout << '\n'; } template<typename Container> std::ostream &print_seq(const Container &a, const char *sep = " ", const char *ends = "\n", std::ostream &os = std::cout) { auto b = std::begin(a), e = std::end(a); for (auto it = std::begin(a); it != e; ++it) { if (it != b) os << sep; os << *it; } return os << ends; } template<typename T, typename = void> struct is_iterable : std::false_type {}; template<typename T> struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>())), decltype(std::end(std::declval<T>()))>> : std::true_type { }; template<typename T, typename = std::enable_if_t< is_iterable<T>::value && !std::is_same<T, std::string>::value>> std::ostream &operator<<(std::ostream &os, const T &a) { return print_seq(a, ", ", "", (os << "{")) << "}"; } struct CastInput { template<typename T> operator T() const { T x; std::cin >> x; return x; } struct Sized { std::size_t n; template<typename T> operator T() const { T x(n); for (auto &e: x) std::cin >> e; return x; } }; Sized operator()(std::size_t n) const { return {n}; } } const in; #ifdef MY_DEBUG #include "debug_dump.hpp" #include "backward.hpp" backward::SignalHandling kSignalHandling; #else #define DUMP(...) #define cerr if(false)std::cerr #endif using namespace std; template<int sign = 1> struct Infinity { template<typename T> constexpr operator T() const { static_assert(sign == 1 or not std::is_unsigned_v<T>, "must be positive in an unsigned type"); if constexpr (std::numeric_limits<T>::has_infinity) { return T(sign) * std::numeric_limits<T>::infinity(); } else { static_assert(std::numeric_limits<T>::max() != T()); // max must be defined return T(sign) * (std::numeric_limits<T>::max() / T(2)); } } constexpr Infinity<sign * -1> operator-() const { return {}; } template<typename T> friend constexpr bool operator==(const T &x, const Infinity &y) { return x == T(y); } template<typename T> friend constexpr bool operator!=(const T &x, const Infinity &y) { return x != T(y); } }; constexpr Infinity<> kBig; template<typename Monoid> struct SegmentTree { using T = typename Monoid::T; int n_; // number of valid leaves. int offset_; // where leaves start std::vector<T> data_; // data size: 2*offset_ inline int size() const { return n_; } inline int offset() const { return offset_; } explicit SegmentTree(int n) : n_(n) { offset_ = 1; while (offset_ < n_) offset_ <<= 1; data_.assign(2 * offset_, Monoid::id()); } explicit SegmentTree(const std::vector<T> &leaves) : n_(leaves.size()) { offset_ = 1; while (offset_ < n_) offset_ <<= 1; data_.assign(2 * offset_, Monoid::id()); for (int i = 0; i < n_; ++i) { data_[offset_ + i] = leaves[i]; } for (int i = offset_ - 1; i > 0; --i) { data_[i] = Monoid::op(data_[i * 2], data_[i * 2 + 1]); } } // Sets i-th value (0-indexed) to x. void set(int i, const T &x) { int k = offset_ + i; data_[k] = x; // Update its ancestors. while (k > 1) { k >>= 1; data_[k] = Monoid::op(data_[k * 2], data_[k * 2 + 1]); } } // Queries by [l,r) range (0-indexed, half-open interval). T fold(int l, int r) const { l = std::max(l, 0) + offset_; r = std::min(r, offset_) + offset_; T vleft = Monoid::id(), vright = Monoid::id(); for (; l < r; l >>= 1, r >>= 1) { if (l & 1) vleft = Monoid::op(vleft, data_[l++]); if (r & 1) vright = Monoid::op(data_[--r], vright); } return Monoid::op(vleft, vright); } T fold_all() const { return data_[1]; } // Returns i-th value (0-indexed). T operator[](int i) const { return data_[offset_ + i]; } friend std::ostream &operator<<(std::ostream &os, const SegmentTree &st) { os << "["; for (int i = 0; i < st.size(); ++i) { if (i != 0) os << ", "; const auto &x = st[i]; os << x; } return os << "]"; } }; // 2 largest items in an interval. struct Max2Op { using value_type = pair<Int, int>; using T = std::array<value_type, 2>; static T op(const T &x, const T &y) { std::array<value_type, 4> a = {x[0], x[1], y[0], y[1]}; std::sort(std::begin(a), std::end(a)); return {a[3], a[2]}; } static constexpr T id() { return {pair{std::numeric_limits<Int>::lowest(), -1}, pair{std::numeric_limits<Int>::lowest(), -1}}; } }; template<class T> T floor_div(T x, T y) { check(y != 0); return x / y - (((x ^ y) < 0) and (x % y)); } // Binary search: // auto ok_bound = bisect(ok, ng, [&](i64 x) -> bool { return ...; }); template<class T, class F> auto bisect(T true_x, T false_x, F pred) -> T { static_assert(std::is_invocable_r_v<bool, F, T>); assert(std::max(true_x, false_x) <= std::numeric_limits<T>::max() / 2); while (std::abs(true_x - false_x) > 1) { T mid = floor_div<T>(true_x + false_x, 2); if (pred(mid)) { true_x = std::move(mid); } else { false_x = std::move(mid); } } return true_x; } template<typename T> struct Compressed { std::vector<T> values; explicit Compressed(std::vector<T> v) : values(v) { std::sort(values.begin(), values.end()); values.erase(std::unique(values.begin(), values.end()), values.end()); } int size() const { return values.size(); } const T &value(int i) const { return values[i]; } int index(const T &x) const { return std::lower_bound(values.begin(), values.end(), x) - values.begin(); } bool contains(const T &x) const { return std::binary_search(values.begin(), values.end(), x); } }; auto solve() { int n = in, D = in; vector<pair<Int, Int>> menu(n); REP(i, n) { menu[i].first = Int(in); menu[i].second = Int(in); } map<Int, vector<Int>> pq; vector<Int> ps; REP(i, n) { auto[pi, qi] = menu[i]; pq[pi].push_back(qi); ps.push_back(pi); } for (auto&[k, v]: pq) { sort(ALL(v), greater{}); } Compressed<Int> cp(ps); SegmentTree<Max2Op> seg(cp.size()); REP(i, n) { auto[pi, qi] = menu[i]; int j = cp.index(pi); Int val = -pi + qi; auto cur = seg[j]; if (val <= cur[1].first) continue; cur[1] = {val, i}; if (cur[0] < cur[1]) swap(cur[0], cur[1]); seg.set(j, cur); } Int ans = bisect<Int>(-(Int) kBig, (Int) kBig, [&](Int x) { REP(i, n) { auto[pi, qi] = menu[i]; Int bot = -pi; if (bot < x) continue; Int cur = -pi + qi; int last = i; REP(j, 1, D) { check(cur >= x); Int lb = -(cur - x); auto delta_max = seg.fold(cp.index(lb), cp.size()); pair<Int, int> delta; if (delta_max[0].second == last) { delta = delta_max[1]; } else { delta = delta_max[0]; } if (delta.second == -1) { goto skip_to_next; } last = delta.second; if (chmin(bot, cur - menu[last].first)) { if (bot < x) { goto skip_to_next; } } cur += delta.first; } return true; skip_to_next: continue; } return false; }); return ans; } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); cout << std::fixed << std::setprecision(18); const int T = 1;//in; REP(t, T) { auto ans = solve(); print(ans); } }