Submission #592737

#	Time	Username	Problem	Language	Result	Execution time	Memory
592737		pakhomovee	Two Antennas (JOI19_antennas)	C++17	100 / 100	1154 ms	69020 KiB

antennas

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <iomanip>
#include <cassert>
#include <deque>
#include <functional>
#include <set>
#include <queue>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <complex>

#define int long long
using namespace std;

struct antenna {
    int a, b, h;

    antenna() {}
    antenna(int a, int b, int h): a(a), b(b), h(h) {}
};

int n;
const int maxn = 2e5;
const int inf = 1e15;
vector<antenna> a;

int tree[maxn * 4];
int mn[maxn * 4];
int smn[maxn * 4];
int mnVal[maxn * 4];
int h[maxn];

void init() {
    fill(tree, tree + maxn * 4, -inf * 2);
    fill(mn, mn + maxn * 4, -inf);
    fill(smn, smn + maxn * 4, inf);
    fill(mnVal, mnVal + maxn * 4, inf);
    fill(h, h + maxn, inf);
}

void tag(int i, int x) {
    tree[i] = max(tree[i], x - mnVal[i]);
    mn[i] = max(x, mn[i]);
}

void push(int i) {
    tag(i * 2 + 1, mn[i]);
    tag(i * 2 + 2, mn[i]);
}

void merge(int i, int l, int r) {
    tree[i] = max({ tree[i], tree[l], tree[r] });
    mn[i] = min(mn[l], mn[r]);
    mnVal[i] = min(mnVal[l], mnVal[r]);
    smn[i] = min(smn[l], smn[r]);
    if (mn[l] != mn[r]) {
        smn[i] = min(smn[i], max(mn[l], mn[r]));
    }
}

void chmax(int i, int l, int r, int ql, int qr, int x) {
    if (qr <= l || r <= ql || mn[i] >= x) {
        return;
    }
    if (ql <= l && r <= qr && smn[i] > x) {
        tag(i, x);
        return;
    }
    int m = (l + r) / 2;
    push(i);
    chmax(i * 2 + 1, l, m, ql, qr, x);
    chmax(i * 2 + 2, m, r, ql, qr, x);
    merge(i, i * 2 + 1, i * 2 + 2);
}

void setinf(int i, int l, int r, int qi) {
    if (qi < l || r <= qi) {
        return;
    }
    if (l + 1 == r) {
        mn[i] = -inf;
        return;
    }
    int m = (l + r) / 2;
    push(i);
    setinf(i * 2 + 1, l, m, qi);
    setinf(i * 2 + 2, m, r, qi);
    merge(i, i * 2 + 1, i * 2 + 2);
}

void updval(int i, int l, int r, int qi, int x) {
    if (qi < l || r <= qi) {
        return;
    }
    if (l + 1 == r) {
        tree[i] = max(tree[i], mn[i] - x);
        mnVal[i] = x;
        return;
    }
    int m = (l + r) / 2;
    push(i);
    updval(i * 2 + 1, l, m, qi, x);
    updval(i * 2 + 2, m, r, qi, x);
    merge(i, i * 2 + 1, i * 2 + 2);
}

void enable(int j) {
    h[j] = a[j].h;
    setinf(0, 0, n, j);
    updval(0, 0, n, j, h[j]);
}

void disable(int j) {
    h[j] = inf;
    updval(0, 0, n, j, h[j]);
}

int get(int i, int l, int r, int ql, int qr) {
    if (qr <= l || r <= ql) {
        return -2;
    }
    if (ql <= l && r <= qr) {
        return tree[i];
    }
    int m = (l + r) / 2;
    push(i);
    int res = max(get(i * 2 + 1, l, m, ql, qr), get(i * 2 + 2, m, r, ql, qr));
    merge(i, i * 2 + 1, i * 2 + 2);
    return res;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        int x, y, h;
        cin >> h >> x >> y;
        a[i] = antenna(x, y, h);
    }
    vector<vector<pair<int, int>>> queries(n + 1);
    int q;
    cin >> q;
    vector<int> ans(q, -1);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        queries[r - 1].push_back({ l - 1, i });
    }
    auto solve = [&] {
        init();
        vector<vector<int>> add(n + 1);
        vector<vector<int>> del(n + 1);
        for (int i = 0; i < n; ++i) {
            add[min(i + a[i].a, n)].push_back(i);
            del[min(i + a[i].b + 1, n)].push_back(i);
            for (int j : add[i]) {
                enable(j);
            }
            for (int j : del[i]) {
                disable(j);
            }
            int L = max(0ll, i - a[i].b);
            int R = max(0ll, i - a[i].a + 1);
            chmax(0, 0, n, L, R, a[i].h);
            for (auto [l, j] : queries[i]) {
                ans[j] = max(ans[j], get(0, 0, n, l, i + 1));
            }
        }
    };
    solve();
    for (int i = 0; i < n; ++i) {
        a[i].h *= -1;
    }
    solve();
    for (int i : ans) {
        cout << i << '\n';
    }
}

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