API tools faq
paste
Advertisement
prog3r

DP with ST

prog3r
Nov 12th, 2024
59
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.98 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using vbo = vector<bool>;
  4. using ll = long long;
  5. using ull = unsigned long long;
  6. using pll = pair<ll, ll>;
  7. using ld = long double;
  8. using qll = queue<ll>;
  9. using vll = vector<ll>;
  10. using vvll = vector<vector<ll>>;
  11. using vvpll = vector<vector<pll>>;
  12. using qld = queue<ld>;
  13. using vld = vector<ld>;
  14. using qpll = queue<pll>;
  15. using vpll = vector<pll>;
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp>
  18. using namespace __gnu_pbds;
  19. template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  20. //ostream& endl(ostream& os) {
  21. //    return os << '\n';
  22. //}
  23. #define all(xxx) xxx.begin(), xxx.end()
  24. #define watch(xxx) cout << "value of " << #xxx << " is " << xxx << endl;
  25. template <class T, class S> inline bool chmax(T &best, const S &b) { return (best < b ? best = b, 1 : 0); }
  26. template <class T, class S> inline bool chmin(T &best, const S &b) { return (best > b ? best = b, 1 : 0); }
  27. template <typename T, typename U>
  28. ostream& operator<<(ostream& os, const pair<T, U>& A) {
  29.     os << A.fi << " " << A.se;
  30.     return os;
  31. }
  32. template <typename T>
  33. ostream& operator<<(ostream& os, const vector<T>& A) {
  34.     for (size_t i = 0; i < A.size(); i++) {
  35.         if (i) os << " ";
  36.         os << A[i];
  37.     }
  38.     return os;
  39. }
  40. void scan(ll &best) { cin >> best; }
  41. void scan(char &best) { cin >> best; }
  42. void scan(double &best) { cin >> best; }
  43. void scan(long double &best) { cin >> best; }
  44. void scan(string &best) { cin >> best; }
  45. template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }
  46. template <class T> void scan(vector<T> &best) {for(auto &i : best) scan(i);}
  47. template <class T> void scan(T &best) { cin >> best; }
  48. void IN() {}
  49. template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {
  50.     scan(head);
  51.     IN(tail...);
  52. }
  53. void print() {
  54.     cout << "\n";
  55. }
  56. template <class Head, class... Tail>
  57. void print(Head&& head, Tail&&... tail) {
  58.     cout << head;
  59.     if (sizeof...(Tail)) cout << " ";
  60.     print(forward<Tail>(tail)...);
  61. }
  62. //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math,trapv")
  63. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math")
  64. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  65. uniform_int_distribution<ll> distrib(1ll, 10ll);
  66. //constexpr ll MOD = 819356875157278019ll;
  67. constexpr ll MOD = 1e9+7;
  68. void in(vector<ll> & best) {
  69.     for (auto & zero_leaf : best) cin >> zero_leaf;
  70. }
  71. void in(vector<ll> & best, ll l, ll r) {
  72.     for (ll i=l; i < r; i+=1) {
  73.         cin >> best[i];
  74.     }
  75. }
  76. void inn(vector<ll> & best, ll l, ll rr) {
  77.     for (ll i=l; i <= rr; i+=1) {
  78.         cin >> best[i];
  79.     }
  80. }
  81. ll powm(ll best, ll b) {
  82.     assert(b >= 0);
  83.     ll d = 1;
  84.     while (b) {
  85.         if (b&1) d = (d*best) % MOD;
  86.         b >>= 1;
  87.         best = (best*best) % MOD;
  88.     }
  89.     return d;
  90. }
  91. ll powm(ll best, ll b, ll MODD) {
  92.     assert(b >= 0);
  93.     ll d = 1;
  94.     while (b) {
  95.         if (b&1) d = (d*best) % MODD;
  96.         b >>= 1;
  97.         best = (best*best) % MODD;
  98.     }
  99.     return d;
  100. }
  101. ll poww(ll best, ll b) {
  102.     assert(b >= 0);
  103.     ll d = 1;
  104.     while (b) {
  105.         if (b&1) d = (d*best);
  106.         b >>= 1;
  107.         best = (best*best);
  108.     }
  109.     return d;
  110. }
  111. ld poww(ld best, ll b) {
  112.     assert(b >= 0);
  113.     ld d = 1;
  114.     while (b) {
  115.         if (b&1) d = (d*best);
  116.         b >>= 1;
  117.         best = (best*best);
  118.     }
  119.     return d;
  120. }
  121. ll mul(ll best, ll b) {
  122.     return (best*b)%MOD;
  123. }
  124. ll mul(ll best, ll b, ll MODD) {
  125.     return (best*b)%MODD;
  126. }
  127. ll sum(ll best, ll b) {
  128.     return (best+b)%MOD;
  129. }
  130. ll sum(ll best, ll b, ll MODD) {
  131.     return (best+b)%MODD;
  132. }
  133. ll sub(ll best, ll b) {
  134.     return (best-(b%MOD)+MOD)%MOD;
  135. }
  136. ll sub(ll best, ll b, ll MODD) {
  137.     return (best-(b%MODD)+MODD)%MODD;
  138. }
  139. void solve() {
  140.     ll n; cin >> n;
  141.     vll a(n); for (auto &x : a) cin >> x;
  142.     a.insert(a.begin(), 0ll);
  143.     struct shit {
  144.         ll val;
  145.         ll pos;
  146.         auto operator<(const shit& other) {
  147.             return val < other.val;
  148.         };
  149.     };
  150.     vector<shit> positions(n+1);
  151.     for (ll i = 0; i <= n; i += 1) {
  152.         positions[i].val = a[i];
  153.         positions[i].pos = i;
  154.     }
  155.     sort(all(positions));
  156.     vll idx_by_order(n+1);
  157.     for (ll i = 0; i <= n; i += 1) {
  158.         idx_by_order[positions[i].pos] = i;
  159.     }
  160.     vll simple_sorted_for_ub;
  161.     for (ll i = 0; i <= n; i += 1) simple_sorted_for_ub.push_back(positions[i].val);
  162.     struct node {
  163.         ll val=1e18;
  164.         ll push=0;
  165.     };
  166.     vector<node> ST_plus_val(4*n+10);
  167.     vector<node> ST_minus_val(4*n+10);
  168.     vector<node> BASIC(4*n+10);
  169.     auto merge = [&] (ll v, vector<node>& tree) {
  170.         assert(tree[v].push == 0);
  171.         tree[v].val = min(tree[2*v+1].val, tree[2*v+2].val);
  172.     };
  173.     auto push = [&] (ll v, vector<node>& tree) {
  174.         tree[2*v+1].val += tree[v].push;
  175.         tree[2*v+1].push += tree[v].push;
  176.         tree[2*v+2].val += tree[v].push;
  177.         tree[2*v+2].push += tree[v].push;
  178.         tree[v].push = 0;
  179.     };
  180.     auto set_point = [&] (auto f, ll v, ll tl, ll tr, ll pos, ll val, vector<node>& tree) -> void {
  181.         if (tl == tr) {
  182.             tree[v].val = val;
  183.             return;
  184.         }
  185.         push(v, tree);
  186.         ll tm = (tl+tr) >> 1;
  187.         if (pos <= tm) {
  188.             f(f, 2*v+1, tl, tm, pos, val, tree);
  189.         } else {
  190.             f(f, 2*v+2, tm+1, tr, pos, val, tree);
  191.         }
  192.         merge(v, tree);
  193.     };
  194.     auto add_on_segment = [&] (auto f, ll v, ll tl, ll tr, ll l, ll r, ll inc, vector<node>& tree)  -> void {
  195.         if (tl == l && tr == r) {
  196.             tree[v].val += inc;
  197.             tree[v].push = inc;
  198.             return;
  199.         }
  200.         push(v, tree);
  201.         ll tm = (tl+tr) >> 1;
  202.         if (l <= tm) {
  203.             f(f, 2*v+1, tl, tm, l, min(r, tm), inc, tree);
  204.         }
  205.         if (r >= tm+1) {
  206.             f(f, 2*v+2, tm+1, tr, max(tm+1, l), r, inc, tree);
  207.         }
  208.         merge(v, tree);
  209.     };
  210.     auto get_minimum = [&] (auto f, ll v, ll tl, ll tr, ll l, ll r, vector<node>& tree) -> ll {
  211.         if (l > r) return 1e18;
  212.         if (tl == l && tr == r) {
  213.             return tree[v].val;
  214.         }
  215.         push(v, tree);
  216.         ll tm = (tl+tr) >> 1;
  217.         ll x = 1e18;
  218.         if (l <= tm) {
  219.             x = min(x, f(f, 2*v+1, tl, tm, l, min(r, tm), tree));
  220.         }
  221.         if (r >= tm+1) {
  222.             x = min(x, f(f, 2*v+2, tm+1, tr, max(tm+1, l), r, tree));
  223.         }
  224.         return x;
  225.     };
  226.     auto print = [&] (vector<node>& tree) {
  227.         for (ll i = 0; i <= n; i += 1) {
  228.             set_point(set_point, 0, 0, n, idx_by_order[0], 0, BASIC);
  229.             cout << get_minimum(get_minimum, 0, 0, n, i, i, tree) << ' ';
  230.         }
  231.         cout << " (printed)" << endl;
  232.     };
  233.     set_point(set_point, 0, 0, n, idx_by_order[0], 0-positions[idx_by_order[0]].val, ST_minus_val);
  234.     set_point(set_point, 0, 0, n, idx_by_order[0], 0+positions[idx_by_order[0]].val, ST_plus_val);
  235.     set_point(set_point, 0, 0, n, idx_by_order[0], 0, BASIC);
  236.     for (ll i = 1; i <= n; i += 1) {
  237.         ll THIS = positions[idx_by_order[i]].val;
  238.         ll first_minus = upper_bound(all(simple_sorted_for_ub), THIS)-simple_sorted_for_ub.begin();
  239.         ll old_goes_now = 1e18;
  240.         old_goes_now = min(old_goes_now, get_minimum(get_minimum,0,0,n,0,first_minus-1,ST_minus_val)+THIS);
  241.         old_goes_now = min(old_goes_now, get_minimum(get_minimum,0,0,n,first_minus,n,ST_plus_val)-THIS);
  242.         ll VAL = abs(positions[idx_by_order[i]].val-positions[idx_by_order[i-1]].val);
  243.         add_on_segment(add_on_segment, 0, 0, n, 0, n, VAL, ST_minus_val);
  244.         add_on_segment(add_on_segment, 0, 0, n, 0, n, VAL, ST_plus_val);
  245.         add_on_segment(add_on_segment, 0, 0, n, 0, n, VAL, BASIC);
  246.         ll SHIT = min(get_minimum(get_minimum,0,0,n,idx_by_order[i-1],idx_by_order[i-1],BASIC), old_goes_now);
  247.         set_point(set_point, 0, 0, n, idx_by_order[i-1], SHIT-positions[idx_by_order[i-1]].val, ST_minus_val);
  248.         set_point(set_point, 0, 0, n, idx_by_order[i-1], SHIT+positions[idx_by_order[i-1]].val, ST_plus_val);
  249.         set_point(set_point, 0, 0, n, idx_by_order[i-1], SHIT, BASIC);
  250.     }
  251.     cout << get_minimum(get_minimum,0,0,n,0,n,BASIC) << endl;
  252. }
  253.  
  254.  
  255.  
  256. int32_t main(int32_t argc, char* argv[]) {
  257. //    ifstream cin("distance.in");
  258. //    ofstream cout("distance.out");
  259.     cout << fixed << setprecision(17);
  260.     bool use_fast_io = true;
  261.     for (int32_t i = 1; i < argc; ++i) {
  262.         if (string(argv[i]) == "-local-no-fast-io") {
  263.             use_fast_io = false;
  264. //            cout << "No fastIO" << endl;
  265.             break;
  266.         }
  267.     }
  268.     if (use_fast_io) {
  269.         ios::sync_with_stdio(false);
  270.         cin.tie(nullptr);
  271.         cout.tie(nullptr);
  272.         cerr.tie(nullptr);
  273.         clog.tie(nullptr);
  274.     }
  275.     ll tt = 1;
  276. //    cin >> tt;
  277.  
  278.     while (tt--) {
  279.         solve();
  280.     }
  281.     return 0;
  282. }
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!