Submission #1149294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149294		adaawf	Two Antennas (JOI19_antennas)	C++20	0 / 100	176 ms	40384 KiB

antennas

#include <iostream>
#include <vector>
using namespace std;
vector<int> g[200005];
vector<pair<int, int>> gg[200005];
int hh = 2e9, res[200005], h[200005], a[200005], b[200005];
long long int lazy[800005], lazy2[800005];
struct HEIT {
    long long int c, mi, ma, res;
} e, t[800005];
HEIT Merge(HEIT aa, HEIT bb) {
    HEIT res;
    res.c = aa.c + bb.c;
    res.mi = min(aa.mi, bb.mi);
    res.ma = max(aa.ma, bb.ma);
    res.res = max(aa.res, bb.res);
    return res;
}
void apply(int v, long long int x, long long int y) {
    if (t[v].c == 0) return;
    t[v].res = max(t[v].res, x - t[v].mi);
    t[v].res = max(t[v].res, t[v].ma - y);
    lazy[v] = max(lazy[v], x);
    lazy2[v] = min(lazy2[v], y);
}
void push(int v) {
    apply(v << 1, lazy[v], lazy2[v]);
    apply(v << 1 | 1, lazy[v], lazy2[v]);
    lazy[v] = -hh; lazy2[v] = hh;
}
void build(int v, int tl, int tr) {
    t[v] = e;
    lazy[v] = -hh; lazy2[v] = hh;
    if (tl == tr) {
        return;
    }
    int mid = (tl + tr) >> 1;
    build(v << 1, tl, mid);
    build(v << 1, mid + 1, tr);
}
void update(int v, int tl, int tr, int l, int r, long long int x) {
    if (l > r) return;
    if (tl == l && tr == r) {
        apply(v, x, x);
        return;
    }
    push(v);
    int mid = (tl + tr) >> 1;
    update(v << 1, tl, mid, l, min(r, mid), x);
    update(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r, x);
    t[v] = Merge(t[v << 1], t[v << 1 | 1]);
}
void update(int v, int tl, int tr, int x) {
    if (tl == tr) {
        if (t[v].c == 0) {
            t[v].c = 1;
            t[v].mi = t[v].ma = h[x];
            t[v].res = -hh;
        }
        else {
            t[v].c = 0;
            t[v].mi = hh; t[v].ma = -hh;
        }
        return;
    }
    push(v);
    int mid = (tl + tr) >> 1;
    if (mid >= x) update(v << 1, tl, mid, x);
    else update(v << 1 | 1, mid + 1, tr, x);
    t[v] = Merge(t[v << 1], t[v << 1 | 1]);
}
long long int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return -hh;
    if (tl == l && tr == r) {
        return t[v].res;
    }
    push(v);
    int mid = (tl + tr) >> 1;
    return max(sum(v << 1, tl, mid, l, min(r, mid)), sum(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r));
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    e = {0, hh, -hh, -hh};
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> a[i] >> b[i];
        g[max(i - a[i], 0)].push_back(i);
        g[max(i - b[i] - 1, 0)].push_back(i);
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        gg[l].push_back({r, i});
    }
    build(1, 1, n);
    for (int i = n; i >= 1; i--) {
        for (int w : g[i]) {
            update(1, 1, n, w);
        }
        int l = i + a[i], r = i + b[i];
        if (l <= n) {
            r = min(r, n);
            update(1, 1, n, l, r, h[i]);
        }
        for (auto w : gg[i]) {
            long long int k = sum(1, 1, n, i, w.first);
            if (k < 0) res[w.second] = -1;
            else res[w.second] = k;
        }
    }
    for (int i = 0; i < q; i++) cout << res[i] << '\n';
}

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