Submission #1061476

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;

#define INF 1145141919

typedef pair<int, int> P;
typedef pair<int, P> P2;
int N, L;
int A[100000], B[100000];

int d(int a, int b) {
  if (a > b) swap(a, b);
  return min(abs(A[b] - A[a]), abs(A[a]+L - A[b]));
}

int main() {
  cin >> N >> L;
  for (int i=0; i<N; i++) {
    int b, c;
    cin >> A[i] >> b >> c;
    B[i] = c-b;
  }
  priority_queue<P2, vector<P2>, greater<P2> > q;
  for (int i=0; i<N; i++) {
    if (B[i] > 0) {
      int l = (i-1+N)%N, r = (i+1)%N;
      while (B[l] >= 0) l = (l-1+N)%N;
      while (B[r] >= 0) r = (r+1)%N;
      q.push(P2(d(i, l), P(i, l)));
      q.push(P2(d(i, r), P(i, r)));
    }
  }

  long long m = 0;
  while (!q.empty()) {
    P2 x = q.top(); q.pop();
    int i = x.second.first, sb = x.second.second;
    int g = min(B[i], -B[sb]);
    m += (long long)d(i, sb) * (long long)g;
    B[i] -= g, B[sb] += g;

    if (B[i] > 0) {
      int l = (i-1+N)%N, r = (i+1)%N;
      while (B[l] >= 0) l = (l-1+N)%N;
      while (B[r] >= 0) r = (r+1)%N;
      q.push(P2(d(i, l), P(i, l)));
      q.push(P2(d(i, r), P(i, r)));
    }
  }
  cout << m << "\n";
  return 0;
}

Submission Info

Judge Result