记录

Code:

#include <algorithm>
#include <iostream>

using namespace std;
using ll = long int;

const int kMaxN = 1e5 + 1;

int n;
ll ans, dis[kMaxN], maxn[kMaxN], summ[kMaxN], mul[kMaxN];
struct Cow {
  ll v, x;
} a[kMaxN];

ll Dis(int l, int r) {
  return abs(a[r].x - a[l].x);
}

void Solve(int l, int r) {
  if (l >= r) {
    return;
  }
  if (l == r - 1) {
    ans += Dis(l, r) * max(a[l].v, a[r].v);
    return;
  }
  int mid = (l + r) / 2;      
  Solve(l, mid), Solve(mid + 1, r);
  dis[mid] = maxn[mid] = summ[mid] = mul[mid] = 0ll;
  for (int i = mid + 1; i <= r; i++) {
    dis[i] = dis[i - 1] + Dis(mid, i);
    maxn[i] = max(maxn[i - 1], a[i].v);
    summ[i] = summ[i - 1] + maxn[i];
    mul[i] = mul[i - 1] + maxn[i] * Dis(mid, i);
  }
  for (int i = mid; i >= l; i--) {
  	int p = upper_bound(maxn + mid, maxn + r + 1, a[i].v) - maxn;
    ans += (Dis(i, mid) * (p - mid - 1) + dis[p - 1]) * a[i].v;
    ans += mul[r] - mul[p - 1] + Dis(i, mid) * (summ[r] - summ[p - 1]);
  }
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].v >> a[i].x;
  }
  sort(a + 1, a + n + 1, [](Cow i, Cow j) { return i.x < j.x; });
  Solve(1, n);
  cout << ans << '\n';
  return 0;
}