oj.uz

Submission #655548

# Submission time Handle Problem Language Result Execution time Memory
655548 2022-11-04T16:59:07 Z piOOE Triple Jump (JOI19_jumps) C++17
100 / 100
 716 ms 40604 KB 
#include <bits/stdc++.h>

using namespace std;

struct Info {
    int add = 0, a = 0, ans = 0;
};

Info operator+(Info a, Info b) {
    return {max(a.add, b.add), max(a.a, b.a), max({a.ans, b.ans, a.add + b.a})};
}

int sz = 1;
vector<Info> t;

void init(int n, vector<int> a) {
    sz = n;
    t.assign(sz << 1, {});
    for (int i = 0; i < n; ++i) {
        t[i + sz].a = t[i + sz].ans = a[i];
    }
    for (int i = sz - 1; i > 0; --i) {
        t[i] = t[i << 1] + t[i << 1 | 1];
    }
}

Info rangeQuery(int l, int r) {
    Info L{}, R{};
    for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
        if (l & 1) {
            L = L + t[l++];
        }
        if (r & 1) {
            R = t[--r] + R;
        }
    }
    return L + R;
}

void modify(int i, int add) {
    i += sz;
    t[i].add = max(t[i].add, add);
    t[i].ans = t[i].add + t[i].a;
    while (i >>= 1) {
        t[i] = t[i << 1] + t[i << 1 | 1];
    }
}

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);

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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 240 ms 13452 KB Output is correct
12 Correct 234 ms 13220 KB Output is correct
13 Correct 237 ms 13328 KB Output is correct
14 Correct 223 ms 13444 KB Output is correct
15 Correct 238 ms 13412 KB Output is correct
16 Correct 223 ms 12720 KB Output is correct
17 Correct 234 ms 12796 KB Output is correct
18 Correct 265 ms 12644 KB Output is correct
19 Correct 234 ms 13300 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 11184 KB Output is correct
2 Correct 93 ms 8840 KB Output is correct
3 Correct 104 ms 9876 KB Output is correct
4 Correct 157 ms 11184 KB Output is correct
5 Correct 132 ms 11192 KB Output is correct
6 Correct 135 ms 11204 KB Output is correct
7 Correct 138 ms 11192 KB Output is correct
8 Correct 140 ms 11180 KB Output is correct
9 Correct 140 ms 11252 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 240 ms 13452 KB Output is correct
12 Correct 234 ms 13220 KB Output is correct
13 Correct 237 ms 13328 KB Output is correct
14 Correct 223 ms 13444 KB Output is correct
15 Correct 238 ms 13412 KB Output is correct
16 Correct 223 ms 12720 KB Output is correct
17 Correct 234 ms 12796 KB Output is correct
18 Correct 265 ms 12644 KB Output is correct
19 Correct 234 ms 13300 KB Output is correct
20 Correct 139 ms 11184 KB Output is correct
21 Correct 93 ms 8840 KB Output is correct
22 Correct 104 ms 9876 KB Output is correct
23 Correct 157 ms 11184 KB Output is correct
24 Correct 132 ms 11192 KB Output is correct
25 Correct 135 ms 11204 KB Output is correct
26 Correct 138 ms 11192 KB Output is correct
27 Correct 140 ms 11180 KB Output is correct
28 Correct 140 ms 11252 KB Output is correct
29 Correct 699 ms 40604 KB Output is correct
30 Correct 565 ms 34620 KB Output is correct
31 Correct 538 ms 36680 KB Output is correct
32 Correct 698 ms 40548 KB Output is correct
33 Correct 716 ms 40544 KB Output is correct
34 Correct 681 ms 39912 KB Output is correct
35 Correct 671 ms 39848 KB Output is correct
36 Correct 693 ms 39848 KB Output is correct
37 Correct 697 ms 40468 KB Output is correct
38 Correct 582 ms 40568 KB Output is correct
39 Correct 571 ms 40548 KB Output is correct
40 Correct 568 ms 38880 KB Output is correct
41 Correct 552 ms 38628 KB Output is correct
42 Correct 546 ms 38628 KB Output is correct
43 Correct 579 ms 39424 KB Output is correct
44 Correct 597 ms 40540 KB Output is correct
45 Correct 588 ms 40548 KB Output is correct
46 Correct 605 ms 39012 KB Output is correct
47 Correct 583 ms 38884 KB Output is correct
48 Correct 604 ms 38916 KB Output is correct
49 Correct 563 ms 40096 KB Output is correct
50 Correct 653 ms 40552 KB Output is correct
51 Correct 616 ms 40536 KB Output is correct
52 Correct 650 ms 39652 KB Output is correct
53 Correct 638 ms 39688 KB Output is correct
54 Correct 607 ms 39584 KB Output is correct
55 Correct 644 ms 40452 KB Output is correct