API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Mar 18th, 2024
303
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 29.66 KB | None | 0 0
raw download clone embed print report
  1. #pragma GCC optimize("Ofast")
  2. // #pragma GCC target("avx,avx2,fma")
  3.  
  4. #include "bits/stdc++.h"
  5.  
  6. //#define NDEBUG
  7. #define F first
  8. #define S second
  9. #define vec vector
  10. #define pb push_back
  11. #define pll pair<ll, ll>
  12. #define pdd pair<ld, ld>
  13. #define pii pair<int, int>
  14. #define all(m) m.begin(), m.end()
  15. #define rall(m) m.rbegin(), m.rend()
  16. #define uid uniform_int_distribution
  17. #define timeStamp() std::chrono::steady_clock::now()
  18. #define unify(m) sort(all(m)), m.erase(unique(all(m)), m.end());
  19. #define duration_micro(a) chrono::duration_cast<chrono::microseconds>(a).count()
  20. #define duration_milli(a) chrono::duration_cast<chrono::milliseconds>(a).count()
  21. #define fast cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), cout.sync_with_stdio(0);
  22. using namespace std;
  23. using str = string;
  24. using ll = long long;
  25. using ld = long double;
  26. using uint = unsigned int;
  27. using ull = unsigned long long;
  28. mt19937 rnd(timeStamp().time_since_epoch().count());
  29. mt19937_64 rndll(timeStamp().time_since_epoch().count());
  30. template<typename T, typename U> bool chmin(T& a, const U& b) {return (T)b < a ? a = b, 1 : 0;}
  31. template<typename T, typename U> bool chmax(T& a, const U& b) {return (T)b > a ? a = b, 1 : 0;}
  32. struct custom_hash {static uint64_t xs(uint64_t x) {x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);} template<typename T> size_t operator()(T x) const {static const uint64_t C = timeStamp().time_since_epoch().count(); return xs(hash<T> {}(x) + C);}};
  33. template<typename K> using uset = unordered_set<K, custom_hash>;
  34. template<typename K, typename V> using umap = unordered_map<K, V, custom_hash>;
  35. template<typename T1, typename T2> ostream& operator<<(ostream& out, const pair<T1, T2>& x) {return out << x.F << ' ' << x.S;}
  36. template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& x) {return in >> x.F >> x.S;}
  37. template<typename T, size_t N> istream& operator>>(istream& in, array<T, N>& a) {for (auto &x : a) in >> x; return in;}
  38. template<typename T, size_t N> ostream& operator<<(ostream& out, const array<T, N>& a) {for (size_t i = 0; i < a.size(); ++i) {out << a[i]; if (i + 1 < a.size()) out << ' ';} return out;}
  39. template<typename T> istream& operator>>(istream& in, vector<T>& a) {for (auto& x : a) in >> x; return in;}
  40. template<typename T> ostream& operator<<(ostream& out, const vector<T>& a) {for (size_t i = 0; i < a.size(); ++i) {out << a[i]; if (i + 1 < a.size()) out << ' ';} return out;}
  41.  
  42. template<typename I> auto array_cnt(I f, I l) {umap<typename iterator_traits<I>::value_type, int> mp; while (f != l) ++mp[*f], ++f; return mp;}
  43. template<typename I> auto subset_sum(I f, I l) {int a = l - f; vec<typename iterator_traits<I>::value_type> o(1 << a); for (int q = 1; q < (1 << a); ++q) {const int i = __builtin_ctz(q); o[q] = *(f + i) + o[q ^ (1 << i)];} return o;}
  44. template<typename I> vec<pii> get_segs_of_eq_elems(I first, I last, function<bool(const typename iterator_traits<I>::value_type&, const typename iterator_traits<I>::value_type&)> cmp = [](const auto& l, const auto& r) {return l == r;}) {using T = typename iterator_traits<I>::value_type; vec<pii> ans; if (first == last) return ans; int l = 0, r = 1; T prev = *first; for (auto cit = next(first); cit != last; ++cit, ++r) {if (!cmp(*cit, prev)) {ans.emplace_back(l, r - 1); l = r;} prev = *cit;} ans.emplace_back(l, r - 1); return ans;}
  45. template<typename I> int LCP(I f1, I l1, I f2, I l2) {for (int o = 0; ; ++f1, ++f2, ++o) if (f1 == l1 || f2 == l2 || *f1 != *f2) return o; return -1;}
  46. template<typename I> int min_period(I f, I l) {int a = l - f; vec<int> m(a); for (int q = 1; q < a; ++q) {for (int w = m[q - 1]; w && !m[q]; w = m[w - 1]) {if (*(f + q) == *(f + w)) m[q] = w + 1;} m[q] += !m[q] && *(f + q) == *f;} int p = a - m.back(); return a % p ? a : p;}
  47. template<typename I> bool is_palindrome(I f, I l) {for (--l; f < l; ++f, --l) if (*f != *l) return 0; return 1;}
  48. str from_base_10_to_base_b(ll x, ll b) {str t; if (x == 0) t = "0"; for (; x; x /= b) t += (char)('0' + x % b); reverse(all(t)); return t;}
  49. #define vi vec<int>
  50. #define vl vec<ll>
  51. #define vvi vec<vec<int>>
  52. #define vvvi vec<vec<vec<int>>>
  53. #define vvl vec<vec<ll>>
  54. #define vpi vec<pii>
  55. #define vpl vec<pll>
  56. #define vs vec<str>
  57. #define vvs vec<vec<str>>
  58. const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1};
  59. const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
  60. template<typename T> int sum_of_digits(T val) {int o = 0; for (; val; val /= 10) o += val % 10; return o;}
  61. template<typename T> struct static_sum_query {vec<T> m; static_sum_query() = default; template<typename I>static_sum_query(I f, I l) {m.resize(l - f + 1); for (auto it = m.begin() + 1; f != l; ++f, ++it) {*it = *(it - 1) + *f;}} template<typename T_arr> static_sum_query(T_arr& m) {(*this) = static_sum_query(all(m));} inline T query(const int l, const int r) const {return m[r + 1] - m[l];}};
  62. template<typename T> vec<pair<T, int>> zip_with_positions(vec<T> &m) {int a = m.size(); vec<pair<T, int>> ans(a); for (int q = 0; q < a; ++q) ans[q] = {m[q], q}; return ans;}
  63. template<typename T> str join(vec<T> &m, str c) {str o; if constexpr(is_same<str, T>::value) {for (const T &s : m) o += s + c;} else {for (const T &s : m) o += to_string(s) + c;} if (o.size()) o.erase(o.end() - c.size(), o.end()); return o;}
  64. vec<pii> get_reflection_points_in_rect(int a, int b, int x, int y) {assert(0 <= x && x < a); assert(0 <= y && y < b); vec<pii> res = {{x, y}}; if (x != a - x - 1) res.pb({a - x - 1, y}); if (y != a - y - 1) res.pb({x, a - y - 1}); if (x != a - x - 1 && y != a - y - 1) res.pb({a - x - 1, a - y - 1}); return res;}
  65. vec<pii> get_rotation_points_in_square(int a, int x, int y) {assert(0 <= x && x < a); assert(0 <= y && y < a); vec<pii> res = {{x, y}}; if (a % 2 == 1 && x == a / 2 && y == a / 2) return res; res.pb({a - y - 1, x}); res.pb({a - x - 1, a - y - 1}); res.pb({y, a - x - 1}); return res;}
  66. template<typename T> vec<vec<int>> get_cycles_of_perm(vec<T> &m, int permutation_indexation) {int a = m.size(); vec<vec<int>> ans; vec<bool> us(a); for (int q = 0; q < a; ++q) {if (us[q]) continue; vec<int> tyt; for (int w = q; !us[w]; w = m[w] - permutation_indexation) {tyt.pb(w); us[w] = 1;} ans.pb(tyt);} return ans;}
  67. int find_closing_bracket(str &s, int i) {char op = s[i], cl = op == '(' ? ')' : op == '{' ? '}' : op == '[' ? ']' : op == '<' ? '>' : '@'; assert(cl != '@'); int dep = 1; for (int q = i + 1; q < s.size(); ++q) {dep += s[q] == op ? 1 : s[q] == cl ? -1 : 0; if (dep == 0) return q;} return -1;}
  68. template<typename T> vec<pair<T, T>> vv_to_vp(vec<vec<T>> &m) {int a = m.size(); vec<pair<T, T>> ans(a); for (int q = 0; q < a; ++q) ans[q] = {m[q][0], m[q][1]}; return ans;}
  69. template<const int k, typename T> vec<array<T, k>> vv_to_varr(vec<vec<T>> &m) {int a = m.size(); vec<array<T, k>> ans(a); for (int q = 0; q < a; ++q) for (int w = 0; w < k; ++w) ans[q][w] = m[q][w]; return ans;}
  70. str from_base_10_to_base_b(str x, ll b) {return from_base_10_to_base_b(stoll(x), b);}
  71. ll from_base_b_to_base_10(str x, ll b) {ll o = 0, pw = 1; for (int q = x.size() - 1; q >= 0; --q, pw *= b) o += (x[q] - '0') * pw; return o;}
  72. str from_base_a_to_base_b(str x, ll a, ll b) {ll x10 = from_base_b_to_base_10(x, a); return from_base_10_to_base_b(x10, b);}
  73. template<typename T> T binpow(T x, T k) {if (k < 0) return 0; T o = 1; for (; k; k >>= 1) {if (k & 1) o = o * x; x = x * x;} return o;}
  74. template<typename T> T ar_prog_sum_fcl(T first, T cnt, T last) {return (first + last) * cnt / 2;}
  75. template<typename T> T ar_prog_sum_fdc(T first, T diff, T cnt) {return (first * 2 + diff * (cnt - 1)) * cnt / 2;}
  76. template<typename T> T ar_prog_sum_fdl(T first, T diff, T last) {return (first + last) * ((last - first) / diff + 1) / 2;}
  77. template<typename T> T geom_prog_sum_fdl(T first, T diff, T last) {return (last * diff - first) / (diff - 1);}
  78. template<typename T> T geom_prog_sum_fdc(T first, T diff, T cnt) {return (first * binpow(diff, cnt) - first) / (diff - 1);}
  79. template<typename T> vec<vec<T>> transpose_matrix(vec<vec<T>> &m) {int a = m.size(), b = a ? m[0].size() : 0; vec<vec<T>> ans(b, vec<T>(a)); for (int q = 0; q < a; ++q) {for (int w = 0; w < b; ++w) {ans[w][q] = m[q][w];}} return ans;}
  80. template<typename T> vec<vec<T>> rotate_matrix_cw(vec<vec<T>> &m) {int a = m.size(), b = a ? m[0].size() : 0; vec<vec<T>> ans(b, vec<T>(a)); for (int w = 0; w < b; ++w) for (int q = 0; q < a; ++q) ans[w][q] = m[a - 1 - q][w]; return ans;}
  81. complex<ll> str_to_cmpl_ll(str t) {int ps = t.find('+'), sgn = 1; if (ps == string::npos) {ps = t.find('-'); sgn = -1; assert(ps != string::npos);} str t1 = t.substr(0, ps), t2 = t.substr(ps + 1); assert(t2.back() == 'i'); t2.pop_back(); return {stoll(t1), stoll(t2) * sgn};}
  82. int time_to_minutes(int h, int m) {return h * 60 + m;}
  83. int time_to_minutes(str s) {int ps = s.find(':'); assert(ps != string::npos); return time_to_minutes(stoi(s.substr(0, ps)), stoi(s.substr(ps + 1)));}
  84. str minutes_to_time(int m, bool h0 = true, bool m0 = true) {int h = m / 60; m %= 60; str o; if (h0) o += (h < 10 ? "0" : ""); o += to_string(h); o += ':'; if (m0) o += (m < 10 ? "0" : ""); o += to_string(m); return o;}
  85. bool is_vowel_lowercase(char c) {return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';}
  86. bool is_consonant_lowercase(char c) {return !is_vowel_lowercase(c);}
  87. ull leq_pow2ll(const ull x) {return 1ull << __lg(x);}
  88. ull geq_pow2ll(const ull x) {return x & (x - 1) ? 2ull << __lg(x) : x;}
  89. ll sqd(const pll p1, const pll p2) {return (p1.F - p2.F) * (p1.F - p2.F) + (p1.S - p2.S) * (p1.S - p2.S);}
  90. ll sqd(const ll x1, const ll y1, const ll x2, const ll y2) {return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);}
  91. template<typename T> int sign(T x) {return x < 0 ? -1 : x > 0 ? 1 : 0;}
  92. template<typename I> bool is_subsequence(I f_pattern, I l_pattern, I f_text, I l_text) {for (; f_text != l_text && f_pattern != l_pattern; ++f_text) if (*f_text == *f_pattern) ++f_pattern; return f_pattern == l_pattern;}
  93. vec<ll> get_divisors(ll x) {vec<ll> ans1, ans2; for (ll q = 1; q * q <= x; ++q) {if (x % q == 0) {ans1.pb(q); ans2.pb(x / q);}} if (ans1.back() == ans2.back()) ans1.pop_back(); reverse(all(ans2)); for (ll i : ans2) ans1.pb(i); return ans1;}
  94. bool is_prime(ll c) {if (c < 2) return 0; if (c == 2 || c == 3) return 1; if (c % 2 == 0 || c % 3 == 0) return 0; const ll gr = sqrtl(c) + 1; for (ll q = 6; q <= gr; q += 6) {if (c % (q - 1) == 0) return 0; if (c % (q + 1) == 0) return 0;} return 1;}
  95. vec<str> split(str &s, char c, bool ignore_empty = false) {vec<str> o; str u; for (int q = 0; q < s.size(); q++) {if (s[q] == c) {if (!u.empty() || !ignore_empty) o.pb(u); u.clear();} else u += s[q];} if (!u.empty() || !ignore_empty) o.pb(u); return o;}
  96. int replace(str &s, str from, str to) {str t = from; t.pb(0); t += s; int a = t.size(); vec<int> m(a); for (int q = 1; q < a; ++q) {for (int w = m[q - 1]; w && !m[q]; w = m[w - 1]) {if (t[q] == t[w]) m[q] = w + 1;} m[q] += !m[q] && t[q] == t[0];} int szf = from.size(), lst = szf; for (int q = szf; q < t.size(); ++q) {if (m[q] == szf && q - lst >= szf) {m[q - szf + 1] = -1; lst = q;}} str ans; int o = 0; for (int q = szf + 1; q < t.size(); ++q) {if (m[q] != -1) ans += t[q]; else ans += to, q += szf - 1, ++o;} s = ans; return o;}
  97. template<typename T> T mul_threshold(T a, T b, T threshold) {if (!a || !b || !threshold) return 0; assert(a > 0 && b > 0); T max_b = threshold / a; return b <= max_b ? a * b : threshold;}
  98. template<typename T> T count_set_bits_pref(T n, int b) {assert(0 <= n); T pw = (T)(1) << b; if (pw > n) return 0; T period = pw * 2; T full = (n + 1) / period; T rem = (n + 1) & (period - 1); return full * pw + (rem < pw ? 0 : rem - pw);}
  99. template<typename T> T count_set_bits_seg(T l, T r, int b) {assert(0 <= l && l <= r); return count_set_bits_pref(r, b) - (l ? count_set_bits_pref(l - 1, b) : 0);}
  100. template<typename I> vector<int> get_substring_occurrences(I f_pattern, I l_pattern, I f_text, I l_text) {const size_t n = std::distance(f_pattern, l_pattern); const size_t m = std::distance(f_text, l_text); assert(n); auto cmp = [&](size_t i, size_t j) {if (i == n || j == n) return i == j; return (i < n ? * (f_pattern + i) : * (f_text + i - n - 1)) == (j < n ? * (f_pattern + j) : * (f_text + j - n - 1));}; vector<int> pf(n), res; for (size_t i = 1, ppf = 0; i < n + 1 + m; ++i) {size_t p = 0; for (size_t j = ppf; j && !p; j = pf[j - 1]) {if (cmp(i, j)) p = j + 1;} p += !p && cmp(i, 0); ppf = p; if (i < n) pf[i] = p; if (p == n) res.push_back(i - n * 2);} return res;}
  101. template<typename T> T integral_tersearch_argmin(auto f, T l, T r) {static_assert(is_integral_v<decltype(l)>); using U = decltype(f(l)); const ld FI = 1.6180339887498948482045868343656381177203; T p1 = l + (r - l) / (FI + 1), p2 = r - (r - l) / (FI + 1); U v1 = f(p1), v2 = f(p2); while (r - l > 7) {if (v1 < v2) {r = p2; p2 = p1, v2 = v1; p1 = l + (r - l) / (FI + 1), v1 = f(p1);} else {l = p1; p1 = p2, v1 = v2; p2 = r - (r - l) / (FI + 1), v2 = f(p2);}} T best_arg = l; U best_val = f(l), prv = best_val; while (++l <= r) {U tyt = l == p1 ? v1 : l == p2 ? v2 : f(l); if (tyt > prv) break; if (chmin(best_val, tyt)) best_arg = l; prv = tyt;} return best_arg;};
  102. template<typename T> T integral_binary_search_last_when_true(auto f, T l, T r) {static_assert(is_same<decltype(l), decltype(r)>::value); while (l + 1 < r) {T md = l + (r - l) / 2; if (f(md))l = md; else r = md;} return l;};
  103. template<typename T> T integral_binary_search_last_when_true(auto f, T l) {T d = 1; while (f(l + d)) d *= 2; d /= 2; for (T u = d; u; u /= 2) if (f(l + d + u)) d += u; return l + d;};
  104.  
  105. template<typename K>
  106. class treap {
  107.     struct Node {
  108.         Node* l = 0;
  109.         Node* r = 0;
  110.         int y;
  111.         size_t sz;
  112.  
  113.         K key;
  114.         K smk;
  115.         K ps_add = 0;
  116.  
  117.         Node(K k): y(rnd()), sz(1) {
  118.             key = k;
  119.             smk = k;
  120.         }
  121.     };
  122.     Node* root = 0;
  123.  
  124.     K last_erased_key;
  125.  
  126.     K gsmk(Node* n) const {return n ? n->smk : 0;}
  127.  
  128.     size_t gsz(Node* n) const {return n ? n->sz : 0;}
  129.  
  130.     //Write, if need
  131.     void apply_push(Node* n, K x) {
  132.         if (!n) return;
  133.         n->smk += gsz(n) * x;
  134.         n->ps_add += x;
  135.         n->key += x;
  136.     }
  137.     void push(Node* n) {
  138.         if (!n) return;
  139.         if (n->ps_add) {
  140.             apply_push(n->l, n->ps_add);
  141.             apply_push(n->r, n->ps_add);
  142.             n->ps_add = 0;
  143.         }
  144.     }
  145.  
  146.     void upd(Node* n) {
  147.         if (!n) return;
  148.         n->smk = gsmk(n->l) + n->key + gsmk(n->r);
  149.  
  150.         n->sz = gsz(n->l) + 1 + gsz(n->r);
  151.     }
  152.  
  153.     Node* merge(Node* l, Node* r) {
  154.         if (!l || !r) return l ? l : r;
  155.         if (l->y > r->y) {
  156.             push(l);
  157.             l->r = merge(l->r, r); upd(l);
  158.             return l;
  159.         }
  160.         push(r);
  161.         r->l = merge(l, r->l); upd(r);
  162.         return r;
  163.     }
  164.  
  165.     array<Node*, 2> split_size(Node* n, size_t k) {
  166.         if (!n) return {0, 0};
  167.         push(n);
  168.         if (k <= gsz(n->l)) {
  169.             array<Node*, 2> p = split_size(n->l, k);
  170.             n->l = p[1]; upd(n);
  171.             p[1] = n;
  172.             return p;
  173.         }
  174.         array<Node*, 2> p = split_size(n->r, k - gsz(n->l) - 1);
  175.         n->r = p[0]; upd(n);
  176.         p[0] = n;
  177.         return p;
  178.     }
  179.  
  180.     array<Node*, 2> split_key(Node* n, K key) {
  181.         if (!n) return {0, 0};
  182.         push(n);
  183.         if (key < n->key) {
  184.             array<Node*, 2> p = split_key(n->l, key);
  185.             n->l = p[1]; upd(n);
  186.             p[1] = n;
  187.             return p;
  188.         }
  189.         array<Node*, 2> p = split_key(n->r, key);
  190.         n->r = p[0]; upd(n);
  191.         p[0] = n;
  192.         return p;
  193.     }
  194.  
  195.     template<typename I>
  196.     Node* build(I f_key, I l_key) {
  197.         if (f_key >= l_key) return 0;
  198.         I md = f_key + (l_key - f_key) / 2;
  199.         Node* n = new Node(*md);
  200.         n->l = build(f_key, md);
  201.         n->r = build(md + 1, l_key);
  202.         upd(n);
  203.         return n;
  204.     }
  205.  
  206.     void update_key_at_pos(Node* n, size_t pos, K new_key) {
  207.         push(n);
  208.         if (pos == gsz(n->l)) {n->key = new_key; upd(n); return;}
  209.         if (pos < gsz(n->l)) update_key_at_pos(n->l, pos, new_key);
  210.         else update_key_at_pos(n->r, pos - gsz(n->l) - 1, new_key);
  211.         upd(n);
  212.     }
  213.  
  214.     Node* insert_node(Node* n, Node* nw) {
  215.         push(n);
  216.         if (!n || nw->y > n->y) {
  217.             auto [lf, rg] = split_key(n, nw->key);
  218.             nw->l = lf;
  219.             nw->r = rg;
  220.             upd(nw);
  221.             return nw;
  222.         }
  223.         if (nw->key < n->key) n->l = insert_node(n->l, nw);
  224.         else n->r = insert_node(n->r, nw);
  225.         upd(n);
  226.         return n;
  227.     }
  228.  
  229.     Node* erase_pos(Node* n, size_t pos) {
  230.         push(n);
  231.         if (gsz(n->l) == pos) {
  232.             last_erased_key = n->key;
  233.             Node* l = n->l, *r = n->r;
  234.             delete n;
  235.             return merge(l, r);
  236.         }
  237.         if (pos < gsz(n->l)) n->l = erase_pos(n->l, pos);
  238.         else n->r = erase_pos(n->r, pos - gsz(n->l) - 1);
  239.         upd(n);
  240.         return n;
  241.     }
  242.  
  243.     Node* erase_one_key_occurrence(Node* n, K key) {
  244.         if (!n) return 0;
  245.         push(n);
  246.         if (n->key == key) {
  247.             Node* l = n->l, *r = n->r;
  248.             delete n;
  249.             return merge(l, r);
  250.         }
  251.         if (key < n->key) n->l = erase_one_key_occurrence(n->l, key);
  252.         else n->r = erase_one_key_occurrence(n->r, key);
  253.         upd(n);
  254.         return n;
  255.     }
  256.  
  257.     Node* erase_all_key_occurrences(Node* n, K key) {
  258.         if (!n) return 0;
  259.         push(n);
  260.         if (n->key == key) {
  261.             Node* l = erase_all_key_occurrences(n->l, key), *r = erase_all_key_occurrences(n->r, key);
  262.             delete n;
  263.             return merge(l, r);
  264.         }
  265.         if (key < n->key) n->l = erase_all_key_occurrences(n->l, key);
  266.         else n->r = erase_all_key_occurrences(n->r, key);
  267.         upd(n);
  268.         return n;
  269.     }
  270.  
  271.     Node* erase_one_key(Node* n, K key) {
  272.         if (!n) return 0;
  273.         push(n);
  274.         if (n->key == key) {
  275.             Node* l = n->l, *r = n->r;
  276.             delete n;
  277.             return merge(l, r);
  278.         }
  279.         if (key < n->key) n->l = erase_one_key(n->l, key);
  280.         else n->r = erase_one_key(n->r, key);
  281.         upd(n);
  282.         return n;
  283.     }
  284.  
  285.     void get_keys_on_subsegment(Node* n, size_t l, size_t& len, vector<K>& res) {
  286.         if (!n || !len) return;
  287.         push(n);
  288.         if (l < gsz(n->l) && len) get_keys_on_subsegment(n->l, l, len, res);
  289.         if (l <= gsz(n->l) && len) res.push_back(n->key), --len;
  290.         if (len) get_keys_on_subsegment(n->r, l > gsz(n->l) ? l - gsz(n->l) - 1 : 0, len, res);
  291.     }
  292.  
  293.     K kth_elem(Node* n, size_t k) {
  294.         assert(0 <= k && k < gsz(n));
  295.         while (n) {
  296.             push(n);
  297.             const size_t szl = gsz(n->l);
  298.             if (k == szl) return n->key;
  299.             if (k < szl) n = n->l;
  300.             else k -= szl + 1, n = n->r;
  301.         }
  302.         assert(0);
  303.         return K();
  304.     }
  305.  
  306.     size_t pos_of_leftest_good(Node* n, auto has_good, auto is_good) {
  307.         size_t ans = 0;
  308.         while (n) {
  309.             push(n);
  310.             if (has_good(n->l)) n = n->l;
  311.             else if (is_good(n)) return ans + gsz(n->l);
  312.             else ans += gsz(n->l) + 1, n = n->r;
  313.         }
  314.         return ans;
  315.     }
  316.  
  317.     size_t pos_of_rightest_good(Node* n, auto has_good, auto is_good) {
  318.         size_t ans = 0;
  319.         while (n) {
  320.             push(n);
  321.             if (has_good(n->r)) ans += gsz(n->l) + 1, n = n->r;
  322.             else if (is_good(n)) return ans + gsz(n->l);
  323.             else n = n->l;
  324.         }
  325.         return ans;
  326.     }
  327.  
  328.     size_t pos_of_closest_from_right_good(Node* n, size_t pos, auto has_good, auto is_good) {
  329.         size_t szr = gsz(n);
  330.         if (pos >= szr || !has_good(n)) return szr;
  331.         size_t ans = 0, pos_to_ret = szr;
  332.         Node* u = 0;
  333.         while (n) {
  334.             push(n);
  335.             if (pos >= gsz(n->l)) {
  336.                 if (pos == gsz(n->l) && is_good(n)) return ans + gsz(n->l);
  337.                 ans += gsz(n->l) + 1;
  338.                 pos -= min(pos, gsz(n->l) + 1);
  339.                 n = n->r;
  340.             } else {
  341.                 if (is_good(n)) pos_to_ret = ans + gsz(n->l), u = 0;
  342.                 else if (has_good(n->r)) pos_to_ret = ans + gsz(n->l) + 1, u = n->r;
  343.                 n = n->l;
  344.             }
  345.         }
  346.         return pos_to_ret + (u ? pos_of_leftest_good(u, has_good, is_good) : 0);
  347.     }
  348.  
  349.     size_t pos_of_closest_from_left_good(Node* n, size_t pos, auto has_good, auto is_good) {
  350.         size_t szr = gsz(n);
  351.         if (!has_good(n)) return szr;
  352.         pos = min(pos, szr - 1);
  353.         pos = szr - 1 - pos;
  354.         size_t ans = 0, pos_to_ret = szr;
  355.         Node* u = 0;
  356.         while (n) {
  357.             push(n);
  358.             if (pos >= gsz(n->r)) {
  359.                 if (pos == gsz(n->r) && is_good(n)) return szr - 1 - (ans + gsz(n->r));
  360.                 ans += gsz(n->r) + 1;
  361.                 pos -= min(pos, gsz(n->r) + 1);
  362.                 n = n->l;
  363.             } else {
  364.                 if (is_good(n)) pos_to_ret = ans + gsz(n->r), u = 0;
  365.                 else if (has_good(n->l)) pos_to_ret = ans + gsz(n->r) + 1, u = n->l;
  366.                 n = n->r;
  367.             }
  368.         }
  369.         if (pos_to_ret == szr) return szr;
  370.         pos_to_ret = szr - 1 - pos_to_ret;
  371.         return pos_to_ret - (u ? gsz(u) - 1 - pos_of_rightest_good(u, has_good, is_good) : 0);
  372.     }
  373.  
  374.     size_t pos_of_leftest_min_key(Node* n) {
  375.         K mnk = gmnk(n);
  376.         return pos_of_leftest_good(n,
  377.         [&](Node * n) {return gmnk(n) == mnk;},
  378.         [&](Node * n) {return n->key == mnk;});
  379.     }
  380.  
  381.     size_t pos_of_rightest_min_key(Node* n) {
  382.         K mnk = gmnk(n);
  383.         return pos_of_rightest_good(n,
  384.         [&](Node * n) {return gmnk(n) == mnk;},
  385.         [&](Node * n) {return n->key == mnk;});
  386.     }
  387.  
  388.     size_t pos_of_leftest_key_leq(Node* n, K key) {
  389.         return pos_of_leftest_good(n,
  390.         [&](Node * n) {return gmnk(n) <= key;},
  391.         [&](Node * n) {return n->key <= key;});
  392.     }
  393.  
  394.     size_t pos_of_closest_from_left_key_leq(Node* n, size_t pos, K key) {
  395.         return pos_of_closest_from_left_good(n, pos,
  396.         [&](Node * n) {return gmnk(n) <= key;},
  397.         [&](Node * n) {return n->key <= key;});
  398.     }
  399.  
  400.     size_t pos_of_closest_from_right_key_leq(Node* n, size_t pos, K key) {
  401.         return pos_of_closest_from_right_good(n, pos,
  402.         [&](Node * n) {return gmnk(n) <= key;},
  403.         [&](Node * n) {return n->key <= key;});
  404.     }
  405.  
  406.     void print_keys(Node* n) {if (!n) return; push(n); print_keys(n->l); cout << n->key << ' '; print_keys(n->r);}
  407.  
  408.     void delete_subtree(Node* n) {if (!n) return; push(n); delete_subtree(n->l); delete_subtree(n->r); delete n;}
  409.  
  410.     void cyclic_shift_left(Node*& n, int shift) {if (shift < 0) cyclic_shift_right(-shift); else {if (gsz(n) == 0) return; if (shift >= gsz(n)) shift %= gsz(n); auto [lf, rg] = split_size(n, shift); n = merge(rg, lf);}}
  411.     void cyclic_shift_right(Node*& n, int shift) {if (shift < 0) cyclic_shift_left(-shift); else {if (gsz(n) == 0) return; if (shift >= gsz(n)) shift %= gsz(n); auto [lf, rg] = split_size(n, gsz(n) - shift); n = merge(rg, lf);}}
  412.  
  413. public:
  414.     treap() = default;
  415.     template<typename I> treap(I f_key, I l_key) {root = build(f_key, l_key);}
  416.     ~treap() {delete_subtree(root);}
  417.  
  418.     size_t size() const {return gsz(root);}
  419.     bool empty() const {return root == 0;}
  420.  
  421.     template<typename I> void insert_array_at_pos(size_t pos, I first, I last) {auto [lf, rg] = split_size(root, pos); root = merge(merge(lf, build(first, last)), rg);}
  422.     template<typename T> void insert_array_at_pos(size_t pos, initializer_list<T> il) {auto [lf, rg] = split_size(root, pos); root = merge(merge(lf, build(il.begin(), il.end())), rg);}
  423.     void insert_key_at_pos(size_t pos, K key) {auto [lf, rg] = split_size(root, pos); root = merge(merge(lf, new Node(key)), rg);}
  424.     void insert_key(K key) {root = insert_node(root, new Node(key));}
  425.  
  426.     void update_key_at_pos(size_t pos, K new_key) {update_key_at_pos(root, pos, new_key);}
  427.  
  428.     void erase_pos(size_t pos) {root = erase_pos(root, pos);}
  429.     void erase_one_key_occurrence(K key) {root = erase_one_key_occurrence(root, key);}
  430.     void erase_all_key_occurrences(K key) {root = erase_all_key_occurrences(root, key);}
  431.     void erase_seg(size_t l, size_t len) {auto [lf, tmp] = split_size(root, l); auto [md, rg] = split_size(tmp, len); root = merge(lf, rg);}
  432.  
  433.     K extract_pos(size_t pos) {erase_pos(pos); return last_erased_key;}
  434.  
  435.     K operator[](size_t pos) {return kth_elem(root, pos);}
  436.  
  437.     bool contains(K key) {Node* n = root; while (n) {push(n); if (key == n->key) return true; n = key < n->key ? n->l : n->r;} return false;}
  438.     size_t get_leftest_pos_of_key(K key) {Node* n = root; size_t pos = 0, o = size(); while (n) {push(n); if (key == n->key) o = min(o, pos + gsz(n->l)), n = n->l; else if (key < n->key) n = n->l; else pos += gsz(n->l) + 1, n = n->r;} assert(o < size() && "No such key"); return o;}
  439.  
  440.     size_t count_keys_leq(K key) {Node* n = root; size_t o = 0; while (n) {push(n); if (n->key <= key) o += gsz(n->l) + 1, n = n->r; else n = n->l;} return o;}
  441.     size_t count_keys_less(K key) {Node* n = root; size_t o = 0; while (n) {push(n); if (n->key < key) o += gsz(n->l) + 1, n = n->r; else n = n->l;} return o;}
  442.     size_t count_keys_in_seg(K l, K r) {return l > r ? 0 : count_keys_leq(r) - count_keys_less(l);}
  443.     size_t count_keys_geq(K key) {return gsz(root) - count_keys_less(key);}
  444.     size_t count_keys_greater(K key) {return gsz(root) - count_keys_leq(key);}
  445.     size_t count_keys_eq(K key) {return count_keys_leq(key) - count_keys_less(key);}
  446.  
  447.     K pref_sumkey(size_t p) {Node* n = root; K sm = 0; while (n) {push(n); if (gsz(n->l) == p) return sm + gsmk(n->l) + n->key; if (gsz(n->l) < p) sm += gsmk(n->l) + n->key, p -= gsz(n->l) + 1, n = n->r; else n = n->l;} assert(0); return sm;}
  448.     K seg_sumkey_fast(size_t l, size_t r) {return pref_sumkey(r) - (l ? pref_sumkey(l - 1) : 0);}
  449.     K seg_sumkey_slow(size_t l, size_t r) {auto [lf, tmp] = split_size(root, l); auto [mid, rg] = split_size(tmp, r - l + 1); K ans = gsmk(mid); root = merge(merge(lf, mid), rg); return ans;}
  450.  
  451.     //If no such pos exists, these functions will return size()
  452.     size_t get_pos_of_leftest_key_leq(K key) {return pos_of_leftest_key_leq(root, key);}
  453.     size_t get_pos_of_closest_from_left_leq(size_t pos, K key) {return pos_of_closest_from_left_key_leq(root, pos, key);}
  454.     size_t get_pos_of_closest_from_right_leq(size_t pos, K key) {return pos_of_closest_from_right_key_leq(root, pos, key);}
  455.  
  456.     size_t get_pos_of_leftest_min_key() {return pos_of_leftest_min_key(root);}
  457.     size_t get_pos_of_rightest_min_key() {return pos_of_rightest_min_key(root);}
  458.  
  459.     void add_to_all_keys(K val) {
  460.         apply_push(root, val);
  461.     }
  462.  
  463.     void cyclic_shift_left(int shift) {cyclic_shift_left(root, shift);}
  464.     void cyclic_shift_right(int shift) {cyclic_shift_right(root, shift);}
  465.     void seg_cyclic_shift_left(size_t l, size_t r, int shift) {auto [lf, tmp] = split_size(root, l); auto [mid, rg] = split_size(tmp, r - l + 1); cyclic_shift_left(mid, shift); root = merge(merge(lf, mid), rg);}
  466.     void seg_cyclic_shift_right(size_t l, size_t r, int shift) {auto [lf, tmp] = split_size(root, l); auto [mid, rg] = split_size(tmp, r - l + 1); cyclic_shift_right(mid, shift); root = merge(merge(lf, mid), rg);}
  467.  
  468.     void print_keys(string end_string = "") {print_keys(root); cout << end_string;}
  469.     vector<K> get_keys_from_seg(size_t l, size_t len) {vector<K> res; get_keys_on_subsegment(root, l, len, res); return res;}
  470. };
  471.  
  472. //Both array must be sorted
  473. //O(log(k)) comparator calls
  474. template<typename T_arr>
  475. auto kth_ordered_statistic_of_two_sorted_arrays(T_arr& m1, T_arr& m2, int k) {
  476.     auto cmp = [&](int u, int i, int j) {
  477.         if (u) swap(i, j);
  478.         int res = m1[i] < m2[j];
  479.         return res ^ u;
  480.     };
  481.     auto go = [&](auto&& go, int u, int i1, int n1, int i2, int n2, int k) -> array<int, 2> {
  482.         if (n1 > n2) return go(go, u ^ 1, i2, n2, i1, n1, k);
  483.         if (n1 == 0) return {u ^ 1, i2 + k};
  484.         if (k == 0) {
  485.             if (cmp(u, i1, i2)) return {u, i1};
  486.             return {u ^ 1, i2};
  487.         }
  488.         int i = min(n1, (k + 1) / 2);
  489.         int j = min(n2, (k + 1) / 2);
  490.         int fl = cmp(u, i1 + i - 1, i2 + j - 1);
  491.         return fl ? go(go, u, i1 + i, n1 - i, i2, n2, k - i) :
  492.                go(go, u, i1, n1, i2 + j, n2 - j, k - j);
  493.     };
  494.     assert(k < m1.size() + m2.size());
  495.     auto [u, i] = go(go, 0, 0, m1.size(), 0, m2.size(), k);
  496.     return (u == 0 ? m1 : m2)[i];
  497. }
  498.  
  499. class Solution {
  500. public:
  501.     long long minimumMoves(vector<int>& m, int k, int mc) {
  502.         ll o = 1e18;
  503.         ll a = m.size();
  504.         treap<ll> t1, t2;
  505.         for (int q = 1; q < a; ++q) {
  506.             if(m[q]) t2.insert_key(q + 1);
  507.         }
  508.         for (int q = 0; q < a; ++q) {
  509.             t1.add_to_all_keys(1);
  510.             t2.add_to_all_keys(-1);
  511.             if (!t2.empty() && t2[0] == 1) {
  512.                 t2.erase_pos(0);
  513.             }
  514.             if (q > 1 && m[q-2]) t1.insert_key(2);
  515.             ll tyt = 0, eso = k;
  516.             vec<ll> u = {m[q], (q && m[q-1]) + (q + 1 < a && m[q+1]), mc};
  517.             for (int i = 0; i < 3; ++i) {
  518.                 ll mn = min<ll>(eso, u[i]);
  519.                 eso -= mn;
  520.                 tyt += i * mn;
  521.             }
  522.             if (eso) {
  523.                 assert(eso <= t1.size() + t2.size());
  524.                 ll kth = kth_ordered_statistic_of_two_sorted_arrays(t1, t2, eso - 1);
  525.                 ll lq1 = t1.count_keys_leq(kth);
  526.                 ll lq2 = t2.count_keys_leq(kth);
  527.                 assert(lq1 + lq2 >= eso);
  528.                 tyt += (lq1 ? t1.pref_sumkey(lq1 - 1) : 0) + (lq2 ? t2.pref_sumkey(lq2 - 1) : 0) - kth * (lq1 + lq2 - eso);
  529.             }
  530.             // cout << q << ": " << tyt << endl;
  531.             chmin(o, tyt);
  532.         }
  533.         return o;
  534.     }
  535. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!