fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. ll add = 0;
  6.  
  7. bool getArrays(vector<int> &X, vector<int> &P, vector<int> &A, vector<int> &B) {
  8.     vector<int> a, b;
  9.     int m = P.size();
  10.     int prev = 0;
  11.     int fpb = -1;
  12.     for (int i = 0; i < m; i++) {
  13.         for (int j = prev; j < P[i]; j++) {
  14.             a.push_back(X[j]);
  15.         }
  16.         b.push_back(X[P[i]]);
  17.         prev = P[i] + 1;
  18.     }
  19.     for (int i = prev; i < X.size(); i++) {
  20.         a.push_back(X[i]);
  21.     }
  22.  
  23.     int n = a.size();
  24.     P.clear();
  25.     int l = 0, r = m - 1;
  26.     while (l < r) {
  27.         if (b[l] == -b[r]) {
  28.             l++;
  29.             r--;
  30.         } else if (abs(b[l]) > abs(b[r])) {
  31.             P.push_back(b[l++]);
  32.         } else if (abs(b[l]) <= abs(b[r])) {
  33.             P.push_back(b[r--]);
  34.         }
  35.     }
  36.     if (l == r) {
  37.         if (b[l] != 0) {
  38.             P.push_back(b[l]);
  39.         }
  40.     }
  41.     sort(P.begin(), P.end());
  42.     swap(b, P);
  43.  
  44.     m = b.size();
  45.     if (m > n) {
  46.         return 0;
  47.     }
  48.  
  49.     for (int i = 0; i < m; i++) {
  50.         if (b[i] >= 0 && fpb == -1) {
  51.             fpb = i;
  52.         }
  53.     }
  54.     if (fpb == -1) fpb = b.size();
  55.  
  56.     int lb = fpb, rb = b.size() - fpb;
  57.     int each = (n + m) / 2;
  58.     for (int i = 0; i < each - lb; i++) {
  59.         if (a[i] > 0) {
  60.             add += abs(a[i]);
  61.             a[i] = 0;
  62.         }
  63.     }
  64.     for (int i = n - 1; i >= n - (each - rb); i--) {
  65.         if (a[i] < 0) {
  66.             add += abs(a[i]);
  67.             a[i] = 0;
  68.         }
  69.     }
  70.  
  71.     int lbound = each - lb;
  72.     int rbound = n - (each - rb);
  73.     X.clear();
  74.     P.clear();
  75.     for (int i = 0; i < lbound; i++) {
  76.         X.push_back(abs(a[i]));
  77.         assert(a[i] <= 0);
  78.     } for (int i = rbound; i < n; i++) {
  79.         P.push_back(a[i]);
  80.         assert(a[i] >= 0);
  81.     } for (int i = lbound; i < rbound; i++) {
  82.         add += abs(a[i]);
  83.     }
  84.     for (int i = 0; i < m; i++) {
  85.         (b[i] < 0 ? A : B).push_back(abs(b[i]));
  86.     }
  87.  
  88.     reverse(A.begin(), A.end());
  89.     reverse(X.begin(), X.end());
  90.     return 1;
  91. }
  92.  
  93. struct fenwick {
  94.     int n;
  95.     vector<ll> sum;
  96.     fenwick(int N) {
  97.         n = N;
  98.         sum.assign(n + 1, 0);
  99.     }
  100.  
  101.     void update(int i, int v) {
  102.         i++;
  103.         for (; i <= n; i += i & -i) 
  104.             sum[i] += v;
  105.     }
  106.  
  107.     ll query(int i) {
  108.         ll ans = 0;
  109.         for (; i; i -= i & -i) 
  110.             ans += sum[i];
  111.         return ans;
  112.     }
  113.  
  114.     ll get(int l, int r) {
  115.         return query(r + 1) - query(l);
  116.     }
  117. };
  118.  
  119. long long get_cost(vector<int> a, vector<int> b) {
  120.     vector<int> A, B;
  121.     if (!getArrays(a, b, A, B)) {
  122.         return -1;
  123.     }
  124.     assert(a.size() - B.size() == b.size() - A.size());
  125.     int off = a.size() - B.size();
  126.  
  127.     int n = a.size(), N = A.size();
  128.     int m = b.size(), M = B.size();
  129.     int tot = n + N;
  130.  
  131.     fenwick sgA(A.size() + 1), sgB(B.size() + 1), sga(a.size() + 1), sgb(b.size() + 1);
  132.     vector<vector<int>> chA(off + 1), chB(off + 1), cha(off + 1), chb(off + 1);
  133.     for (int i = 0; i < A.size(); i++) {
  134.         sgA.update(i, A[i]);
  135.         int id = lower_bound(b.begin(), b.end(), A[i]) - b.begin();
  136.         int get = max(0, id - i);
  137.         if (get <= off) {
  138.             chA[get].push_back(i);
  139.         }
  140.     } for (int i = 0; i < B.size(); i++) {
  141.         sgB.update(i, B[i]);
  142.         int id = lower_bound(a.begin(), a.end(), B[i]) - a.begin();
  143.         int get = max(0, id - i);
  144.         if (get <= off) {
  145.             chB[get].push_back(i);
  146.         }
  147.     } for (int i = 0; i < a.size(); i++) {
  148.         sga.update(i, -a[i]);
  149.         int id = upper_bound(B.begin(), B.end(), a[i]) - B.begin() - 1;
  150.         int get = max(0, i - id);
  151.         if (get <= off) {
  152.             cha[get].push_back(i);
  153.         }
  154.     } for (int i = 0; i < b.size(); i++) {
  155.         sgb.update(i, -b[i]);
  156.         int id = upper_bound(A.begin(), A.end(), b[i]) - A.begin() - 1;
  157.         int get = max(0, i - id);
  158.         if (get <= off) {
  159.             chb[get].push_back(i);
  160.         }
  161.     }
  162.  
  163.     vector<array<int, 2>> Am(tot + 1), Bm(tot + 1);
  164.     Am[0] = Bm[0] = {-1, -1};
  165.     for (int i = 0; i < m; i++) 
  166.         Bm[i + 1] = {b[i], i};
  167.     for (int i = 0; i < M; i++) 
  168.         Bm[i + m + 1] = {B[i], i + m};
  169.     for (int i = 0; i < n; i++) 
  170.         Am[i + 1] = {a[i], i};
  171.     for (int i = 0; i < N; i++) 
  172.         Am[i + n + 1] = {A[i], i + n};
  173.     sort(Am.begin(), Am.end());
  174.     sort(Bm.begin(), Bm.end());
  175.  
  176.     vector<vector<int>> places(off + 1), getNxt(off + 1);
  177.     places[off].push_back(0);
  178.     vector<array<int, 4>> counts(tot + 1); // {a, A, b, B}
  179.     vector<int> need(tot + 1);
  180.     need[0] = off;
  181.     for (int i = 1; i <= tot; i++) {
  182.         counts[i] = counts[i - 1];
  183.         need[i] = need[i - 1];
  184.  
  185.         bool s = Am[i][1] >= n;
  186.         bool k = Bm[i][1] >= m;
  187.         counts[i][s]++;
  188.         counts[i][k + 2]++;
  189.  
  190.         bool ok = false;
  191.         if (s == k) {
  192.             if (s) {
  193.                 need[i]++;
  194.             } else if (!s) {
  195.                 need[i]--;
  196.                 ok = true;
  197.             }
  198.         }
  199.         if (need[i] <= off && need[i] >= 0) {
  200.             if (ok) getNxt[need[i]].push_back(i);
  201.             places[need[i]].push_back(i);
  202.         }
  203.     }
  204.  
  205.     assert(need[tot] == 0);
  206.  
  207.     vector<ll> dp(tot + 1, 1e18);
  208.     auto getCost = [&](array<int, 4> &x, array<int, 4> &y) { // {a, A, b, B}
  209.         ll ret = 0;
  210.         if (x[0] != y[0]) 
  211.             ret += sga.get(x[0], y[0] - 1) + sgB.get(x[3], y[3] - 1);
  212.         if (x[2] != y[2]) 
  213.             ret += sgA.get(x[1], y[1] - 1) + sgb.get(x[2], y[2] - 1);
  214.         return ret;
  215.     };
  216.     dp[0] = 0;
  217.     int cnt = 0;
  218.     for (int i = off; i >= 0; i--) {
  219.         for (int &x : chA[cnt]) {
  220.             sgA.update(x, -2 * A[x]);
  221.         } for (int &x : chB[cnt]) {
  222.             sgB.update(x, -2 * B[x]);
  223.         } for (int &x : cha[cnt]) {
  224.             sga.update(x, 2 * a[x]);
  225.         } for (int &x : chb[cnt]) {
  226.             sgb.update(x, 2 * b[x]);
  227.         }
  228.         for (int j = 0; j < places[i].size(); j++) {
  229.             int x = places[i][j];
  230.  
  231.             if (j + 1 != places[i].size()) {
  232.                 int nxt = places[i][j + 1];
  233.                 dp[nxt] = min(dp[nxt], dp[x] + getCost(counts[x], counts[nxt]));
  234.             }
  235.             if (i) {
  236.                 int id = upper_bound(getNxt[i - 1].begin(), getNxt[i - 1].end(), x) - getNxt[i - 1].begin();
  237.                 if (id != getNxt[i - 1].size()) {
  238.                     int nxt = getNxt[i - 1][id];
  239.                     dp[nxt] = min(dp[nxt], dp[x] + getCost(counts[x], counts[nxt - 1]) + 
  240.                     abs(Am[nxt][0] - Bm[nxt][0]));
  241.                 } 
  242.             }
  243.         }
  244.         cnt++;
  245.     }
  246.  
  247.     return add + dp[tot];
  248. }
  249.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/KyTdUP
language:
C++ (gcc 8.3)
created:
12 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!