Submission #1188505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188505		onbert	Two Antennas (JOI19_antennas)	C++20	100 / 100	850 ms	74904 KiB

antennas

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

struct event {
    int t, l, r, val;
    bool operator < (const event &b) const {
        if (t != b.t) return t < b.t;
        return val < b.val;
    }
};

const int maxn = 2e5 + 5, maxN = 8e5 + 5, INF = 1e10, INF2 = 2e10;
int n;
int h[maxn], a[maxn], b[maxn];
int q;
pair<int,int> qry[maxn];
int ans[maxn];

int seg[maxN], segPB[maxN], lazy[maxN], lazyPB[maxN];
void build(int id, int l, int r) {
    seg[id] = segPB[id] = -INF - INF2, lazy[id] = lazyPB[id] = 0;
    if (l == r) return;
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
}
void push(int id) {
    segPB[id] = max(seg[id] + lazyPB[id], segPB[id]);
    seg[id] += lazy[id];
    if (id * 2 < maxN) {
        lazyPB[id*2] = max(lazy[id*2] + lazyPB[id], lazyPB[id*2]);
        lazy[id*2] += lazy[id];
    }
    if (id * 2 + 1 < maxN) {
        lazyPB[id*2+1] = max(lazy[id*2+1] + lazyPB[id], lazyPB[id*2]);
        lazy[id*2+1] += lazy[id];
    }
    lazy[id] = lazyPB[id] = 0;
}
void update(int id, int l, int r, int findl, int findr, int val) {
    push(id);
    if (r < findl || findr < l) return;
    if (findl <= l && r <= findr) {
        lazy[id] += val;
        lazyPB[id] = max(lazy[id], lazyPB[id]);
        push(id);
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, findl, findr, val); update(id*2+1, mid+1, r, findl, findr, val);
    seg[id] = max(seg[id*2], seg[id*2+1]);
}
int mx(int id, int l, int r, int findl, int findr) {
    push(id);
    if (r < findl || findr < l) return - INF - INF2;
    if (findl <= l && r <= findr) return segPB[id];
    int mid = (l+r)/2;
    return max(mx(id*2, l, mid, findl, findr), mx(id*2+1, mid+1, r, findl, findr));
}

void solve() {
    build(1, 1, n);
    vector<event> vec[n+1];
    for (int i=1;i<=n;i++) {
        // cout << i << endl;
        vec[i].push_back({0, i-b[i], i-a[i], +INF+h[i]});
        if (i+1 <= n) vec[i+1].push_back({0, i-b[i], i-a[i], -INF-h[i]});
        if (i + a[i] <= n) vec[i+a[i]].push_back({0, i, i, +INF2 - h[i]});
        if (i + b[i] + 1 <= n) vec[i + b[i] + 1].push_back({0, i, i, -INF2 + h[i]});
    }
    for (int i=0;i<q;i++) vec[qry[i].second].push_back({1, qry[i].first, n, i});
    for (int i=1;i<=n;i++) {
        sort(vec[i].begin(), vec[i].end());
        for (auto [t, l, r, val]:vec[i]) {
            if (t == 0) {
                update(1, 1, n, l, r, val);
            } else if (t == 1) {
                ans[val] = max(mx(1, 1, n, l, r), ans[val]);
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i=1;i<=n;i++) cin >> h[i] >> a[i] >> b[i];
    cin >> q;
    for (int i=0;i<q;i++) {
        cin >> qry[i].first >> qry[i].second;
        ans[i] = -INF;
    }
    solve();
    for (int i=1;i<=n;i++) h[i] = -h[i];
    solve();
    // cout << "test\n";
    for (int i=0;i<q;i++) {
        if (ans[i] < 0) cout << "-1\n";
        else cout << ans[i] << "\n";
    }
}

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