oj.uz

Submission #147507

# Submission time Handle Problem Language Result Execution time Memory
147507 2019-08-29T21:07:58 Z kuroni Triple Jump (JOI19_jumps) C++17
46 / 100
 1378 ms 152796 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N = 500005, Q = 500005;

int n, q, l, r, a[N], ans[Q];
vector<int> pos;
vector<pair<int, int>> upd[N], que[N];

struct STree
{
#define m (l + r) / 2
#define lc i * 2
#define rc i * 2 + 1

    int tot[4 * N], cur[4 * N] , lz[4 * N];

    void apply(int i, int v)
    {
        lz[i] = max(lz[i], v);
        tot[i] = max(tot[i], cur[i] + lz[i]);
    }

    void down(int i)
    {
        apply(lc, lz[i]);
        apply(rc, lz[i]);
        lz[i] = 0;
    }

    void update_range(int l, int r, int i, int L, int R, int v)
    {
        if (l > R || r < L || L > R)
            return;
        if (L <= l && r <= R)
        {
            apply(i, v);
            return;
        }
        down(i);
        update_range(l, m, lc, L, R, v);
        update_range(m + 1, r, rc, L, R, v);
        tot[i] = max(tot[lc], tot[rc]);
    }

    void update_node(int l, int r, int i, int u, int v)
    {
        if (l > u || r < u)
            return;
        if (l == r)
        {
            cur[i] = v; lz[i] = 0;
            apply(i, 0);
            return;
        }
        down(i);
        if (u <= m)
            update_node(l, m, lc, u, v);
        else
            update_node(m + 1, r, rc, u, v);
        cur[i] = max(cur[lc], cur[rc]);
        tot[i] = max(tot[lc], tot[rc]);
    }

    int query(int l, int r, int i, int L, int R)
    {
        if (l > R || r < L || L > R)
            return 0;
        else if (L <= l && r <= R)
            return tot[i];
        down(i);
        return max(query(l, m, lc, L, R), query(m + 1, r, rc, L, R));
    }

#undef m
#undef lc
#undef rc
} seg;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        while (!pos.empty())
        {
            int u = pos.back();
            upd[2 * i - u].push_back({u, a[i] + a[u]});
            if (a[u] <= a[i])
                pos.pop_back();
            else
                break;
        }
        pos.push_back(i);
    }
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> l >> r;
        que[r].push_back({l, i});
    }
    for (int i = 1; i <= n; i++)
    {
        for (pair<int, int> &v : upd[i])
            seg.update_node(1, n, 1, v.fi, v.se);
        seg.update_range(1, n, 1, 1, i, a[i]);
        for (pair<int, int> &v : que[i])
            ans[v.se] = seg.query(1, n, 1, v.fi, i);
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Correct 24 ms 23852 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 29 ms 23932 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Correct 24 ms 23852 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 29 ms 23932 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct
11 Correct 362 ms 42280 KB Output is correct
12 Correct 356 ms 42332 KB Output is correct
13 Correct 359 ms 42360 KB Output is correct
14 Correct 354 ms 42360 KB Output is correct
15 Correct 364 ms 42480 KB Output is correct
16 Correct 360 ms 41592 KB Output is correct
17 Correct 355 ms 41692 KB Output is correct
18 Correct 356 ms 41848 KB Output is correct
19 Correct 360 ms 42104 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 39552 KB Output is correct
2 Correct 154 ms 38920 KB Output is correct
3 Correct 165 ms 39664 KB Output is correct
4 Correct 219 ms 39672 KB Output is correct
5 Correct 224 ms 39576 KB Output is correct
6 Correct 203 ms 38904 KB Output is correct
7 Correct 203 ms 38764 KB Output is correct
8 Correct 204 ms 38972 KB Output is correct
9 Correct 208 ms 39244 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Correct 24 ms 23852 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 29 ms 23932 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct
11 Correct 362 ms 42280 KB Output is correct
12 Correct 356 ms 42332 KB Output is correct
13 Correct 359 ms 42360 KB Output is correct
14 Correct 354 ms 42360 KB Output is correct
15 Correct 364 ms 42480 KB Output is correct
16 Correct 360 ms 41592 KB Output is correct
17 Correct 355 ms 41692 KB Output is correct
18 Correct 356 ms 41848 KB Output is correct
19 Correct 360 ms 42104 KB Output is correct
20 Correct 210 ms 39552 KB Output is correct
21 Correct 154 ms 38920 KB Output is correct
22 Correct 165 ms 39664 KB Output is correct
23 Correct 219 ms 39672 KB Output is correct
24 Correct 224 ms 39576 KB Output is correct
25 Correct 203 ms 38904 KB Output is correct
26 Correct 203 ms 38764 KB Output is correct
27 Correct 204 ms 38972 KB Output is correct
28 Correct 208 ms 39244 KB Output is correct
29 Runtime error 1378 ms 152796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -