제출 #655441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
655441		piOOE	3단 점프 (JOI19_jumps)	C++17	46 / 100	1123 ms	62432 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

constexpr int inf = 1e9 + 7;

vector<int> t, tag;
int sz = 1;

void pull(int x) {
    t[x] = max(t[x << 1], t[x << 1 | 1]) + tag[x];
}

void init(int n, vector<int> a) {
    sz = 1 << (__lg(n) + bool(n & (n - 1)));
    t.assign(sz << 1, {}), tag.assign(sz << 1, {});
    for (int i = 0; i < n; ++i) {
        t[i + sz] = a[i];
    }
    for (int i = sz - 1; i > 0; --i) {
        pull(i);
    }
}

void push(int x) {
    for (int k : {x << 1, x << 1 | 1}) {
        tag[k] += tag[x];
        t[k] += tag[x];
    }
    tag[x] = 0;
}

void rangeAdd(int l, int r, int val, int x = 1, int lx = 0, int rx = sz) {
    if (l >= rx || lx >= r) return;
    if (l <= lx && rx <= r) {
        tag[x] += val;
        t[x] += val;
        return;
    }
    int mid = (lx + rx) >> 1;
    rangeAdd(l, r, val, x << 1, lx, mid), rangeAdd(l, r, val, x << 1 | 1, mid, rx);
    pull(x);
}

int rangeQuery(int l, int r, int x = 1, int lx = 0, int rx = sz) {
    if (l >= rx || lx >= r) return -inf;
    if (l <= lx && rx <= r) return t[x];
    int mid = (lx + rx) >> 1;
    return max(rangeQuery(l, r, x << 1, lx, mid), rangeQuery(l, r, x << 1 | 1, mid, rx)) + tag[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<array<int, 3>> events;

    auto relax = [&](int i, int j) {
        int r = j + (j - i);
        if (r < n) {
            events.push_back({i, j, -1});
        }
    };

    vector<int> stk;
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && a[stk.back()] <= a[i]) {
            relax(stk.back(), i);
            stk.pop_back();
        }
        if (!stk.empty()) {
            relax(stk.back(), i);
        }
        stk.push_back(i);
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        events.push_back({l - 1, r, i});
    }

    vector<int> ans(q);

    sort(events.begin(), events.end(), [&](array<int, 3> x, array<int, 3> y) {
        return x[0] != y[0] ? x[0] > y[0] : x[2] < y[2];
    });

    init(n, a);

    set<array<int, 3>> st;

    for (auto [i, j, tp]: events) {
        if (tp > -1) {
            ans[tp] = rangeQuery(i, j);
        } else {
            int k = j + (j - i);
            int sum = a[i] + a[j];

            auto it = st.lower_bound({k + 1, -1, -1});
            if (it != st.begin() && (*prev(it))[2] >= sum) {
                continue;
            }
            int r = n;
            while (true) {
                it = st.lower_bound({k, -1, -1});
                if (it == st.end()) {
                    r = n;
                    break;
                }
                auto [x, y, s] = *it;
                if (s > sum) {
                    r = (*it)[0];
                    break;
                }
                rangeAdd(x, y, -s);
                st.erase(it);
            }
            if (it != st.begin()) {
                auto [x, y, s] = *prev(it);
                assert(x < k);
                assert(y >= k);
                assert(s < sum);
                st.erase(prev(it));
                rangeAdd(k, y, -s);
                st.insert({x, k, s});
            }
            rangeAdd(k, r, sum);
            st.insert({k, r, sum});
//            for (auto [l, r, k]: st) {
//                cout << l << " " << r << "  " << k << endl;
//            }
//            for (int i = 0; i < n; ++i) {
//                cout << rangeQuery(i, i + 1) - a[i] << " ";
//            }
//            cout << endl;
//            cout << endl;
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54