Submission #291424

#	Time	Username	Problem	Language	Result	Execution time	Memory
291424		rama_pang	Arranging Tickets (JOI17_arranging_tickets)	C++14	100 / 100	2168 ms	15832 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;

// Solution:
// We can binary search the answer. We also break the circle to
// a line segment.
//
// If intervals [a, b] and [c, d] is reversed, and a < b < c < d,
// then we originally have interval values:
// ([1, a), 0), ([a, b], 1), ((b, c), 0), ([c, d], 1), ((d, N], 0)
// and reversed values are:
// ([1, a), 2), ([a, b], 1), ((b, c), 2), ([c, d], 1), ((d, N], 2)
// We can see that all regions increased - thus all flipped intervals
// must share a point t.
//
// For a fixed point t, let a[i] be the sum of people travelling through i,
// and b[i] be the final one once we reversed optimally. Then b[t] = max(b[i])
// or b[t] = max(b[i]) - 1. This allows us to check only a[t] - max_ans and
// a[t] - max_ans + 1 flips for a point t, where max_ans is the current
// mid in the binary search. Proof follows.
//
// Assume then b[t] < max(b[i]) - 1. Then we can find two reversed segments [a, b] and
// [c, d], such that a is the minimum coordinate of reversed segment and d is the
// maximum one of reversed segments. By definition, [a, b] and [c, d] passes through t, 
// and we can unreverse them. This will not change max(b[i]), and increment b[t] by either
// 1 or 2. Thus we can keep doing this until the condition is satisfied without breaking
// the solution.
//
// This yields an O(M^2 log^2 M) solution. We can further speed this up by noticing that
// we only need to check t where a[t] = max(a[i]) and t is the minimum and maximum i that
// is equal max(a[i]). Why? Since b[i] - a[i] is smaller the closer i is to t, let j not be
// in the common interval of all reversed intervals. Then b[t] - a[t] + 1 <= b[j] - a[j].
// If we assume a[t] + 1 <= a[j], we can sum them to get b[t] + 2 <= b[j]. But by definition
// b[t] = max(b[i]) or b[t] = max(b[i]) - 1, thus we get a contradiction. Therefore, a[t] = 
// max(a[i]) must be satisfied.
//
// Now we prove the second condition (only checking the leftmost and rightmost t such that a[t] =
// max(a[i])). First, there is no reversed interval [x, y], such that l < x < y < r. Assume otherwise.
// Then, when we reverse [x, y], let b' be the resulting arrangement. We have b'[t] = b[t] + 1
// and b'[l] = b[l] - 1, and b'[l] >= b'[t] since we use t = l. Then we get b[l] >= b[t] + 2 which
// is a contradiction since b[t] = max(b[i]) or b[t] = max(b[i]) - 1. Thus no such [x, y] exist, which
// means we only need to consider t = l or t = r.
//
// After we determine max_ans and t, we can do the reversal greedily. We can use a segment tree or a
// priority queue to support the operations: point update += x at position i and remove x items from 
// the right to simulate the greedy selection. We check after we do all flips to see if we satisfy
// everything.
//
// Time: O(N log^2 N)

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, M;
  cin >> N >> M;

  vector<int> A(M), B(M), C(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i] >> C[i];
    A[i]--, B[i]--;
    if (A[i] > B[i]) {
      swap(A[i], B[i]);
    }
  }

  vector<long long> sum(N);
  vector<vector<pair<int, int>>> segs(N);
  for (int i = 0; i < M; i++) {
    sum[A[i]] += C[i];
    sum[B[i]] -= C[i];
    segs[A[i]].emplace_back(B[i], C[i]);
  }
  for (int i = 1; i < N; i++) {
    sum[i] += sum[i - 1];
  }

  long long mx = *max_element(begin(sum), end(sum));
  int ll = -1, rr = -1;
  for (int i = 0; i < N; i++) {
    if (sum[i] == mx) {
      ll = i;
      break;
    }
  }
  for (int i = N - 1; i >= 0; i--) {
    if (sum[i] == mx) {
      rr = i;
      break;
    }
  }

  auto Check = [&](int t, long long mx, long long flips) -> bool {
    vector<long long> upd_sum(N);
    for (int i = 1; i < N; i++) {
      upd_sum[i] += upd_sum[i - 1];
    }
    long long flipped = 0;
    priority_queue<array<int, 3>> pq;
    for (int pos = 0; pos <= t; pos++) {
      for (auto i : segs[pos]) {
        if (i.first > t) {
          pq.push({i.first, pos, i.second});
        }
      }
      // Look at effects to upd_sum for derivation, sum[pos] += 2 * constant
      long long need = (sum[pos] - mx + flips + 1) / 2; 
      if (pos == t) need = flips;
      need = max(need - flipped, 0ll);
      flipped += need;
      while (need > 0) {
        if (pq.empty()) {
          return false;
        }
        auto arr = pq.top(); pq.pop();
        long long del = min(need, 1ll * arr[2]);
        arr[2] -= del, need -= del;
        if (arr[2] > 0) {
          pq.push(arr);
        }
        // Add [0, A) and [B, N)
        upd_sum[0] += del;
        upd_sum[arr[1]] -=  del;
        upd_sum[arr[0]] +=  del;
        // Undo [A, B)
        upd_sum[arr[1]] -= del;
        upd_sum[arr[0]] += del;
      }
    }

    for (int i = 0; i < N; i++) {
      if (i > 0) {
        upd_sum[i] += upd_sum[i - 1];
      }
      if (sum[i] + upd_sum[i] > mx) {
        return false;
      }
    }
    return true;
  };

  auto CheckAll = [&](long long m) -> bool {
    return Check(ll, m, sum[ll] - m + 0) ||
           Check(ll, m, sum[ll] - m + 1) ||
           Check(rr, m, sum[rr] - m + 0) ||
           Check(rr, m, sum[rr] - m + 1);
  };

  long long lo = 0, hi = mx;
  while (lo < hi) {
    long long md = (lo + hi) / 2;
    if (CheckAll(md)) {
      hi = md;
    } else {
      lo = md + 1;
    }
  }

  cout << lo << "\n";
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 35 / 35
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 15 / 15