welleyth

I. Степан і кубики

Jun 23rd, 2021 (edited)
739
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define pb push_back
  9. #define int long long
  10. #define mp make_pair
  11. #define left left_compile
  12. #define right right_compile
  13.  
  14. const int INF = (int)1e15;
  15. const int md = (int)1e9 + 7;
  16. const int MAXN = (int)1e5 + 10;
  17. const int N = (int)2e5 + 1111;
  18. const int debug = 0;
  19.  
  20. typedef tree<
  21. int,
  22. null_type,
  23. less_equal<int>,
  24. rb_tree_tag,
  25. tree_order_statistics_node_update>
  26. ordered_set;
  27.  
  28. mt19937 rnd(time(nullptr));
  29.  
  30. vector<vector<int>> t(4*N);
  31. vector<vector<int>> pr(4*N);
  32. vector<int> sum(4*N);
  33. int a[N];
  34.  
  35. vector<int> ans;
  36.  
  37. vector<int> Mg(vector<int> a,vector<int> b){
  38.     ans.clear();
  39.     int id[2];
  40.     id[0] = id[1] = 0;
  41.     int sz[2];
  42.     sz[0] = a.size(), sz[1] = b.size();
  43.     while(id[0] < sz[0] && id[1] < sz[1]){
  44.         if(a[id[0]] < b[id[1]])
  45.             ans.pb(a[id[0]++]);
  46.         else
  47.             ans.pb(b[id[1]++]);
  48.     }
  49.     while(id[0] < sz[0])
  50.         ans.pb(a[id[0]++]);
  51.     while(id[1] < sz[1])
  52.         ans.pb(b[id[1]++]);
  53.     return ans;
  54. }
  55.  
  56. void build(int v,int l,int r){
  57.     if(l > r)
  58.         return;
  59.     if(l == r){
  60.         t[v].pb(a[l]);
  61.         pr[v] = t[v];
  62.         sum[v] = a[l];
  63.         return;
  64.     }
  65.     int m = (r + l) / 2;
  66.     build(v<<1,l,m);
  67.     build(v<<1|1,m+1,r);
  68.     t[v] = Mg(t[v<<1],t[v<<1|1]);
  69.     sum[v] = sum[v<<1] + sum[v<<1|1];
  70.     pr[v] = t[v];
  71.     for(int i = 1; i < pr[v].size(); i++){
  72.         pr[v][i] += pr[v][i-1];
  73.     }
  74.     return;
  75. }
  76.  
  77. int ask(int v,int l,int r,int tl,int tr,int M){
  78.     if(l > r || tl > tr)
  79.         return 0;
  80.     if(l == tl && r == tr){
  81.         if(t[v].back() <= M){
  82.             return (r-l+1) * M - sum[v];
  83.         }
  84.         if(t[v][0] > M){
  85.             return sum[v] - (r - l + 1) * M;
  86.         }
  87.         int id = upper_bound(t[v].begin(),t[v].end(),M) - t[v].begin();
  88.         id--;
  89.         return M * (id + 1) - pr[v][id] + (sum[v] - pr[v][id]) - M * (r-l-id);
  90.     }
  91.     int m = (l + r) / 2;
  92.     return ask(v<<1,l,m,tl,min(tr,m),M) + ask(v<<1|1,m+1,r,max(m+1,tl),tr,M);
  93. }
  94.  
  95. vector<int> get(int v,int l,int r,int tl,int tr){
  96.     if(l > r || tl > tr)
  97.         return vector<int>();
  98.     if(l == tl && r == tr)
  99.         return t[v];
  100.     int m = (l + r) / 2;
  101.     return Mg(get(v<<1,l,m,tl,min(tr,m)),get(v<<1|1,m+1,r,max(m+1,tl),tr));
  102. }
  103.  
  104. int n,m;
  105.  
  106. void myerase(ordered_set& st, int v){
  107.     int r = st.order_of_key(v);
  108.     auto it = st.find_by_order(r);
  109.     st.erase(it);
  110.     return;
  111. }
  112.  
  113. void solve_case(){
  114.  
  115.     cin >> n >> m;
  116.  
  117.     for(int i = 0; i < n; i++){
  118.         cin >> a[i];
  119.     }
  120.  
  121.     build(1,0,n-1);
  122.  
  123.     vector<int> cur;
  124.     ordered_set st;
  125.  
  126.     for(int i = 0; i < m; i++){
  127.         st.insert(a[i]);
  128.     }
  129.  
  130.     int ans = INF;
  131.  
  132.     int k = 0;
  133.     while(2 * (k + 1) - m < 0)
  134.         k++;
  135.  
  136.     ans = min(ans,ask(1,0,n-1,0,m-1,*st.find_by_order(k)));
  137.  
  138.     for(int i = m; i < n; i++){
  139.         myerase(st,a[i-m]);
  140.         st.insert(a[i]);
  141.         auto it = st.find_by_order(k);
  142.         int t = *it;
  143.         ans = min(ans,ask(1,0,n-1,i-m+1,i,t));
  144.     }
  145.  
  146.     cout << ans;
  147.  
  148.     return;
  149. }
  150.  
  151. signed main(){
  152.     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  153. //    freopen("input.txt","r",stdin);
  154. //    freopen("output.txt","w",stdout);
  155.  
  156.     init();
  157.  
  158.     int t = 1;
  159. //    cin >> t;
  160.  
  161.     for(int _ = 1; _ <= t; _++){
  162. //        n = _;
  163.         solve_case();
  164.     }
  165.  
  166.     return 0;
  167. }
  168.  
  169. /*
  170. ..........
  171. .#........
  172. .#........
  173. .#........
  174. ..........
  175. ..........
  176. ..........
  177. ..........
  178. ..........
  179. .........#
  180.  
  181. */
  182.  
RAW Paste Data