Submission #1136664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136664		LinkedArray	Sails (IOI07_sails)	C++20	100 / 100	70 ms	3400 KiB

sails

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

using ll = long long;
#define pb push_back
#define int ll

const int NUM_ROWS = 1e5;

vector<int> aib(NUM_ROWS + 1);
vector<int> row_ids(NUM_ROWS + 1);
vector<pair<int, int>> rows;

int query (int k) {
  int ans = 0;
  while (k >= 1) {
    ans += aib[k];
    k -= (k & (-k));
  }
  return ans;
}

void update (int k, int val) {
  while (k <= NUM_ROWS) {
    aib[k] += val;
    k += (k & (-k));
  }
}

void range_update (int l, int r, int val) {
  update(l, +val);
  update(r + 1, -val);
}

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

  int n, i, h, k, delta, num_delta, lb_pos, ub_pos, ans;

  cin >> n;

  for (i = 0; i <= NUM_ROWS; i++) {
    row_ids[i] = i;
  }

  rows = vector<pair<int, int>>(n + 1);
  for (i = 1; i <= n; i++) {
    cin >> rows[i].first >> rows[i].second;
  }
  sort(rows.begin() + 1, rows.end());
  for (i = 1; i <= n; i++) {
    h = rows[i].first;
    k = rows[i].second;
    delta = h - k + 1;
    num_delta = query(delta);

    auto it_lb =
        lower_bound(row_ids.begin() + 1, row_ids.begin() + h + 1, num_delta,
                    [] (int mij, int val) { return query(mij) > val; });
    lb_pos = it_lb - row_ids.begin();

    auto it_ub =
        upper_bound(row_ids.begin() + 1, row_ids.begin() + h + 1, num_delta,
                    [] (int val, int mij) { return query(mij) < val; });
    ub_pos = it_ub - 1 - row_ids.begin();

    range_update(lb_pos, lb_pos + ub_pos - delta, 1);
    range_update(ub_pos + 1, h, 1);
  }
  ans = 0;
  for (i = 1; i <= NUM_ROWS; i++) {
    num_delta = query(i);
    ans += num_delta * (num_delta - 1) / 2;
  }
  cout << ans << "\n";
  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