제출 #1036926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036926		juicy	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	676 ms	58968 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 5e5 + 5, inf = 1e9;
 
int n;
int a[N], b[N];
set<array<int, 2>> A, B;
 
int get(const set<array<int, 2>> &st, int x) {
  return (*prev(st.lower_bound(array<int, 2>{x + 1, -2 * inf})))[1];
}
 
void add(set<array<int, 2>> &st, array<int, 2> x) {
  for (auto it = st.lower_bound(array<int, 2>{x[0]}); it != st.end(); it = st.erase(it)) {
    if (x[1] < (*it)[1]) {
      break;
    }
  }
  st.insert(x);
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
  }  
  vector<int> ord(n); iota(ord.begin(), ord.end(), 1);
  sort(ord.begin(), ord.end(), [&](int u, int v) {
    return b[u] > b[v];
  });
  A.insert({0, -2 * inf}), B.insert({0, -2 * inf});
  int res = 0;
  for (int x : ord) {
    if (get(A, a[x]) < a[x] + b[x] && get(B, inf - a[x] + 1) < b[x] - a[x]) {
      ++res;
      add(A, {a[x], a[x] + b[x]});
      add(B, {inf - a[x] + 1, b[x] - a[x]});
    }
  }
  cout << res;
  return 0;
}

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