제출 #1127692

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127692		zNatsumi	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	550 ms	32620 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
using ii = pair<int, int>;

const int N = 5e5 + 5;
const long long INF = 1e16;

int n, x[N], e[N];

struct SegTree{
  ii st[N << 2];

  ii Merge(ii x, ii y){ return make_pair(max(x.first, y.first), min(x.second, y.second)); }

  void build(int tl, int tr, int i){
    if(tl == tr){
      st[i] = {-INF, INF};
      return;
    }
    int tm = tl + tr >> 1;
    build(tl, tm, i<<1);
    build(tm + 1, tr, i<<1|1);
    st[i] = Merge(st[i<<1], st[i<<1|1]);
  }
  void update(int pos, ii x, int tl, int tr, int i){
    if(tl == tr){
      st[i] = Merge(st[i], x);
      return;
    }
    int tm = tl + tr >> 1;
    if(pos <= tm) update(pos, x, tl, tm, i<<1);
    else update(pos, x, tm + 1, tr, i<<1|1);
    st[i] = Merge(st[i<<1], st[i<<1|1]);
  }
  ii get(int l, int r, int tl, int tr, int i){
    if(r < tl || tr < l || l > r) return make_pair(-INF, INF);
    if(l <= tl && tr <= r) return st[i];
    int tm = tl + tr >> 1;
    return Merge(get(l, r, tl, tm, i<<1), get(l, r, tm + 1, tr, i<<1|1));
  }
} it;

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> x[i] >> e[i];

  vector<int> order(n), rrh;
  iota(order.begin(), order.end(), 1);
  sort(order.begin(), order.end(), [&](int i, int j){ return e[i] > e[j]; });

  for(int i = 1; i <= n; i++) rrh.push_back(x[i]);
  sort(rrh.begin(), rrh.end());
  rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end());

  int res = 0, lim = rrh.size();
  auto id = [&](int x)->int{
    return lower_bound(rrh.begin(), rrh.end(), x) - rrh.begin() + 1;
  };

  it.build(1, lim, 1);
  for(auto i : order){
    int pos = id(x[i]);

    if(it.get(1, pos, 1, lim, 1).first >= x[i] + e[i]) continue;
    if(it.get(pos, lim, 1, lim, 1).second <= x[i] - e[i]) continue;

    res += 1;
    it.update(pos, make_pair(x[i] + e[i], x[i] - e[i]), 1, lim, 1);
  }
  cout << res << "\n";

  return 0;
}

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