oj.uz

Submission #655432

# Submission time Handle Problem Language Result Execution time Memory
655432 2022-11-04T11:21:38 Z piOOE Triple Jump (JOI19_jumps) C++17
0 / 100
 58 ms 21540 KB 
#include <bits/stdc++.h>

using namespace std;

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 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 0;
    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);
                st.erase(it);
                rangeAdd(k, y, -s);
                st.insert({x, k, s});
            }
            rangeAdd(k, r, sum);
            st.insert({k, r, sum});
        }
    }

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 21540 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -