Submission #978250

#	Time	Username	Problem	Language	Result	Execution time	Memory
978250		asdfgrace	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	488 ms	24160 KiB

Main

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

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

/*
for any given pair it's ez to check
if you can create an edge between them
probably can calc contrib
this way you can quickly check like how many people you can donate this book to?
note that you can only donate to someone else if your e-value is greater than theirs
at the very least
2^n sub is ez
what about n^2 then
you get a dag with each edge existing if i can infl j
ans = # of nodes with indeg 0
basically for each node
can we just like check if its indeg is 0?
for (all nodes)
erase all nodes on LEFT with smaller e and larger dif
erase all nodes on RIGHT with smaller e and smaller sum
so if NO NODE on the RIGHT has a larger e and larger dif
and NO NODE on the LEFT has a larger e and smaller sum
this node is kept
Q: on the right, what is max dif for node w/ smaller e?

*/

const int inf = 2e9 + 5;

struct SegTree {
  int n;
  vector<int> st;
  
  SegTree (int x) {
    n = x;
    st.resize(2 * n, -inf);
  }
  
  void upd(int k, int x) {
    k += n;
    st[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
      st[k] = max(st[k * 2], st[k * 2 + 1]);
    }
  }
  
  int quer(int l, int r) {
    l += n; r += n;
    int ret = -inf;
    while (r >= l && l >= 1) {
      if (l % 2) ret = max(ret, st[l++]);
      if (r % 2 == 0) ret = max(ret, st[r--]);
      l /= 2; r /= 2;
    }
    return ret;
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  vector<array<int, 2>> xe(n);
  vector<int> evals;
  int mne = inf, mxe = -1;
  for (int i = 0; i < n; i++) {
    cin >> xe[i][0] >> xe[i][1];
    evals.push_back(xe[i][1]);
    mne = min(mne, xe[i][1]);
    mxe = max(mxe, xe[i][1]);
  }
  sort(xe.begin(), xe.end());
  int cx = -1, ce = -1;
  for (int i = n - 1; i >= 0; i--) {
    if (xe[i][0] != cx) {
      cx = xe[i][0];
      ce = xe[i][1];
    }
    xe[i] = {cx, ce};
  }
  auto it = unique(xe.begin(), xe.end());
  xe.erase(it, xe.end());
  sort(evals.begin(), evals.end());
  auto it2 = unique(evals.begin(), evals.end());
  evals.erase(it2, evals.end());
  int u = (int) evals.size();
  n = (int) xe.size();
  if (mne == mxe) {
    cout << n << '\n';
    return 0;
  }
  /*
  for this to work
  for some j < i, e[i] > e[j], dif[i] <= dif[j]
  so all k > i with e[k] > e[i] must have dif[i] > dif[k] or dif[k] < dif[i]
  max value of dif[k > i] must be less than dif[i]
  for some j > i, e[i] > e[j], sum[j] <= sum[i] for i to give j a book
  so for all k < i with e[k] > e[i], must have sum[i] <= sum[k] for k to give i a book
  so must have sum[i] > sum[k] for it to not work
  min value of sum[k < i] must be greater than sum[i]
  */
  
  SegTree rdif(u), lsum(u);
  vector<bool> ok(n, true);
  for (int i = 0; i < n; i++) {
    int pos = lower_bound(evals.begin(), evals.end(), xe[i][1]) - evals.begin();
    if (lsum.quer(pos, u - 1) >= xe[i][0] + xe[i][1]) ok[i] = false;
    lsum.upd(pos, xe[i][0] + xe[i][1]);
  }
  for (int i = n - 1; i >= 0; i--) {
    int pos = lower_bound(evals.begin(), evals.end(), xe[i][1]) - evals.begin();
    if (-rdif.quer(pos, u - 1) <= xe[i][0] - xe[i][1]) ok[i] = false;
    rdif.upd(pos, -xe[i][0] + xe[i][1]);
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (ok[i]) ans++;
  }
  cout << ans << '\n';
}

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