QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#629144 | #4219. Insects | nhuang685 | RE | 0ms | 0kb | C++23 | 11.2kb | 2024-10-11 06:14:50 | 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