Submission #792116

#	Time	Username	Problem	Language	Result	Execution time	Memory
792116		WLZ	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	886 ms	101980 KiB

Main

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

#ifdef DEBUG
#include "templates/debug.h"
#else
#define debug(...) 0
#endif

#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define eb emplace_back
#define pb push_back
#define mt make_tuple
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int) x.size()

using ll = long long;
using ull = unsigned ll;
using lll = __int128_t;
using ulll = __uint128_t;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
template<typename T> using mx_pq = priority_queue<T>;
template<typename T> using mn_pq = priority_queue<T, vector<T>, greater<T>>;

template<typename T> void cmax(T &a, const T &b) { a = max(a, b); }
template<typename T> void cmin(T &a, const T &b) { a = min(a, b); }

const int INF = 0x3f3f3f3f;
const ll LINF = (ll) 1e18;
const double DINF = 1.0 / 0.0;
const double pi = acos(-1);
const double EPS = 1e-9;

void solve(int current_case);

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  //cin >> t;
  for (int q = 1; q <= t; q++) solve(q);
  return 0;
}

ii swapped(const ii &p) {
  return {p.second, p.first};
}

void solve(int current_case) {
  int n; cin >> n;
  vi x(n), e(n);
  vii v(n);
  rep(i, 0, n) cin >> x[i] >> e[i], v[i] = {e[i], x[i]};
  sort(v.rbegin(), v.rend());
  set<ii> st_l, st_r_2, st_r;
  set<ii, greater<> > st_l_2;
  int ans = 0;
  for (auto &p : v) {
    ii pl = make_pair(p.first - p.second, p.second), pr = make_pair(p.first + p.second, p.second);
    auto it_l = st_l.lower_bound({p.first - p.second, -INF}), it_r = st_r.lower_bound({p.first + p.second, -INF});
    if ((it_l != st_l.end() && it_l->second >= p.second) || (it_r != st_r.end() && it_r->second <= p.second)) continue;
    ans++;
    //debug(p);
    pl = swapped(pl), pr = swapped(pr);
    it_l = st_l_2.lower_bound(pl), it_r = st_r_2.lower_bound(pr);
    while (it_l != st_l_2.end() && it_l->second <= pl.second) {
      st_l.erase(swapped(*it_l));
      it_l = st_l_2.erase(it_l);
    }
    while (it_r != st_r_2.end() && it_r->second <= pr.second) {
      st_r.erase(swapped(*it_r));
      it_r = st_r_2.erase(it_r);
    }
    st_l_2.insert(pl); st_r_2.insert(pr);
    st_l.insert(swapped(pl)); st_r.insert(swapped(pr));
  }
  cout << ans << '\n';
}

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