Submission #76663437

---

Source Code Expand

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

typedef long long ll;

constexpr int mx_n = 2 * 100005;
constexpr int mx_t = 1000006;
int n, d;
int s[mx_n], t[mx_n];
vector<int> enter_at[mx_t], leave_at[mx_t];

void solve() {
#ifdef GEN_TEST
  n = 5;
  d = 2;
  for(int i = 0; i < n; ++i) {
    s[i] = rand() % 10 + 1;
    t[i] = rand() % (11 - s[i] + 1) + s[i];
  }
  cout << n << " " << d << endl;
  for(int i = 0; i < n; ++i) {
    cout << s[i] << " " << t[i] << endl;
  }
#else
  cin >> n >> d;
  for(int i = 0; i < n; ++i) {
    cin >> s[i] >> t[i];
  }
#endif

  for(int i = 0; i < n; ++i) {
    enter_at[s[i]].push_back(i);
    leave_at[t[i]].push_back(i);
  }
  ll ans = 0;
  multiset<int> valid; // has s[i] for s[i] <= t-d;
  multiset<int> future; // has s[i] for s[i] > t-d;

  for(int t = 0; t < mx_t; ++t) {
    for(int i: enter_at[t]) {
      future.insert(s[i]);
    }
    while(future.size() > 0 && *future.begin() <= t-d) {
      valid.insert(*future.begin());
      future.erase(future.begin());
    }
    int tot = valid.size();
    ans += 1ll * tot * (tot-1) / 2;
    for(int i: leave_at[t]) {
      if(s[i] <= t-d) {
        valid.erase(valid.find(s[i]));
      } else {
        future.erase(future.find(s[i]));
      }
    }

  }

  cout << ans << endl;

}

void brute() {
  ll ans = 0;
  for(int i = 0; i < n; ++i) {
    for(int j = i+1; j < n; ++j) {
      int from = max(s[i], s[j]);
      int to = min(t[i], t[j]);
      if(from <= to) {
        ans += max(0, (to-from)-d+1);
      }
    }
  }

  cout << "BRUTE: " << ans << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t = 1;
  // cin >> t;
  while(t--) {
    solve();
    #ifndef ONLINE_JUDGE
      brute();
    #endif
  }

  return 0;
}

Submission Info

Judge Result