/** * JOI 2019 Spring Camp - Cake 3 * * Problem Analysis: * We need to choose M pieces. Let the chosen pieces be sorted by Color: P_1, P_2, ..., P_M. * The beauty is sum(V) - sum(|C_diff|). * The sum of color differences in a circle for sorted colors is 2 * (C_max - C_min). * * Strategy: * 1. Sort all pieces by Color C. * 2. We need to select a range [i, j] in the sorted array such that: * - The pieces i and j are the min and max color boundaries. * - We select M pieces total from the range [i, j]. * - To maximize beauty, we must pick the M pieces with the largest Values V within [i, j]. * 3. The objective function for a fixed range [i, j] (where j >= i + M - 1): * f(i, j) = SumTopM(i, j) - 2 * (C[j] - C[i]) * 4. We use Divide and Conquer Optimization. * solve(i_start, i_end, j_start, j_end) computes the best j for i in [i_start, i_end]. * We maintain a global Segment Tree that tracks the values in the current window [curr_L, curr_R]. * * Complexity: O(N * log^2 N) */ #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; // Structure to represent a piece of cake struct Piece { long long v, c; int original_id; }; int N, M; vector<Piece> pieces; vector<long long> v_coords; // For coordinate compression of V // Segment Tree to maintain counts and sums of V values // We use coordinate compression on V values, so the tree size is N. const int MAXN = 200005; long long seg_count[4 * MAXN]; long long seg_sum[4 * MAXN]; // Add a value (by its compressed index/rank) to the segment tree void update(int node, int start, int end, int idx, int val_cnt, long long val_amount) { if (start == end) { seg_count[node] += val_cnt; seg_sum[node] += val_amount; // If val_cnt is 1, we add real_value; if -1, we subtract return; } int mid = (start + end) / 2; if (idx <= mid) update(node * 2, start, mid, idx, val_cnt, val_amount); else update(node * 2 + 1, mid + 1, end, idx, val_cnt, val_amount); seg_count[node] = seg_count[node * 2] + seg_count[node * 2 + 1]; seg_sum[node] = seg_sum[node * 2] + seg_sum[node * 2 + 1]; } // Query the sum of the k largest values in the segment tree long long query(int node, int start, int end, int k) { if (k <= 0) return 0; if (seg_count[node] <= k) return seg_sum[node]; // Take everything if (start == end) { // We are at a leaf, we need 'k' items from here. // The value at this leaf is seg_sum[node] / seg_count[node] (conceptually) // Since all items at a leaf are identical in compressed value: long long single_val = seg_sum[node] / seg_count[node]; return single_val * k; } int mid = (start + end) / 2; // Right child has larger values (since we compressed V such that larger index = larger V) if (seg_count[node * 2 + 1] >= k) { return query(node * 2 + 1, mid + 1, end, k); } else { return seg_sum[node * 2 + 1] + query(node * 2, start, mid, k - seg_count[node * 2 + 1]); } } // Global pointers for the current range covered by the segment tree int cur_L = 1; int cur_R = 0; // Function to move the segment tree range to [L, R] void move_range(int L, int R) { // Extend or shrink R while (cur_R < R) { cur_R++; // Identify the rank of the V value at cur_R int rank = lower_bound(v_coords.begin(), v_coords.end(), pieces[cur_R].v) - v_coords.begin(); update(1, 0, N - 1, rank, 1, pieces[cur_R].v); } while (cur_R > R) { int rank = lower_bound(v_coords.begin(), v_coords.end(), pieces[cur_R].v) - v_coords.begin(); update(1, 0, N - 1, rank, -1, -pieces[cur_R].v); cur_R--; } // Extend or shrink L while (cur_L > L) { cur_L--; int rank = lower_bound(v_coords.begin(), v_coords.end(), pieces[cur_L].v) - v_coords.begin(); update(1, 0, N - 1, rank, 1, pieces[cur_L].v); } while (cur_L < L) { int rank = lower_bound(v_coords.begin(), v_coords.end(), pieces[cur_L].v) - v_coords.begin(); update(1, 0, N - 1, rank, -1, -pieces[cur_L].v); cur_L++; } } long long max_beauty = -2e18; // Initialize with a very small number // Divide and Conquer function // Computes the optimal j for each i in [i_start, i_end], knowing optimal j is in [j_start, j_end] void solve(int i_start, int i_end, int j_start, int j_end) { if (i_start > i_end) return; int i_mid = (i_start + i_end) / 2; int best_j = -1; long long current_max = -4e18; // We need to iterate j from max(j_start, i_mid + M - 1) to j_end int start_scan = max(j_start, i_mid + M - 1); // Evaluate for i_mid // We iterate j and find the best one for this specific i_mid for (int j = start_scan; j <= j_end; ++j) { move_range(i_mid, j); // Adjust seg tree to [i_mid, j] long long sum_top_m = query(1, 0, N - 1, M); long long beauty = sum_top_m - 2 * (pieces[j].c - pieces[i_mid].c); if (beauty > current_max) { current_max = beauty; best_j = j; } } if (best_j != -1) { max_beauty = max(max_beauty, current_max); } else { // If no valid j found (e.g. range too small), we still need a valid best_j for recursion bounds. // Logic suggests best_j should be at least start_scan. best_j = j_start; } // Recursive calls // For i < i_mid, optimal j is <= best_j solve(i_start, i_mid - 1, j_start, best_j); // For i > i_mid, optimal j is >= best_j solve(i_mid + 1, i_end, best_j, j_end); } int main() { // Fast I/O ios_base::sync_with_stdio(false); cin.tie(NULL); if (!(cin >> N >> M)) return 0; pieces.resize(N + 1); // 1-based indexing for convenience in logic for (int i = 1; i <= N; ++i) { cin >> pieces[i].v >> pieces[i].c; v_coords.push_back(pieces[i].v); } // 1. Sort pieces by Color C sort(pieces.begin() + 1, pieces.end(), [](const Piece& a, const Piece& b) { return a.c < b.c; }); // 2. Coordinate Compression for V values sort(v_coords.begin(), v_coords.end()); v_coords.erase(unique(v_coords.begin(), v_coords.end()), v_coords.end()); // 3. Divide and Conquer // i can range from 1 to N - M + 1 // j can range from M to N // We initialize pointers for seg tree logic cur_L = 1; cur_R = 0; solve(1, N - M + 1, M, N); cout << max_beauty << endl; return 0; }