fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll INF = (1LL<<62);
  5.  
  6. // Tính chi phí cho mỗi vị trí bắt đầu t=1..N để gom K học sinh (pos) vào K vị trí liên tiếp t..t+K-1
  7. // Trả về vector size N: cost[t-1]
  8. vector<ll> compute_costs_fast(int N, int K, vector<int>& pos) {
  9.     if (K == 0) return vector<ll>(N, 0);
  10.     vector<int> P = pos;
  11.     sort(P.begin(), P.end());
  12.     // A: nhân đôi
  13.     vector<int> A(2*K);
  14.     for (int i = 0; i < K; ++i) {
  15.         A[i] = P[i];
  16.         A[i+K] = P[i] + N;
  17.     }
  18.     // D[k] = A[k] - k
  19.     vector<ll> D(2*K);
  20.     for (int k = 0; k < 2*K; ++k) D[k] = (ll)A[k] - (ll)k;
  21.     // prefix sums
  22.     vector<ll> pref(2*K+1, 0);
  23.     for (int i = 0; i < 2*K; ++i) pref[i+1] = pref[i] + D[i];
  24.  
  25.     // Precompute medians for windows idx=0..K-1
  26.     // median of D[l..r-1] where l=idx, r=idx+K: choose lower median at position l + (K-1)/2
  27.     vector<ll> med_idx(K);
  28.     int midOff = (K-1)/2;
  29.     for (int idx = 0; idx < K; ++idx) {
  30.         ll medD = D[idx + midOff];
  31.         med_idx[idx] = medD + idx; // median of (D_j + idx)
  32.     }
  33.  
  34.     vector<ll> cost(N, INF);
  35.     // For each t, binary search med_idx to get 1 or 2 candidate windows
  36.     for (int t = 1; t <= N; ++t) {
  37.         int pos = (int)(lower_bound(med_idx.begin(), med_idx.end(), (ll)t) - med_idx.begin());
  38.         // check pos and pos-1
  39.         for (int cand = pos-1; cand <= pos; ++cand) {
  40.             if (cand < 0 || cand >= K) continue;
  41.             int l = cand, r = cand + K; // D[l..r-1]
  42.             ll val = (ll)t - (ll)cand; // want sum |D - val|
  43.             // count m = number of D[l..r-1] <= val
  44.             int m = (int)(upper_bound(D.begin() + l, D.begin() + r, val) - (D.begin() + l));
  45.             ll sumLeft = val * (ll)m - (pref[l + m] - pref[l]);
  46.             ll sumRight = (pref[r] - pref[l + m]) - val * (ll)(K - m);
  47.             ll cur = sumLeft + sumRight;
  48.             if (cur < cost[t-1]) cost[t-1] = cur;
  49.         }
  50.     }
  51.     return cost;
  52. }
  53.  
  54. // Sparse table cho RMQ min
  55. struct SparseTable {
  56.     int n, LOG;
  57.     vector<vector<ll>> st;
  58.     vector<int> lg;
  59.     SparseTable() {}
  60.     SparseTable(const vector<ll>& a) {
  61.         n = (int)a.size();
  62.         lg.assign(n+1, 0);
  63.         for (int i=2;i<=n;++i) lg[i] = lg[i>>1] + 1;
  64.         LOG = lg[n];
  65.         st.assign(LOG+1, vector<ll>(n));
  66.         st[0] = a;
  67.         for (int k = 1; k <= LOG; ++k) {
  68.             for (int i = 0; i + (1<<k) <= n; ++i) {
  69.                 st[k][i] = min(st[k-1][i], st[k-1][i + (1<<(k-1))]);
  70.             }
  71.         }
  72.     }
  73.     ll range_min(int l, int r) { // inclusive 0-based
  74.         if (l > r) return INF;
  75.         int len = r - l + 1;
  76.         int k = lg[len];
  77.         return min(st[k][l], st[k][r - (1<<k) + 1]);
  78.     }
  79. };
  80.  
  81. int main() {
  82.     ios::sync_with_stdio(false);
  83.     cin.tie(nullptr);
  84.     int T;
  85.     if (!(cin >> T)) return 0;
  86.     while (T--) {
  87.         int N, M, L;
  88.         cin >> N >> M >> L;
  89.         vector<int> P(M), Q(L);
  90.         for (int i = 0; i < M; ++i) cin >> P[i];
  91.         for (int i = 0; i < L; ++i) cin >> Q[i];
  92.         // compute costs
  93.         vector<ll> costP = compute_costs_fast(N, M, P);
  94.         vector<ll> costQ = compute_costs_fast(N, L, Q);
  95.  
  96.         // duplicate costQ to handle circular interval selection
  97.         vector<ll> costQ2(2*N);
  98.         for (int i = 0; i < 2*N; ++i) costQ2[i] = costQ[i % N];
  99.  
  100.         SparseTable st(costQ2);
  101.  
  102.         ll ans = INF;
  103.         // try each start t1 for P block (1..N)
  104.         for (int t1 = 1; t1 <= N; ++t1) {
  105.             // Q block starts must be in [t1+M .. t1 + N - L] (1-based)
  106.             int l = t1 + M;
  107.             int r = t1 + N - L;
  108.             int Lidx = l - 1;
  109.             int Ridx = r - 1;
  110.             if (Lidx < 0) Lidx = 0;
  111.             if (Ridx >= 2*N) Ridx = 2*N - 1;
  112.             if (Lidx <= Ridx) {
  113.                 ll bestQ = st.range_min(Lidx, Ridx);
  114.                 ans = min(ans, costP[t1-1] + bestQ);
  115.             }
  116.         }
  117.         cout << ans << '\n';
  118.     }
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
1
12 6 4
1 3 5 7 9 11
2 12 8 4
stdout 
15
https://ideone.com/xP3mGV
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

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!