fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // We need to store Slope (m) and Constant (c)
  5. // Value at index i = (slope * i) + c
  6. struct node {
  7.     long long slope;
  8.     long long c;
  9. };
  10.  
  11. node tree[400009];
  12. long long ans[400009]; // Use long long for the answer to prevent overflow
  13.  
  14. // Pushes the slope and constant down to children
  15. void push(int node, int tl, int tr) {
  16.     // Left Child
  17.     tree[2*node].slope += tree[node].slope;
  18.     tree[2*node].c     += tree[node].c;
  19.  
  20.     // Right Child
  21.     tree[2*node+1].slope += tree[node].slope;
  22.     tree[2*node+1].c     += tree[node].c;
  23.  
  24.     // Reset current
  25.     tree[node].slope = 0;
  26.     tree[node].c = 0;
  27. }
  28.  
  29. // Update adds 'm_add' to slope and 'c_add' to constant for range [l, r]
  30. void update(int node, int l, int r, int tl, int tr, long long m_add, long long c_add) {
  31.     if (l > r) {
  32.         return;
  33.     }
  34.     if (l == tl && r == tr) {
  35.         tree[node].slope += m_add;
  36.         tree[node].c += c_add;
  37.     } else {
  38.         push(node, tl, tr);
  39.         int mid = (tl + tr) / 2;
  40.         update(2*node, l, min(r, mid), tl, mid, m_add, c_add);
  41.         update(2*node+1, max(l, mid+1), r, mid+1, tr, m_add, c_add);
  42.     }
  43. }
  44.  
  45. // Traverse to leaves to calculate final values
  46. void query(int node, int l, int r) {
  47.     if (l == r) {
  48.         // Calculate final value: y = mx + c
  49.         ans[l] = tree[node].slope * l + tree[node].c;
  50.         return;
  51.     }
  52.     push(node, l, r);
  53.     int mid = (l + r) / 2;
  54.     query(2*node, l, mid);
  55.     query(2*node+1, mid+1, r);
  56. }
  57.  
  58. int main() {
  59.     ios_base::sync_with_stdio(false);
  60.     cin.tie(NULL);
  61.     cout.tie(NULL);
  62.  
  63.     int n, m;
  64.     if (!(cin >> n >> m)) return 0;
  65.  
  66.     vector<int> v(n);
  67.     for (int i = 0; i < n; i++) {
  68.         cin >> v[i];
  69.     }
  70.  
  71.     long long base_cost = 0;
  72.  
  73.     for (int i = 0; i < n - 1; i++) {
  74.         int start = v[i];
  75.         int target = v[i+1];
  76.  
  77.         // 1. Calculate Standard Scrolling Cost (Cyclic distance)
  78.         int dist = target - start;
  79.         if (dist < 0) dist += m;
  80.         base_cost += dist;
  81.  
  82.         // 2. Calculate Savings
  83.         // Using button 'x' costs: 1 + dist(x, target)
  84.         // We save: dist - (1 + dist(x, target))
  85.         // Max saving is (dist - 1) when x == target.
  86.         // As x moves back from target, saving drops by 1.
  87.  
  88.         int max_save = dist - 1;
  89.         if (max_save <= 0) continue;
  90.  
  91.         // We need to add a sequence 1, 2, 3... ending at 'target' with value 'max_save'
  92.         // Equation for line: y = 1*i + C
  93.  
  94.         int len = max_save; 
  95.         int start_idx = target - len + 1;
  96.  
  97.         if (start_idx >= 1) {
  98.             // Case 1: The saving range is contiguous (e.g., indices 3, 4, 5)
  99.             // Sequence starts at index 'start_idx' with value 1.
  100.             // 1 = 1 * start_idx + C  =>  C = 1 - start_idx
  101.             update(1, start_idx, target, 1, m, 1, 1 - start_idx);
  102.         } else {
  103.             // Case 2: The saving range wraps around (e.g., indices ..., m, 1, 2)
  104.  
  105.             // Part A: Suffix of array [m - (needed_len) + 1, m]
  106.             // Length of part A
  107.             int len_suffix = len - target;
  108.             int suffix_start = m - len_suffix + 1;
  109.  
  110.             // Starts with value 1 at suffix_start
  111.             // 1 = 1 * suffix_start + C => C = 1 - suffix_start
  112.             update(1, suffix_start, m, 1, m, 1, 1 - suffix_start);
  113.  
  114.             // Part B: Prefix of array [1, target]
  115.             // This continues the sequence. Value at index 1 is not 1, but (len_suffix + 1).
  116.             // val = 1 * i + C
  117.             // (len_suffix + 1) = 1 * 1 + C => C = len_suffix
  118.             update(1, 1, target, 1, m, 1, len_suffix);
  119.         }
  120.     }
  121.  
  122.     // Push all lazy values down to leaves
  123.     query(1, 1, m);
  124.  
  125.     long long best_saving = 0;
  126.     for (int i = 1; i <= m; i++) {
  127.         if (ans[i] > best_saving) {
  128.             best_saving = ans[i];
  129.         }
  130.     }
  131.  
  132.     cout << base_cost - best_saving << "\n";
  133. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin 
6 6
6 5 4 3 2 1
stdout 
15
https://ideone.com/oBdyyl
language:
C++14 (gcc 8.3)
created:
7 hours 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!