Submission #332889

#	Time	Username	Problem	Language	Result	Execution time	Memory
332889		12tqian	Two Antennas (JOI19_antennas)	C++17	100 / 100	1375 ms	35180 KiB

antennas

#include <bits/stdc++.h>

const int INF = 1e9;

template <class T> struct LazySeg {
    int sz;
    std::vector<T> c; // stores max of c
    std::vector<T> d; // stores max of d
    std::vector<T> lazy; // stores what you subtract max with
    void init(int n) {
        sz = 1;
        while (sz < n) sz *= 2;
        c.assign(2 * sz, -INF);
        d.assign(2 * sz, -INF);
        lazy.assign(2 * sz, -INF);
    }   
    void pull(int ind) {
        c[ind] = std::max(c[2 * ind], c[2 * ind + 1]);
        d[ind] = std::max(d[2 * ind], d[2 * ind + 1]);
    }
    void push(int ind, int L, int R) {
        d[ind] = std::max(d[ind], c[ind] + lazy[ind]);
        if (L != R) {
            lazy[2 * ind] = std::max(lazy[2 * ind], lazy[ind]);
            lazy[2 * ind + 1] = std::max(lazy[2 * ind + 1], lazy[ind]);
        }
        lazy[ind] = -INF;
    }
    void set(int p, T val, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;   
        push(ind, L, R);
        if (p < L || R < p) return; 
        if (L == R) {
            c[ind] = val;
            push(ind, L, R);    
            return;
        }
        int M = (L + R) / 2;
        set(p, val, 2 * ind, L, M);
        set(p, val, 2 * ind + 1, M + 1, R);
        pull(ind);
    }
    void set_max(int lo, int hi, T val, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (R < lo || hi < L) return;
        if (lo <= L && R <= hi) {
            lazy[ind] = val;
            push(ind, L, R);
            return;
        }
        int M = (L + R) / 2;
        set_max(lo, hi, val, 2 * ind, L, M);
        set_max(lo, hi, val, 2 * ind + 1, M + 1, R);
        pull(ind);
    }
    T qmax(int t, int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);    
        if (R < lo || hi < L) return -INF;
        if (lo <= L && R <= hi) return (t == 0 ? c[ind] : d[ind]);
        int M = (L + R) / 2;
        return std::max(qmax(t, lo, hi, 2 * ind, L, M), qmax(t, lo, hi, 2 * ind + 1, M + 1, R));
    }
};

int main() {
    using namespace std;
    ios_base::sync_with_stdio(0);
    int n; cin >> n;
    vector<int> h(n), a(n), b(n);
    for (int i = 0; i < n; i++) 
        cin >> h[i] >> a[i] >> b[i];
    int q; cin >> q;
    vector<array<int, 2>> queries(q);
    for (int i = 0; i < q; i++)
        cin >> queries[i][0] >> queries[i][1], queries[i][0]--, queries[i][1]--;
    vector<int> ans(q, -1);
    LazySeg<int> seg;
    int tt = 0;
    auto solve = [&]() {
        tt++;
        seg.init(n);
        vector<vector<array<int, 2>>> events(n);
        for (int i = 0; i < n; i++) {
            if (i + a[i] < n)
                events[i + a[i]].push_back({1, i});
            if (i + b[i] < n)
                events[i + b[i]].push_back({3, i});
            events[i].push_back({2, i});
        }
        for (int i = 0; i < q; i++) 
            events[queries[i][1]].push_back({4, i});
        for (auto& v : events)
            sort(v.begin(), v.end());        
        for (int j = 0; j < n; j++) {
            for (auto& e : events[j]) {
                int id = e[1];
                if (e[0] == 1) {
                    seg.set(id, h[id]);
                } else if (e[0] == 2) {
                    int l = max(0, j - b[id]);
                    int r = j - a[id];
                    if (l <= r) {
                        seg.set_max(l, r, -h[id]);
                    }
                } else if (e[0] == 3) {
                    seg.set(id, -INF);
                } else if (e[0] == 4) {
                    int l = queries[id][0];
                    int r = queries[id][1];
                    ans[id] = max(ans[id], seg.qmax(1, l, r));
                }
            }
        }
    };
    solve();
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    reverse(h.begin(), h.end());
    for (int i = 0; i < q; i++) {
        queries[i][0] = n - 1 - queries[i][0];
        queries[i][1] = n - 1 - queries[i][1];
        swap(queries[i][0], queries[i][1]);
    }
    solve();
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
    return 0;
}

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