Submission #1295700

#TimeUsernameProblemLanguageResultExecution timeMemory
1295700MinhKienTwo Antennas (JOI19_antennas)C++20
0 / 100
309 ms42520 KiB
#include <iostream>
#include <vector>

using namespace std;

#define ll long long

const int N = 2e5 + 10;
const ll INF = 1e17;

int n, m;
vector <int> add[N], rev[N], queries[N];

struct obj {
    ll h;
    int l, r;

    void inp() {
        cin >> h >> l >> r;
    }
} a[N];

struct query {
    int l, r;
    ll ans;

    void inp() {
        cin >> l >> r;
        ans = -INF;
    }
} q[N];

struct SEG {
    struct node {
        ll one, two, val, lazy;

        node () {
            one = two = val = lazy = -INF;
        }
    } st[N << 2];

    void reset() {
        fill_n(st, N << 2, node());
    }

    void down(int id) {
        ll lz = st[id].lazy;
        if (lz == -INF) return;

        st[id].lazy = -INF;

        st[id << 1].two = max(st[id << 1].two, lz);
        st[id << 1].val = st[id << 1].two + st[id << 1].one;
        st[id << 1].lazy = max(st[id << 1].lazy, lz);

        st[id << 1 | 1].two = max(st[id << 1 | 1].two, lz);
        st[id << 1 | 1].val = st[id << 1 | 1].two + st[id << 1 | 1].one;
        st[id << 1 | 1].lazy = max(st[id << 1 | 1].lazy, lz);
    }

    void update_one(int l, int r, int u, ll VAL, int id) {
        if (l == r) {
            st[id].one = VAL;
            st[id].val = st[id].one + st[id].two;
            return;
        }

        int mid = (l + r) >> 1;
        down(id);

        if (u <= mid) update_one(l, mid, u, VAL, id << 1);
        else update_one(mid + 1, r, u, VAL, id << 1 | 1);

        st[id].one = max(st[id << 1].one, st[id << 1 | 1].one);
        st[id].val = max(max(st[id << 1].val, st[id << 1 | 1].val), st[id].one + st[id].two);
    }

    void update_two(int l, int r, int u, int v, ll VAL, int id) {
        if (l > v || r < u) return;

        if (l >= u && r <= v) {
            st[id].two = max(st[id].two, VAL);
            st[id].lazy = max(st[id].lazy, VAL);
            st[id].val = st[id].one + st[id].two;
            return;
        }

        int mid = (l + r) >> 1;
        down(id);
        update_two(l, mid, u, v, VAL, id << 1);
        update_two(mid + 1, r, u, v, VAL, id << 1 | 1);

        st[id].val = max(max(st[id << 1].val, st[id << 1 | 1].val), st[id].one + st[id].two);
    }

    ll get(int l, int r, int u, int v, int id) {
        if (l > v || r < u) return -INF;

        if (l >= u && r <= v) return st[id].val;

        int mid = (l + r) >> 1;
        down(id);
        return max(get(l, mid, u, v, id << 1), get(mid + 1, r, u, v, id << 1 | 1));
    }
} seg;

void input() {
    cin >> n;
    for (int i = 1; i <= n; ++i) a[i].inp();
    cin >> m;
    for (int i = 1; i <= m; ++i) q[i].inp();
}

void LeftToRight() {
    // reset //
    seg.reset();
    // ------------------ //

    for (int i = 1; i <= n; ++i) {
        if (i + a[i].l <= n) add[i + a[i].l].push_back(i);
        if (i + a[i].r + 1 <= n) rev[i + a[i].r + 1].push_back(i);
    }

    for (int i = 1; i <= m; ++i) {
        queries[q[i].r].push_back(i);
    }

    seg.reset();
    for (int i = 1; i <= n; ++i) {
        for (int z: add[i]) seg.update_one(1, n, z, -a[z].h, 1);
        for (int z: rev[i]) seg.update_one(1, n, z, -INF, 1);

        int Left = max(1, i - a[i].r), Right = i - a[i].l;
        if (Left <= Right) {
            seg.update_two(1, n, Left, Right, a[i].h, 1);
        }

        for (int z: queries[i]) {
            q[z].ans = seg.get(1, n, q[z].l, q[z].r, 1);
        }
    }
}

void RightToLeft() {
    // reset //
    seg.reset();
    for (int i = 1; i <= n; ++i) {
        add[i].clear();
        rev[i].clear();
        queries[i].clear();
    }
    // ------------------ //

    for (int i = 1; i <= n; ++i) {
        if (i - a[i].l >= 1) add[i - a[i].l].push_back(i);
        if (i - a[i].r - 1 >= 1) rev[i - a[i].r - 1].push_back(i);
    }

    for (int i = 1; i <= m; ++i) {
        queries[q[i].l].push_back(i);
    }

    seg.reset();
    for (int i = n; i >= 1; --i) {
        for (int z: add[i]) seg.update_one(1, n, z, -a[z].h, 1);
        for (int z: rev[i]) seg.update_one(1, n, z, -INF, 1);

        int Left = i + a[i].l, Right = min(n, i + a[i].r);
        if (Left <= Right) {
            seg.update_two(1, n, Left, Right, a[i].h, 1);
        }

        for (int z: queries[i]) {
            q[z].ans = max(q[z].ans, seg.get(1, n, q[z].l, q[z].r, 1));
        }
    }
}

void solve() {
    LeftToRight();
    RightToLeft();

    for (int i = 1; i <= m; ++i) {
        if (q[i].ans < 0) q[i].ans = -1;
        cout << q[i].ans << "\n";
    }
}

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

    input();
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...