QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#629144#4219. Insectsnhuang685RE 0ms0kbC++2311.2kb2024-10-11 06:14:502024-10-11 06:14:50

Judging History

你现在查看的是最新测评结果

  • [2024-10-11 06:14:50]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-11 06:14:50]
  • 提交

answer

/**
 * @author n685
 * @brief
 * @date 2024-10-09 17:44:17
 *
 *
 */
#pragma GCC optimize("O3,unroll-loops")
#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

namespace rs = std::ranges;
namespace rv = std::views;

template <class T> constexpr T INF = T{};
template <std::floating_point T>
constexpr T INF<T> = std::numeric_limits<T>::infinity();
template <> constexpr int INF<int> = 0x3f3f3f3f; // 1061109567
template <>
constexpr int64_t INF<int64_t> = 0x3f3f3f3f3f3f3f3f; // 4557430888798830399

template <class T> struct CC {
  std::vector<T> val;
  void insert(T a) { val.push_back(a); }
  void init() {
    std::sort(val.begin(), val.end());
    val.erase(std::unique(val.begin(), val.end()), val.end());
  }
  int operator[](T a) const {
    return static_cast<int>(
      std::distance(val.begin(), std::lower_bound(val.begin(), val.end(), a))
    );
  }
  int size() const { return static_cast<int>(val.size()); }
};

template <class Node>
concept PSegNode = requires(Node n, Node& node, int k) {
  requires std::same_as<std::decay_t<decltype(n.ch)>, std::array<int, 2>>;
  typename Node::Index;
  typename Node::Output;
  requires std::integral<typename Node::Index>;
  Node();
  requires std::
    same_as<std::decay_t<decltype(Node::ID)>, typename Node::Output>;
  {
    std::as_const(n).value()
  } -> std::same_as<typename Node::Output>;
  {
    Node::comb(Node::ID, Node::ID)
  } -> std::same_as<typename Node::Output>;
  Node();
  {
    n.reset_value()
  } -> std::same_as<void>;
  {
    n.pull(n)
  } -> std::same_as<void>;
  {
    n.need_push()
  } -> std::same_as<bool>;
  {
    n.push(node, node, k)
  } -> std::same_as<void>;
};
template <PSegNode Node> struct PSeg {
  using Index = Node::Index;
  using Output = Node::Output;
  std::vector<Node> data;
  int new_node() {
    data.emplace_back();
    return static_cast<int>(data.size()) - 1;
  }
  int copy_node(Node n) {
    data.push_back(std::move(n));
    return static_cast<int>(data.size()) - 1;
  }
  void copy_ch(int par, int ch) {
    int ind
      = data[par].ch[ch] == -1 ? new_node() : copy_node(data[data[par].ch[ch]]);
    data[par].ch[ch] = ind;
  }

  Index sz{};
  std::vector<int> rts;
  void new_rt(int rt) { rts[rt] = new_node(); }
  int new_rt() {
    rts.push_back(new_node());
    return static_cast<int>(rts.size()) - 1;
  }
  void copy_rt(int rt, int dest) { rts[dest] = copy_node(data[rts[rt]]); }
  int copy_rt(int rt) {
    rts.push_back(copy_node(data[rts[rt]]));
    return static_cast<int>(rts.size()) - 1;
  }
  int copy_rt() { return copy_rt(static_cast<int>(rts.size()) - 1); }

  PSeg() = default;
  explicit PSeg(Index sz_, int nrts = 0)
      : sz(static_cast<Index>(std::bit_ceil<std::make_unsigned_t<Index>>(sz_))),
        rts(nrts, -1) {}

  void pull(int node) {
    data[node].reset_value();
    if (data[node].ch[0] != -1) {
      data[node].pull(data[data[node].ch[0]]);
    }
    if (data[node].ch[1] != -1) {
      data[node].pull(data[data[node].ch[1]]);
    }
  }
  void push(int node, Index k) {
    data[node].push(data[data[node].ch[0]], data[data[node].ch[1]], k);
  }

  template <class F, class... Args>
    requires std::invocable<F, Node&, const Args&..., Index>
  void upd_i(
    const F& f,
    Index l,
    Index r,
    int node,
    Index ll,
    Index rr,
    const Args&... args
  ) {
    if (l <= ll && rr <= r) {
      std::invoke(f, data[node], args..., rr - ll + 1);
      return;
    }
    Index mid = (ll + rr) / 2;
    bool np = data[node].need_push();
    if (np || l <= mid) {
      copy_ch(node, 0);
    }
    if (np || r > mid) {
      copy_ch(node, 1);
    }
    if (np) {
      push(node, rr - ll + 1);
    }
    if (l <= mid) {
      upd_i(f, l, r, data[node].ch[0], ll, mid, args...);
    }
    if (r > mid) {
      upd_i(f, l, r, data[node].ch[1], mid + 1, rr, args...);
    }
    pull(node);
  }
  template <class F, class... Args>
  void upd(const F& f, int rt, Index l, Index r, const Args&... args) {
    upd_i(f, l, r, rts[rt], 0, sz - 1, args...);
  }
  template <class F, class... Args>
  void upd_r(const F& f, Index l, Index r, const Args&... args) {
    upd_i(f, l, r, rts.back(), 0, sz - 1, args...);
  }
  Output query_i(Index l, Index r, int node, Index ll, Index rr) {
    if (l <= ll && rr <= r) {
      return data[node].value();
    }
    Index mid = (ll + rr) / 2;
    if (data[node].need_push()) {
      copy_ch(node, 0);
      copy_ch(node, 1);
      push(node, rr - ll + 1);
    }
    Output ans = Node::ID;
    if (l <= mid && data[node].ch[0] != -1) {
      ans = Node::comb(ans, query_i(l, r, data[node].ch[0], ll, mid));
    }
    if (r > mid && data[node].ch[1] != -1) {
      ans = Node::comb(ans, query_i(l, r, data[node].ch[1], mid + 1, rr));
    }
    return ans;
  }
  Output query(int rt, Index l, Index r) {
    return query_i(l, r, rts[rt], 0, sz - 1);
  }
  Output query_r(Index l, Index r) {
    return query_i(l, r, rts.back(), 0, sz - 1);
  }

  Index last_true_i(
    const std::function<bool(Output)>& f,
    int node,
    Index l,
    Index r,
    bool id
  ) {
    if (l == r) {
      if (f(data[node].value())) {
        return l;
      }
      return -1;
    }
    const Index mid = (l + r) / 2;
    if (data[node].need_push()) {
      copy_ch(node, 0);
      copy_ch(node, 1);
      push(node, r - l + 1);
    }
    if (data[node].ch[1] == -1) {
      if (id) {
        return r;
      }
    } else if (f(data[data[node].ch[1]].value())) {
      return last_true_i(f, data[node].ch[1], mid + 1, r, id);
    }
    if (data[node].ch[0] == -1) {
      if (id) {
        return mid;
      }
    } else if (f(data[data[node].ch[0]].value())) {
      return last_true_i(f, data[node].ch[0], l, mid, id);
    }
    return -1;
  }
  Index first_true_i(
    const std::function<bool(Output)>& f,
    int node,
    Index l,
    Index r,
    bool id
  ) {
    if (l == r) {
      if (f(data[node].value())) {
        return l;
      }
      return -1;
    }
    const Index mid = (l + r) / 2;
    if (data[node].need_push()) {
      copy_ch(node, 0);
      copy_ch(node, 1);
      push(node, r - l + 1);
    }
    if (data[node].ch[0] == -1) {
      if (id) {
        return l;
      }
    } else if (f(data[data[node].ch[0]].value())) {
      return first_true_i(f, data[node].ch[0], l, mid);
    }
    if (data[node].ch[1] == -1) {
      if (id) {
        return mid + 1;
      }
    } else if (f(data[data[node].ch[1]].value())) {
      return first_true_i(f, data[node].ch[1], mid + 1, r);
    }
    return -1;
  }
  Index last_true(const std::function<bool(Output)>& f, int rt) {
    return last_true_i(f, rts[rt], 0, sz - 1, f(Node::ID));
  }
  Index first_true(const std::function<bool(Output)>& f, int rt) {
    return first_true_i(f, rts[rt], 0, sz - 1, f(Node::ID));
  }
};

template <class T> struct Node {
  std::array<int, 2> ch{-1, -1};
  using Index = int;
  using Output = T;
  static constexpr Output ID{0};

  T val{Node::ID};
  T la{0};
  Output value() const { return val; }
  static Output comb(Output lhs, Output rhs) { return std::max(lhs, rhs); }
  Node() = default;

  void reset_value() { val = T{0}; }
  void pull(Node& node) { val = std::max(val, node.val); }
  bool need_push() { return la != T{0}; }
  void push(Node& lch, Node& rch, Index k) {
    lch.add(la, k);
    rch.add(la, k);
    la = T{0};
  }

  void add(T v, Index /*k*/) {
    val += v;
    la += v;
  }
};

struct Point {
  int ia, ib;
  int a, b;
};

constexpr int MX = 100000;
std::array<std::array<Point, MX>, 2> p;

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  std::freopen("log.txt", "r", stdin);
  std::freopen("correct.txt", "w", stdout);

  start_clock();
  int n;
  std::cin >> n;
  // std::array<std::vector<Point>, 2> p;
  // p[0].reserve(n);
  for (int i = 0; i < n; ++i) {
    int a, b;
    std::cin >> a >> b;
    p[0][i] = {.ia = a, .ib = b, .a = -1, .b = -1};
  }
  int m;
  std::cin >> m;
  // p[1].reserve(m);
  for (int i = 0; i < m; ++i) {
    int x, y;
    std::cin >> x >> y;
    p[1][i] = {.ia = x, .ib = y, .a = -1, .b = -1};
  }
  auto dq = [&](
              auto& self,
              int l,
              int r,
              std::array<std::vector<int>, 2>& cur,
              int add = 0
            ) -> void {
    int mid = (l + r) / 2;
    std::array<std::array<std::vector<int>, 2>, 2> gr;
    for (int i : cur[1]) {
      if (i > mid) {
        gr[1][1].push_back(i);
      }
    }
    std::erase_if(cur[1], [mid](int i) { return i > mid; });
    std::vector<std::vector<std::pair<int, int>>> loc;
    int sx, sy;
    {
      CC<int> cx, cy;
      cx.val.reserve(cur[0].size() + cur[1].size());
      for (int i : {0, 1}) {
        for (int j : cur[i]) {
          cx.insert(p[i][j].ia);
          cy.insert(p[i][j].ib);
        }
      }
      cx.init();
      cy.init();
      sx = cx.size(), sy = cy.size();
      loc.resize(sx);
      for (int i : {0, 1}) {
        for (int j : cur[i]) {
          p[i][j].a = cx[p[i][j].ia];
          p[i][j].b = cy[p[i][j].ib];
          loc[p[i][j].a].emplace_back(j, i);
        }
      }
    }

    int al = 0, ar = 0;
    {
      PSeg<Node<int64_t>> dp(sy + 1);
      dp.data.reserve(80 * (std::ssize(cur[0]) + std::ssize(cur[1])));
      dp.rts.reserve(sx);
      for (int i = 0; i < sx; ++i) {
        if (i == 0) {
          dp.new_rt();
        } else {
          dp.copy_rt(i - 1);
        }
        for (auto [j, t] : loc[i]) {
          if (t == 1) {
            int64_t cv = dp.query(i, p[t][j].b + 1, p[t][j].b + 1);
            int ind
              = dp.last_true([&](int64_t val) { return val > cv; }, i) + 1;
            dp.upd(&Node<int64_t>::add, i, ind, sy, 1);
          } else {
            dp.upd(&Node<int64_t>::add, i, 0, p[t][j].b, 1);
          }
        }
      }
      std::vector<int> seq(sx + 1);
      seq[sx] = 0;
      for (int i = sx - 1; i >= 0; --i) {
        int64_t cv = dp.query(i, seq[i + 1], seq[i + 1]);
        int fi = dp.last_true([&](int64_t val) { return val >= cv; }, i);
        seq[i] = fi;
      }
      for (int i : cur[0]) {
        if (p[0][i].b >= seq[p[0][i].a]) {
          ++al;
          gr[1][0].push_back(i);
        } else {
          gr[0][0].push_back(i);
        }
      }
      for (int i : cur[1]) {
        if (p[1][i].b >= seq[p[1][i].a]) {
          gr[1][1].push_back(i);
        } else {
          ++ar;
          if (i <= mid) {
            gr[0][1].push_back(i);
          }
        }
      }
    }
    if (l == r) {
      std::cout << (n + l + 1) - (add + al + ar) << '\n';
      return;
    }
    self(self, l, mid, gr[0], add + al);
    self(self, mid + 1, r, gr[1], add + ar);
  };

  std::array<std::vector<int>, 2> a;
  a[0].resize(n);
  a[1].resize(m);
  std::iota(a[0].begin(), a[0].end(), 0);
  std::iota(a[1].begin(), a[1].end(), 0);
  dq(dq, 0, m - 1, a);
  end_clock();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

3
0 0
1 1
2 2
4
0 0
1 1
0 0
3 3

output:


result: