Submission #1251624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251624		apxo	Sails (IOI07_sails)	C++20	100 / 100	68 ms	1860 KiB

sails

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
int n;
pair<int, int> a[maxn];
long long bit[maxn];
int cnt[maxn];

void update(int i, int x) {
  for (; i < maxn; i += i & (-i)) {
    bit[i] += x;
  }
}

int get(int i) {
  long long ans = 0;
  for (; i > 0; i -= i & (-i)) {
    ans += bit[i];
  }
  return ans;
}

void upd(int l, int r) {
  if (l > r) return;
  update(l, 1);
  update(r + 1, -1);
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i].first >> a[i].second;
  }
  sort(a + 1, a + n + 1);
  int lim = 0;
  for (int i = 1; i <= n; ++i) {
    if (lim + a[i].second <= a[i].first) {
      upd(lim + 1, lim + a[i].second);
      lim += a[i].second;
      continue;
    }
    if (lim < a[i].first) {
      a[i].second -= a[i].first - lim;
      upd(lim + 1, a[i].first);
    }
    int deg = get(lim - a[i].second + 1);
    int l = 1, r = lim, pl = -1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (get(mid) >= deg) {
        pl = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    l = 1, r = lim;
    int pr = -1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (get(mid) <= deg) {
        pr = mid;
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    upd(pl + 1, lim);
    a[i].second -= lim - pl;
//    debug(i, lim, pl, pr, deg, a[i]);
    upd(pr, pr + a[i].second - 1);
    lim = a[i].first;
  } 
  long long res = 0;
  for (int i = 1; i <= lim; ++i) {
    int x = get(i);
    res += 1ll * x * (x - 1) / 2;
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10