Submission #1207788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207788		Hamed_Ghaffari	Two Antennas (JOI19_antennas)	C++20	100 / 100	521 ms	40060 KiB

antennas

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

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
#define maxs(a,b) (a=max(a,b))

const int MXN = 2e5+5, inf = 1e9;

int n;

int seg[MXN<<2], hseg[MXN<<2], lz[MXN<<2], hlz[MXN<<2];

inline void pull(int id) {
    seg[id] = max(seg[lc], seg[rc]);
    hseg[id] = max(hseg[lc], hseg[rc]);
}
void build(int l=1, int r=n+1, int id=1) {
    lz[id] = 0, hlz[id] = 0;
    seg[id] = hseg[id] = -inf;
    if(r-l == 1) return;
    build(l, mid, lc);
    build(mid, r, rc);
}
inline void apply(int x, int hx, int id) {
    hseg[id] = max(hseg[id], seg[id]+hx);
    seg[id] += x;
    hlz[id] = max(hlz[id], lz[id]+hx);
    lz[id] += x;
}
inline void push(int id) {
    if(lz[id] || hlz[id]) {
        apply(lz[id], hlz[id], lc);
        apply(lz[id], hlz[id], rc);
        lz[id] = hlz[id] = 0;
    }
}
void upd(int s, int e, int x, int l=1, int r=n+1, int id=1) {
    if(s>=r || l>=e) return;
    if(s<=l && r<=e) {
        apply(x, max(x, 0), id);
        return;
    }
    push(id);
    upd(s, e, x, l, mid, lc);
    upd(s, e, x, mid, r, rc);
    pull(id);
}
int get(int s, int e, int l=1, int r=n+1, int id=1) {
    if(s>=r || l>=e) return -inf;
    if(s<=l && r<=e) return hseg[id];
    push(id);
    return max(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}

int q, H[MXN], A[MXN], B[MXN], L[MXN], R[MXN], ans[MXN];
vector<int> Q[MXN], add[MXN], rem[MXN];

void solve() {
    for(int i=1; i<=q; i++) Q[R[i]].push_back(i);
    for(int i=1; i<=n; i++) {
        if(i+A[i]<=n) add[i+A[i]].push_back(i);
        if(i+B[i]+1<=n) rem[i+B[i]+1].push_back(i);
    }
    build();
    for(int r=1; r<=n; r++) {
        for(int i : add[r]) upd(i, i+1, inf-H[i]);
        for(int i : rem[r]) upd(i, i+1, -inf+H[i]);
        if(r-A[r]>=1) {
            upd(max(1, r-B[r]), r-A[r]+1, H[r]);
            upd(max(1, r-B[r]), r-A[r]+1, -H[r]);
        }
        for(int i : Q[r])
            ans[i] = max(ans[i], get(L[i], R[i]+1));
    }
    for(int i=1; i<=n; i++) {
        Q[i].clear();
        add[i].clear();
        rem[i].clear();
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> H[i] >> A[i] >> B[i];
    cin >> q;
    for(int i=1; i<=q; i++) cin >> L[i] >> R[i], ans[i]=-inf;
    solve();
    reverse(H+1, H+n+1);
    reverse(A+1, A+n+1);
    reverse(B+1, B+n+1);
    for(int i=1; i<=q; i++) {
        L[i] = n+1-L[i];
        R[i] = n+1-R[i];
        swap(L[i], R[i]);
    }
    solve();
    for(int i=1; i<=q; i++)
        cout << (ans[i]<0 ? -1 : ans[i]) << '\n';
}

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