Submission #1177252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177252		JohnTitor	Two Antennas (JOI19_antennas)	C++20	35 / 100	3019 ms	33412 KiB

antennas

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

// each point has h[i] a[i] b[i]
// two points (i, j) can see each other if max(a[i], a[j]) <= abs(i - j) <= min(b[i], b[j])
// can try to break the abs and maybe do something with increasing b[i] or a[i], but a better way is to do this:
// - WLOG assume j < i
// - then for each j, the i it can reach form a continuous range
// - and for each i, the j it can reach also form a continuous range
// - so iterate over increasing i, and we turn on and off j as necessary
// - then for each i, we can get the answer of the relevant range and find out what is the max and min, from there find out the
// max diff
// - O(nlog(n)) in total assuming we use a segment tree to get min and max from a range
//
// this find the max over all doesn't help with the range queries, but we can use it it help with the range query using some
// sqrt trick:
// - pick block size K then the each query is split into blocks
// - the whole blocks and mixing with each other can be precalculated:
//   - there's O(n / K) such blocks and we can calculate the answer in n * O(n / K + K) total:
//     - for each element, iterate over its possible range, it can only contribute to some blocks
//     - for the whole blocks, we only need to get the max and min, so it's O(1)
//     - for the non whole block, just iterate over everything
// - for the remaining part, we can just iterate over the items and get in the range
// - which can be done as allocated offline query to each element
// - total should be K * q * complexity of the DS
//
//
//
//
// is there some 2d idea?
// - consider a square of [1, n] * [1, n]
// - for each query, we are effectively computing the max of the distance when paired inside [l, r] * [l, r]
// - |h[i] - h[j]| = max(h[i] - h[j], h[j] - h[i]) so instead of maximising the distance, we can maximise the signed distance
// - let the row i and column j cell to be h[i] - h[j]
// - if we choose every pairs then:
//   - just add h[i] to all the row
//   - just add -h[j] to all the column
//   - which is O(n) rectangle adds
// - then we can try to block the bad cell:
//   - for each i, there is at most 2 ranges where we can use i
//   - so we can filter out the ranges where we can pair i
//   - so add -inf to where we are not allowed to pair
// - then we have a 2d structures where to query [l, r], we need to get the max inside a square [l, r] * [l, r]
// - this is not really possible or it's very advanced
//   - quadtree can't handle the 1 x n rects well
//   - segment tree of segment trees can't really do the lazy update well

// shift the range into -5e8 5e8 to make the number works
constexpr int INF = 1e9;

int n;
constexpr int MAX_N = 2e5;
constexpr int BLOCK_SIZE = 256;
constexpr int BLOCK_COUNT = (MAX_N - 1) / BLOCK_SIZE + 1;
class point_t {
public:
    int h, a, b;
} p[MAX_N];
int pre_result[BLOCK_COUNT][BLOCK_COUNT];
vector<int> turn_on[MAX_N];
vector<int> turn_off[MAX_N];
multiset<int> block_set[BLOCK_COUNT];

int block_id(const int &i) { return i / BLOCK_SIZE; }
bool is_block_start(const int &i) { return i % BLOCK_SIZE == 0; }

void precalculate() {
    const int block_count = block_id(n - 1) + 1;
    // calculate where we need to turn on or off the left paired element
    for (int i = 0; i < n; i++) {
        int l = i + p[i].a;
        int r = i + p[i].b;
        if (l < n) turn_on[l].push_back(i);
        if (r + 1 < n) turn_off[r + 1].push_back(i);
    }

    // calculate the result
    for (int i = 0; i < block_count; i++)
        for (int j = i; j <= block_count; j++) pre_result[i][j] = -1;
    for (int i = 0; i < n; i++) {
        // first turn on and off the relevant items
        for (auto &&j : turn_off[i]) {
            auto &&s = block_set[block_id(j)];
            s.erase(s.find(p[j].h));
        }
        for (auto &&j : turn_on[i]) {
            auto &&s = block_set[block_id(j)];
            s.insert(p[j].h);
        }

        // then each block now have the elements that can see this elements
        const int b_id = block_id(i);
        // iterate over each elements this can see
        const int r = i - p[i].a;
        int l = max(0, i - p[i].b);
        while (l <= r) {
            if (is_block_start(l) && (block_id(l) != block_id(r))) {
                // can get the whole blocks
                const auto l_b_id = block_id(l);
                auto &&s = block_set[l_b_id];
                if (!s.empty()) {
                    auto &&result = pre_result[l_b_id][b_id];
                    auto &&block_max = *s.rbegin();
                    auto &&block_min = *s.begin();
                    result = max(result, max(block_max - p[i].h, p[i].h - block_min));
                }
                l += BLOCK_SIZE;
            } else {
                // can only get l
                if ((l + p[l].a <= i) && (l + p[l].b >= i)) {
                    const auto l_b_id = block_id(l);
                    auto &&result = pre_result[l_b_id][b_id];
                    result = max(result, abs(p[l].h - p[i].h));
                }
                l++;
            }
        }
    }
    // pre_result[a][b] now contains all the way to pair block a and block b
    // use dp to get it to contain all the result when pairing all the items
    for (int diff = 0; diff < block_count; diff++) {
        for (int l = 0; l + diff < block_count; l++) {
            int r = l + diff;
            if (r + 1 < n) pre_result[l][r + 1] = max(pre_result[l][r + 1], pre_result[l][r]);
            if (l > 0) pre_result[l - 1][r] = max(pre_result[l - 1][r], pre_result[l][r]);
        }
    }
}

class segment_tree_t {
public:
    pair<int, int> st[MAX_N * 4 + 1];
    int node_id[MAX_N];

    void build(int i, int l, int r) {
        st[i].first = INF;
        st[i].second = -INF;
        if (l == r) {
            node_id[l] = i;
        } else {
            int m = (l + r) / 2;
            build(i * 2, l, m);
            build(i * 2 + 1, m + 1, r);
        }
    }

    template <bool TURN_ON>
    void update(const int &u) {
        int i = node_id[u];
        if constexpr (TURN_ON) {
            st[i].first = st[i].second = p[u].h;
        } else {
            st[i].first = INF;
            st[i].second = -INF;
        }
        i /= 2;
        while (i) {
            st[i].first = min(st[i * 2].first, st[i * 2 + 1].first);
            st[i].second = max(st[i * 2].second, st[i * 2 + 1].second);
            i /= 2;
        }
    }
    pair<int, int> get(const int &i, const int &l, const int &r, const int &u, const int &v) {
        if (l > v || r < u) return {INF, -INF};
        if (u <= l && v >= r) return st[i];
        int m = (l + r) / 2;
        auto [left_min, left_max] = get(i * 2, l, m, u, v);
        auto [right_min, right_max] = get(i * 2 + 1, m + 1, r, u, v);
        return {min(left_min, right_min), max(left_max, right_max)};
    }
    pair<int, int> get(const int &u, const int &v) {
        if (u > v) return {INF, -INF};
        // it's possible to do this non recursive too but let's keep it simple
        return get(1, 0, n - 1, u, v);
    }
} tree;

class point_query_t {
public:
    int l, r, i, id;
};
// right queries mean we are trying to pair i with something to the right of it, in the range l r
// left queries mean the reversed
deque<point_query_t> right_queries;
deque<point_query_t> left_queries;
deque<point_query_t> queries;
int q;
int ans[MAX_N];

void process_left_queries() {
    // query, try to pair with the left side of the array
    sort(left_queries.begin(), left_queries.end(), [](const auto &A, const auto &B) { return A.i < B.i; });
    queries.clear();
    tree.build(1, 0, n - 1);
    for (int i = 0; i < n; i++) {
        for (auto &&need_on : turn_on[i]) tree.update<true>(need_on);
        for (auto &&need_off : turn_off[i]) tree.update<false>(need_off);
        // handle all the queries at i to the left
        while ((!left_queries.empty()) && (left_queries.front().i == i)) {
            queries.push_back(left_queries.front());
            left_queries.pop_front();
        }
        const auto i_l = i - p[i].b;
        const auto i_r = i - p[i].a;
        while ((!queries.empty()) && (queries.front().i == i)) {
            auto [l, r, _, id] = queries.front();
            queries.pop_front();
            auto [min_value, max_value] = tree.get(max(l, i_l), min(r, i_r));
            if (min_value != INF) ans[id] = max(ans[id], p[i].h - min_value);
            if (max_value != -INF) ans[id] = max(ans[id], max_value - p[i].h);
            if (i < r) queries.push_back(point_query_t{.l = l, .r = r, .i = i + 1, .id = id});
        }
    }
}

void process_right_queries() {
    // need to remake the turn on turn off arrays since we reverse direction now
    for (int i = 0; i < n; i++) turn_on[i].clear();
    for (int i = 0; i < n; i++) turn_off[i].clear();
    for (int i = 0; i < n; i++) {
        int l = i - p[i].b;
        int r = i - p[i].a;
        if (r >= 0) turn_on[r].push_back(i);
        if (l > 0) turn_off[l - 1].push_back(i);
    }

    // query, try to pair with the right side of the array
    sort(right_queries.begin(), right_queries.end(), [](const auto &A, const auto &B) { return A.i > B.i; });
    queries.clear();
    tree.build(1, 0, n - 1);
    for (int i = n - 1; i >= 0; i--) {
        for (auto &&need_on : turn_on[i]) tree.update<true>(need_on);
        for (auto &&need_off : turn_off[i]) tree.update<false>(need_off);
        // handle all the queries at i to the right
        while ((!right_queries.empty()) && (right_queries.front().i == i)) {
            queries.push_back(right_queries.front());
            right_queries.pop_front();
        }
        const auto i_l = i + p[i].a;
        const auto i_r = i + p[i].b;
        while ((!queries.empty()) && (queries.front().i == i)) {
            auto [l, r, _, id] = queries.front();
            queries.pop_front();
            auto [min_value, max_value] = tree.get(max(l, i_l), min(r, i_r));
            if (min_value != INF) ans[id] = max(ans[id], p[i].h - min_value);
            if (max_value != -INF) ans[id] = max(ans[id], max_value - p[i].h);
            if (i > l) queries.push_back(point_query_t{.l = l, .r = r, .i = i - 1, .id = id});
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        auto &&[h, a, b] = p[i];
        cin >> h >> a >> b;
        h -= 5e8;
    }

    precalculate();

    // read and handle query
    // to avoid memory issue we can't just place down all the query, so need to store it in the form of (i, l, r, id):
    // - query id is id
    // - the range of the query is from l to r
    // - the current element being considered is i
    // we can keep pushing it until the end of the queue with increased i
    cin >> q;
    for (int i = 0; i < q; i++) {
        static int l, r;
        cin >> l >> r;
        l--;
        r--;
        const int first_block = block_id(l);
        const int last_block = block_id(r);
        if (first_block + 1 < last_block) ans[i] = pre_result[first_block + 1][last_block - 1];
        else ans[i] = -1;
        if (first_block == last_block) {
            right_queries.push_back(point_query_t{.l = l, .r = r, .i = r, .id = i});
        } else {
            left_queries.push_back(point_query_t{.l = l, .r = r, .i = r - r % BLOCK_SIZE, .id = i});
            right_queries.push_back(point_query_t{.l = l, .r = r, .i = l - l % BLOCK_SIZE + BLOCK_SIZE - 1, .id = i});
        }
    }
    process_left_queries();
    process_right_queries();
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65