API tools faq
paste
gt22

Untitled

gt22
May 11th, 2020
2,530
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.81 KB | None | 0 0
raw download clone embed print report
  1. #include <vector>
  2. #include <functional>
  3. #include <optional>
  4. #include <iostream>
  5. #include "optimization.h"
  6.  
  7. using namespace std;
  8. using ll = long long;
  9.  
  10. template<typename T>
  11. struct Monoid;
  12.  
  13. template<typename Mon>
  14. struct ValidMonoid : private Mon {
  15.     using value_type = typename Mon::value_type;
  16.     using T = typename Mon::value_type;
  17.     static_assert(std::is_same_v<decltype(Mon::compose(std::declval<T>(), std::declval<T>())), T>);
  18.     static_assert(std::is_same_v<decltype(Mon::identity()), T>);
  19.     using Mon::compose;
  20.     using Mon::identity;
  21. };
  22.  
  23.  
  24. template<typename T>
  25. struct Updater : Updater<Monoid<T>> {
  26.     using valid = ValidMonoid<Monoid<T>>;
  27. };
  28.  
  29. template<typename Upd>
  30. struct ValidUpdater : private Upd {
  31.     using value_type = typename Upd::value_type;
  32.     using update_type = typename Upd::update_type;
  33.     using T = typename Upd::value_type;
  34.     using U = typename Upd::update_type;
  35.     using valid = ValidMonoid<Upd>;
  36.     static_assert(std::is_same_v<decltype(Upd::update(std::declval<T>(), std::declval<U>(),
  37.                                                       std::declval<size_t>(), std::declval<size_t>())), T>);
  38.     using Upd::update;
  39.     using Upd::compose;
  40.     using Upd::identity;
  41. };
  42.  
  43. template<typename T>
  44. struct Updater<Monoid<T>> : Monoid<T> {
  45.     using M = Monoid<T>;
  46.     using valid = ValidMonoid<M>;
  47.     using value_type = typename M::value_type;
  48.     using update_type = typename M::value_type;
  49.  
  50.     static value_type update(const value_type& a, const update_type& b, size_t l, size_t r) { return M::compose(a, b); }
  51. };
  52.  
  53. template<typename T>
  54. struct STOp {
  55.     using composer = ValidMonoid<Monoid<T>>;
  56.     using updater = ValidUpdater<Updater<T>>;
  57. };
  58.  
  59. template<typename Op>
  60. struct ValidSTOp : Op {
  61.     using compose_valid = ValidMonoid<typename Op::composer>;
  62.     using updater_valid = ValidUpdater<typename Op::updater>;
  63.     static_assert(std::is_same_v<typename Op::composer::value_type, typename Op::updater::value_type>);
  64.     using typename Op::composer;
  65.     using typename Op::updater;
  66. };
  67.  
  68. template<typename Operation>
  69. class SegmentTreeFromAbove {
  70. public:
  71.     using Op = ValidSTOp<STOp<Operation>>;
  72.     using Cm = ValidMonoid<typename Op::composer>;
  73.     using Up = ValidUpdater<typename Op::updater>;
  74.     using T = typename Cm::value_type;
  75.     using U = typename Up::update_type;
  76.  
  77.     explicit SegmentTreeFromAbove(size_t n) : n(n) {
  78.         data.resize(4 * n, Cm::identity());
  79.         updates.resize(data.size(), Up::identity());
  80.     }
  81.  
  82.     explicit SegmentTreeFromAbove(int n) : SegmentTreeFromAbove(static_cast<size_t>(n)) {}
  83.  
  84.     template<typename Cont>
  85.     explicit SegmentTreeFromAbove(const Cont& cont) : SegmentTreeFromAbove(cont.size()) {
  86.         build(cont);
  87.     }
  88.  
  89.     T compute(size_t l, size_t r) {
  90.         return compute(1, 0, n, l, r);
  91.     }
  92.  
  93.     void applyToLeaf(size_t i, std::function<T(const T&, size_t, size_t)> f) {
  94.         applyToLeaf(1, 0, n, i, std::move(f));
  95.     }
  96.  
  97.     void applyToLeaf(size_t i, std::function<T(const T&)> f) {
  98.         applyToLeaf(i, [f](const T& t, size_t l, size_t r){ return f(t); });
  99.     }
  100.  
  101.     void set(size_t i, T x) {
  102.         applyToLeaf(i, [&x](const T& y, size_t l, size_t r) { return x; });
  103.     }
  104.  
  105.     void update(size_t i, U upd) {
  106.         applyToLeaf(i, [this, &upd](const T& x, size_t l, size_t r) { return Up::update(x, upd, l, r); });
  107.     }
  108.  
  109.     void update(size_t l, size_t r, U upd) {
  110.         update(1, 0, n, l, r, upd);
  111.     }
  112.  
  113. private:
  114.  
  115.     T compute(size_t v, size_t vl, size_t vr, size_t l, size_t r) {
  116.         if (disjoint(vl, vr, l, r)) return Cm::identity();
  117.         if (embedded(vl, vr, l, r)) return data[v];
  118.         size_t vm = mid(vl, vr);
  119.         return Up::update(
  120.                 Cm::compose(
  121.                 compute(left(v), vl, vm, l, r),
  122.                 compute(right(v), vm, vr, l, r)
  123.                 ),
  124.                 updates[v], vl, vr
  125.         );
  126.     }
  127.  
  128.     void update(size_t v, size_t vl, size_t vr, size_t l, size_t r, U upd) {
  129.         recompute(v, vl, vr);
  130.         if (disjoint(vl, vr, l, r)) return;
  131.         if (embedded(vl, vr, l, r)) {
  132.             updates[v] = Up::compose(updates[v], upd);
  133.             recompute(v, vl, vr);
  134.             return;
  135.         }
  136.         size_t vm = mid(vl, vr);
  137.         push(v);
  138.         update(left(v), vl, vm, l, r, upd);
  139.         update(right(v), vm, vr, l, r, upd);
  140.         recompute(v, vl, vr);
  141.     }
  142.  
  143.     void push(size_t v) {
  144.         updates[left(v)] = Up::compose(updates[left(v)], updates[v]);
  145.         updates[right(v)] = Up::compose(updates[right(v)], updates[v]);
  146.         updates[v] = Up::identity();
  147.     }
  148.  
  149.     void applyToLeaf(size_t v, size_t vl, size_t vr, size_t i, std::function<T(const T&, size_t, size_t)> f) {
  150.         if (vl == i && vr == i + 1) {
  151.             data[v] = Up::update(f(data[v], vl, vr), updates[i], vl, vr);
  152.             return;
  153.         }
  154.         size_t vm = mid(vl, vr);
  155.         if (i < vm) applyToLeaf(left(v), vl, vm, i, f);
  156.         else applyToLeaf(right(v), vm, vr, i, f);
  157.         recompute(v, vl, vr);
  158.     }
  159.  
  160.     template<typename Cont>
  161.     void build(const Cont& cnt) {
  162.         size_t i = 0;
  163.         for (auto x : cnt) {
  164.             set(i++, x);
  165.         }
  166.     }
  167.  
  168.     bool disjoint(size_t vl, size_t vr, size_t l, size_t r) { return vr <= l || r <= vl; }
  169.  
  170.     bool embedded(size_t vl, size_t vr, size_t l, size_t r) { return l <= vl && vr <= r; }
  171.  
  172.     size_t mid(size_t vl, size_t vr) { return (vl + vr + 1) / 2; }
  173.  
  174.     size_t left(size_t i) { return 2 * i; }
  175.  
  176.     size_t right(size_t i) { return 2 * i + 1; }
  177.  
  178.     void recompute(size_t i, size_t vl, size_t vr) {
  179.         if(vl + 1 == vr) {
  180.             data[i] = Up::update(data[i], updates[i], vl, vr);
  181.             updates[i] = Up::identity();
  182.         } else {
  183.             data[i] = Up::update(
  184.                     Cm::compose(data[left(i)], data[right(i)]),
  185.                     updates[i], vl, vr
  186.             );
  187.         }
  188.     }
  189.  
  190.     size_t n;
  191.     std::vector<T> data;
  192.     std::vector<U> updates;
  193. };
  194.  
  195.  
  196. template<typename T, T id = 0>
  197. struct Sum {
  198. };
  199.  
  200. template<typename T, T id>
  201. struct Monoid<Sum<T, id>> {
  202.     using value_type = T;
  203.  
  204.     static T identity() { return id; };
  205.  
  206.     static T compose(T a, T b) {
  207.         return a + b;
  208.     }
  209. };
  210.  
  211. template<typename T, T id>
  212. struct Updater<Sum<T, id>> : Monoid<Sum<T, id>> {
  213.     using update_type = T;
  214.  
  215.     static T update(T x, T up, size_t l, size_t r) {
  216.         return x + up * (r - l);
  217.     }
  218. };
  219.  
  220. template<typename T, T id = std::numeric_limits<T>::max()>
  221. struct Min {
  222. };
  223.  
  224. template<typename T, T id>
  225. struct Monoid<Min<T, id>> {
  226.     using value_type = T;
  227.  
  228.     static T identity() { return id; };
  229.  
  230.     static T compose(T a, T b) {
  231.         return min(a, b);
  232.     }
  233. };
  234.  
  235. template<typename T, const T* id = &std::numeric_limits<T>::min()>
  236. struct Max {
  237. };
  238.  
  239. template<typename T, const T* id>
  240. struct Monoid<Max<T, id>> {
  241.     using value_type = T;
  242.  
  243.     static T identity() { return *id; };
  244.  
  245.     static T compose(T a, T b) {
  246.         return max(a, b);
  247.     }
  248. };
  249.  
  250. //template<typename T, T* id>
  251. //struct Updater<Max<T, id>> : Monoid<Max<T, id>> {
  252. //
  253. //    using value_type = T;
  254. //    using update_type = T;
  255. //
  256. //    static value_type update(value_type a, update_type b, size_t l, size_t r) {
  257. //        return max(a, b);
  258. //    }
  259. //
  260. //};
  261.  
  262. template<typename T, T id = 0>
  263. struct PureSum {
  264. };
  265.  
  266. template<typename T, T id>
  267. struct Updater<PureSum<T, id>> : Monoid<Sum<T, id>> {
  268.     using update_type = T;
  269.  
  270.     static T update(const T& a, const T& b, size_t l, size_t r) { return a + b; }
  271.  
  272. };
  273.  
  274. struct CountSegments {};
  275.  
  276. struct CSNode {
  277.     enum class Color {
  278.         BLACK,
  279.         WHITE
  280.     };
  281.  
  282.     Color beg, end;
  283.     size_t black_cnt, len;
  284. };
  285.  
  286. std::string to_str(CSNode::Color c) {
  287.     return c == CSNode::Color::BLACK ? "B" : "W";
  288. }
  289. bool debug = false;
  290. template<>
  291. struct Monoid<CountSegments> {
  292.     using value_type = CSNode;
  293.     using Color = CSNode::Color;
  294.     static value_type identity() {
  295.         return {Color::WHITE, Color::WHITE, 0, 0};
  296.     }
  297.  
  298.     static value_type compose(value_type a, value_type b) {
  299.         CSNode res = {a.beg, b.end, a.black_cnt + b.black_cnt - (a.end == Color::BLACK && b.beg == Color::BLACK), a.len + b.len};
  300.         if(debug)
  301.         std::cerr << "Composing "
  302.                   << to_str(a.beg) << "[" << a.black_cnt << "]" << to_str(a.end)
  303.                   << " with "
  304.                   << to_str(b.beg) << "[" << b.black_cnt << "]" << to_str(b.end)
  305.                   << " result "
  306.                   << to_str(res.beg) << "[" << res.black_cnt << "]" << to_str(res.end)
  307.                   << std::endl;
  308.         return res;
  309.     }
  310. };
  311.  
  312.  
  313. template<>
  314. struct Updater<CountSegments> {
  315.  
  316.     using value_type = CSNode;
  317.     using update_type = std::optional<CSNode::Color>;
  318.  
  319.     static update_type identity() {
  320.         return std::optional<CSNode::Color>();
  321.     }
  322.  
  323.     static update_type compose(update_type a, update_type b) {
  324.         if(!b.has_value()) return a;
  325.         return b;
  326.     }
  327.  
  328.     static value_type update(value_type a, update_type u, size_t l, size_t r) {
  329.         if(!u.has_value()) return a;
  330.         CSNode res = {u.value(), u.value(), u.value() == CSNode::Color::BLACK, u.value() == CSNode::Color::BLACK ? (r - l) : 0};
  331.         if(debug)
  332.             std::cerr << "Updating "
  333.                       << to_str(a.beg) << "[" << a.black_cnt << "]" << to_str(a.end)
  334.                       << " to "
  335.                       << to_str(res.beg) << "[" << res.black_cnt << "]" << to_str(res.end)
  336.                       << std::endl;
  337.         return res;
  338.     }
  339. };
  340.  
  341. struct RectUpdater;
  342.  
  343. template<>
  344. struct Updater<RectUpdater> : Monoid<Sum<int>> {
  345.  
  346.     using value_type = pair<int, int>;
  347.     using update_type = int;
  348.  
  349.     static value_type update(value_type rect, update_type k, size_t l, size_t r) {
  350.         return {rect.first + k, rect.second};
  351.     }
  352. };
  353. constexpr pair<int, int> identity{0, -1};
  354.  
  355. template<typename Op, typename Up>
  356. struct ComplexOp {
  357. };
  358.  
  359. template<typename Op, typename Up>
  360. struct STOp<ComplexOp<Op, Up>> {
  361.     using composer = ValidMonoid<typename STOp<Op>::composer>;
  362.     using updater = ValidUpdater<typename STOp<Up>::updater>;
  363. };
  364.  
  365. int main() {
  366.     int n = readInt();
  367.     std::vector<std::tuple<int, int, int, int, int, int>> events;
  368.     for (int i = 0; i < n; ++i) {
  369.         int x1 = readInt(), y1 = readInt(), x2 = readInt(), y2 = readInt(), k = readInt();
  370.         events.emplace_back(x1, 0, y1, y2, k, i);
  371.         events.emplace_back(x2, 2, y1, y2, k, i);
  372.     }
  373.     int K = 2e5;
  374.     sort(events.begin(), events.end());
  375.     std::vector<pair<int, int>> rects(n);
  376.     int N = 2 * K + 2;
  377.     SegmentTreeFromAbove<Max<pair<int, int>, &identity>> tree(N);
  378.     for(auto [x, type, y1, y2, k, i] : events) {
  379.         y1 += K;
  380.         y2 += K + 1;
  381.         switch(type) {
  382.             case 0: {
  383.                 rects[i] = tree.compute(y2, N);
  384.                 rects[i].first += k;
  385.                 break;
  386.             }
  387.             case 2: {
  388.                 tree.update(y1, y2, pair<int, int>{rects[i].first, i});
  389.                 break;
  390.             }
  391.         }
  392.     }
  393.     int maxI = 0;
  394.     for (int i = 0; i < n; ++i) {
  395.         if(rects[i].first > rects[maxI].first) {
  396.             maxI = i;
  397.         }
  398.     }
  399.     std::vector<int> chain;
  400.     for(int i = maxI; i != -1; i = rects[i].second) {
  401.         chain.push_back(i);
  402.     }
  403.     std::reverse(chain.begin(), chain.end());
  404.     writeInt(rects[maxI].first, '\n');
  405.     for(int i : chain) {
  406.         writeInt(i + 1, ' ');
  407.     }
  408.     writeChar('\n');
  409. }
  410.  
  411. // x1 y1 x2 y2
  412. // a1 b1 a2 b2
  413. // a1 > x2 && b2 < y1
  414.  
  415. //WWWWWWWWWWW
  416. //WWWWWWWWWWW
  417. //WWBBWWWWWWW
  418. //WWBBBBWWWWW
  419. //WWBBBBWWWWW
  420. //WWBBBBWBBWW
  421. //WWBWBBWBBWW
  422. //WWWWWWWWWWW
  423.  
  424. //int main() {
  425. //    int n = readInt();
  426. //    int N = 1000002;
  427. //    SegmentTreeFromAbove<CountSegments> tree(N);
  428. //    for (int i = 0; i < n; ++i) {
  429. //        debug = i == 5;
  430. //        int color = readChar(), x = readInt(), l = readInt();
  431. //        x += 500000;
  432. //        tree.update(x, x+l, color == 'W' ? CSNode::Color::WHITE : CSNode::Color::BLACK);
  433. //        CSNode ans = tree.compute(0, N);
  434. //        writeInt(ans.black_cnt, ' ');
  435. //        writeInt(ans.len, '\n');
  436. //    }
  437. //}
  438.  
  439. //int main() {
  440. //    int n = readInt(), q = readInt();
  441. //    vector<int> v;
  442. //    v.reserve(n);
  443. //    for (int i = 0; i < n; ++i) {
  444. //        v.push_back(readInt());
  445. //    }
  446. //    SegmentTreeFromAbove<ComplexOp<Max<ll, static_cast<ll>(-1e15)>, PureSum<ll>>> tree(v);
  447. //    for (int i = 0; i < q; ++i) {
  448. //        int cmd = readChar();
  449. //        readChar();
  450. //        readChar();
  451. //        int l = readInt() - 1, r = readInt();
  452. //        if (cmd == 'm') {
  453. //            writeInt(tree.compute(l, r), '\n');
  454. //        } else {
  455. //            int x = readInt();
  456. //            tree.update(l, r, x);
  457. //        }
  458. //    }
  459. //    return 0;
  460. //}
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!