oj.uz

답안 #503077

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
503077 2022-01-07T06:34:43 Z blue 3단 점프 (JOI19_jumps) C++17
100 / 100
 974 ms 97500 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;

const int maxN = 500'000;
const ll INF = 1'000'000'000'000'000'000LL;

int N, Q;
vll A;
const int Z = (1<<19);

struct segtree
{
    vll lp = vll(Z<<1, -INF);
    vll half = vll(Z<<1, 0);
    vll full = vll(Z<<1, -INF);

    void build(int i, int l, int r)
    {
        if(l == r)
        {
            half[i] = A[l];
        }
        else
        {
            build(2*i, l, (l+r)/2);
            build(2*i+1, (l+r)/2+1, r);
            half[i] = max(half[2*i], half[2*i+1]);
        }
    }

    void deploy(int i, int l, int r, int L, int R, ll V)
    {
        if(R < l || r < L) return;
        else if(L <= l && r <= R)
        {
            lp[i] = max(lp[i], V);
            full[i] = max(full[i], half[i] + lp[i]);
        }
        else
        {
            deploy(2*i, l, (l+r)/2, L, R, V);
            deploy(2*i+1, (l+r)/2+1, r, L, R, V);

            full[i] = max({half[i] + lp[i], full[2*i], full[2*i+1]});
        }
    }

    pair<ll, ll> rangemax(int i, int l, int r, int L, int R)
    {
        if(R < l || r < L) return {-INF, -INF};
        else if(L <= l && r <= R)
        {
            return {full[i], half[i]};
        }
        else
        {
            pair<ll, ll> lft =rangemax(2*i, l, (l+r)/2, L, R);
            pair<ll, ll> rgt = rangemax(2*i+1, (l+r)/2+1, r, L, R);
            return {max({lft.first, rgt.first, lft.second + lp[i], rgt.second + lp[i]}), max(lft.second, rgt.second)};
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;

    A = vll(1+N+1);
    for(int i = 1; i <= N; i++) cin >> A[i];

    vi re[1+N];

    A[N+1] = INF;

    vi st{N+1};
    for(int i = N; i >= 1; i--)
    {
        while(A[i] > A[st.back()])
        {
            re[i].push_back(st.back());
            st.pop_back();
        }
        if(st.back() != N+1)
            re[i].push_back(st.back());

        st.push_back(i);
    }

    cin >> Q;
    vi l(1+Q), r(1+Q), lqi[1+N];
    for(int j = 1; j <= Q; j++)
    {
        cin >> l[j] >> r[j];
        lqi[l[j]].push_back(j);
    }

    vll res(1+Q, -INF);

    segtree S;
    S.build(1, 1, N);

    for(int li = N; li >= 1; li--)
    {
        for(int ri: re[li])
        {
            if(ri + (ri - li) > N) continue;
            S.deploy(1, 1, N, ri + (ri - li), N, A[li] + A[ri]);

        }

        for(int q: lqi[li])
        {
            res[q] = S.rangemax(1, 1, N, li, r[q]).first;
        }
    }

    for(int j = 1; j <= Q; j++) cout << res[j] << '\n';
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24880 KB Output is correct
2 Correct 11 ms 24868 KB Output is correct
3 Correct 11 ms 24848 KB Output is correct
4 Correct 11 ms 24912 KB Output is correct
5 Correct 11 ms 24876 KB Output is correct
6 Correct 15 ms 24884 KB Output is correct
7 Correct 11 ms 24924 KB Output is correct
8 Correct 11 ms 24908 KB Output is correct
9 Correct 12 ms 24892 KB Output is correct
10 Correct 13 ms 24908 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24880 KB Output is correct
2 Correct 11 ms 24868 KB Output is correct
3 Correct 11 ms 24848 KB Output is correct
4 Correct 11 ms 24912 KB Output is correct
5 Correct 11 ms 24876 KB Output is correct
6 Correct 15 ms 24884 KB Output is correct
7 Correct 11 ms 24924 KB Output is correct
8 Correct 11 ms 24908 KB Output is correct
9 Correct 12 ms 24892 KB Output is correct
10 Correct 13 ms 24908 KB Output is correct
11 Correct 228 ms 42052 KB Output is correct
12 Correct 236 ms 42004 KB Output is correct
13 Correct 233 ms 42016 KB Output is correct
14 Correct 268 ms 42072 KB Output is correct
15 Correct 246 ms 42044 KB Output is correct
16 Correct 293 ms 41428 KB Output is correct
17 Correct 239 ms 41428 KB Output is correct
18 Correct 233 ms 41352 KB Output is correct
19 Correct 263 ms 42048 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 42752 KB Output is correct
2 Correct 88 ms 43324 KB Output is correct
3 Correct 93 ms 42556 KB Output is correct
4 Correct 158 ms 42808 KB Output is correct
5 Correct 140 ms 42704 KB Output is correct
6 Correct 136 ms 42680 KB Output is correct
7 Correct 150 ms 42832 KB Output is correct
8 Correct 179 ms 42688 KB Output is correct
9 Correct 148 ms 42704 KB Output is correct

Subtask #4
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24880 KB Output is correct
2 Correct 11 ms 24868 KB Output is correct
3 Correct 11 ms 24848 KB Output is correct
4 Correct 11 ms 24912 KB Output is correct
5 Correct 11 ms 24876 KB Output is correct
6 Correct 15 ms 24884 KB Output is correct
7 Correct 11 ms 24924 KB Output is correct
8 Correct 11 ms 24908 KB Output is correct
9 Correct 12 ms 24892 KB Output is correct
10 Correct 13 ms 24908 KB Output is correct
11 Correct 228 ms 42052 KB Output is correct
12 Correct 236 ms 42004 KB Output is correct
13 Correct 233 ms 42016 KB Output is correct
14 Correct 268 ms 42072 KB Output is correct
15 Correct 246 ms 42044 KB Output is correct
16 Correct 293 ms 41428 KB Output is correct
17 Correct 239 ms 41428 KB Output is correct
18 Correct 233 ms 41352 KB Output is correct
19 Correct 263 ms 42048 KB Output is correct
20 Correct 160 ms 42752 KB Output is correct
21 Correct 88 ms 43324 KB Output is correct
22 Correct 93 ms 42556 KB Output is correct
23 Correct 158 ms 42808 KB Output is correct
24 Correct 140 ms 42704 KB Output is correct
25 Correct 136 ms 42680 KB Output is correct
26 Correct 150 ms 42832 KB Output is correct
27 Correct 179 ms 42688 KB Output is correct
28 Correct 148 ms 42704 KB Output is correct
29 Correct 943 ms 91068 KB Output is correct
30 Correct 817 ms 92488 KB Output is correct
31 Correct 791 ms 90492 KB Output is correct
32 Correct 923 ms 91036 KB Output is correct
33 Correct 893 ms 91092 KB Output is correct
34 Correct 908 ms 90456 KB Output is correct
35 Correct 974 ms 90024 KB Output is correct
36 Correct 907 ms 90356 KB Output is correct
37 Correct 912 ms 90912 KB Output is correct
38 Correct 624 ms 97500 KB Output is correct
39 Correct 680 ms 97484 KB Output is correct
40 Correct 597 ms 95728 KB Output is correct
41 Correct 652 ms 95364 KB Output is correct
42 Correct 604 ms 95504 KB Output is correct
43 Correct 604 ms 96452 KB Output is correct
44 Correct 665 ms 96680 KB Output is correct
45 Correct 675 ms 96732 KB Output is correct
46 Correct 614 ms 95188 KB Output is correct
47 Correct 629 ms 94948 KB Output is correct
48 Correct 633 ms 94908 KB Output is correct
49 Correct 632 ms 96196 KB Output is correct
50 Correct 721 ms 94276 KB Output is correct
51 Correct 706 ms 94280 KB Output is correct
52 Correct 701 ms 93412 KB Output is correct
53 Correct 733 ms 93308 KB Output is correct
54 Correct 685 ms 93228 KB Output is correct
55 Correct 694 ms 93972 KB Output is correct