Submission #807713

#	Time	Username	Problem	Language	Result	Execution time	Memory
807713		dong_liu	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	281 ms	36472 KiB

Main

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

typedef pair<int, int> pi;

struct node {
  pi mx_e{0, -1};
  int case1 = INT_MAX, case2 = INT_MAX;

  node operator+(const node &o) {
    return {max(mx_e, o.mx_e), min(case1, o.case1), min(case2, o.case2)};
  }
};

vector<node> st;
int n_;

void rm_right(vector<int> &v, int i, int ex) {
  if (st[i].case1 <= ex) {
    if (i >= n_)
      v.push_back(i - n_);
    else {
      rm_right(v, i * 2, ex);
      rm_right(v, i * 2 + 1, ex);
    }
  }
}

vector<int> rm_right(int l, int r, int ex) {
  vector<int> v;
  for (l += n_, r += n_; l <= r; l /= 2, r /= 2) {
    if (l & 1) rm_right(v, l++, ex);
    if (~r & 1) rm_right(v, r--, ex);
  }
  return v;
}

void rm_left(vector<int> &v, int i, int ex) {
  if (st[i].case2 <= ex) {
    if (i >= n_)
      v.push_back(i - n_);
    else {
      rm_left(v, i * 2, ex);
      rm_left(v, i * 2 + 1, ex);
    }
  }
}

vector<int> rm_left(int l, int r, int ex) {
  vector<int> v;
  for (l += n_, r += n_; l <= r; l /= 2, r /= 2) {
    if (l & 1) rm_left(v, l++, ex);
    if (~r & 1) rm_left(v, r--, ex);
  }
  return v;
}

void rem(int i) {
  st[i += n_] = node();
  while (i >>= 1) st[i] = st[i * 2] + st[i * 2 + 1];
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n;
  vector<pair<int, int>> v(n);
  for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
  sort(v.begin(), v.end());
  vector<int> x(n), e(n);
  for (int i = 0; i < n; i++) tie(x[i], e[i]) = v[i];
  n_ = 1;
  while (n_ < n) n_ *= 2;
  st = vector<node>(n_ * 2);
  for (int i = 0; i < n; i++) {
    st[n_ + i].mx_e = {e[i], i};
    st[n_ + i].case1 = e[i] + x[i];
    st[n_ + i].case2 = e[i] - x[i];
  }
  for (int i = n_ - 1; i > 0; i--) st[i] = st[i * 2] + st[i * 2 + 1];
  int cnt = 0;
  while (~st[1].mx_e.second) {
    int i = st[1].mx_e.second;
    cnt++;
    for (int j : rm_right(i, n - 1, e[i] + x[i])) {
      rem(j);
    }
    for (int j : rm_left(0, i, e[i] - x[i])) {
      rem(j);
    }
  }
  cout << cnt << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31