Submission #1103953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103953		TrendBattles	Triple Jump (JOI19_jumps)	C++14	100 / 100	853 ms	75316 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;

#define INFILE "tjump.inp"
#define OUTFILE "tjump.out"

int maximise(int& x, int y) {
    if (x < y) return x = y, true;
    return false;
}
namespace SUBTASK_1 {
    const int MAX_N = 5000;
    int value[MAX_N + 10];

    int dp[MAX_N + 10][MAX_N + 10];
    int max_value[MAX_N + 10];

    void main(int N) {
        for (int i = 1; i <= N; ++i) {
            cin >> value[i];
        }

        for (int i = N; i >= 1; --i) {
            for (int j = i + 1; j <= N; ++j) {
                max_value[j] = max(max_value[j - 1], value[j]);

                if (j - i >= 2) {
                    dp[i][j] = value[i] + value[j] + max_value[i + (j - i) / 2];
                }

                maximise(dp[i][j], max(dp[i][j - 1], dp[i + 1][j]));
            }
        }

        int Q; cin >> Q;
        for (int qu = 1; qu <= Q; ++qu) {
            int l, r; cin >> l >> r;
            cout << dp[l][r] << '\n';
        }
    }
}

const int MAX_N = (int) 5e5;
int value[MAX_N + 10];

int debugging = false;
struct SegmentTree {
    vector <int> max_value, max_lazy, max_all;
    int N;
    void build(int v, int tl, int tr) {
        if (tl == tr) {
            max_value[v] = value[tl];
            return;
        }

        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm);
        build(v << 1 | 1, tm + 1, tr);

        max_value[v] = max(max_value[v << 1], max_value[v << 1 | 1]);
    }
    SegmentTree(int N): N(N), max_value(N << 2), max_lazy(N << 2), max_all(N << 2) {
        build(1, 1, N);
    }

    void Apply(int v, int delta) {
        maximise(max_lazy[v], delta);
        maximise(max_all[v], max_lazy[v] + max_value[v]);
    }
    void Push(int v) {
        for (int child : {v << 1, v << 1 | 1}) {
            Apply(child, max_lazy[v]);
        }
    }
    void update_range(int v, int tl, int tr, int l, int r, int delta) {
        if (l > r) return;

        if (l == tl and r == tr) {
            Apply(v, delta);
            
            return;
        }

        Push(v);
        int tm = (tl + tr) >> 1;
        update_range(v << 1, tl, tm, l, min(r, tm), delta);
        update_range(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, delta);

        //max_lazy[v] = max(max_lazy[v << 1], max_lazy[v << 1 | 1]);
        max_all[v] = max(max_all[v << 1], max_all[v << 1 | 1]);
    }
    void update_range(int l, int r, int delta) {
        update_range(1, 1, N, l, r, delta);
    }

    int get_range(int v, int tl, int tr, int l, int r) {
        if (l > r) return 0;

        if (l == tl and r == tr) return max_all[v];
        Push(v);
        int tm = (tl + tr) >> 1;

        return max(
            get_range(v << 1, tl, tm, l, min(r, tm)),
            get_range(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r)
        );
    }

    int get_range(int l, int r) {
        return get_range(1, 1, N, l, r);
    }
};
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen(INFILE, "r")) {
        freopen(INFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }   

    int N; cin >> N;
    // if (N <= 5000) {
    //     SUBTASK_1::main(N);
    //     return 0;
    // }

    for (int i = 1; i <= N; ++i) cin >> value[i];
    SegmentTree tree(N);

    vector <vector <int>> query_line(N + 1);
    vector <int> stack;
    
    int Q; cin >> Q;
    vector <int> start(Q), dest(Q);
    for (int qu = 0; qu < Q; ++qu) {
        cin >> start[qu] >> dest[qu];
        query_line[start[qu]].push_back(qu);
    }

    vector <int> finale(Q);
    for (int i = N; i >= 1; --i) {
        while (not stack.empty()) {
            int j = stack.back(); 

           // debugging = i == 11 and j == 12;

            tree.update_range(2 * j - i, N, value[i] + value[j]);

            if (value[i] < value[j]) break;
            stack.pop_back();
        }   

        
        stack.push_back(i);
        for (int id : query_line[i]) {
            finale[id] = tree.get_range(i + 2, dest[id]);
        }
    }

    for (int qu = 0; qu < Q; ++qu) cout << finale[qu] << '\n';
    return 0;
}

Compilation message (stderr)

jumps.cpp: In constructor 'SegmentTree::SegmentTree(int)':
jumps.cpp:50:9: warning: 'SegmentTree::N' will be initialized after [-Wreorder]
   50 |     int N;
      |         ^
jumps.cpp:49:18: warning:   'std::vector<int> SegmentTree::max_value' [-Wreorder]
   49 |     vector <int> max_value, max_lazy, max_all;
      |                  ^~~~~~~~~
jumps.cpp:63:5: warning:   when initialized here [-Wreorder]
   63 |     SegmentTree(int N): N(N), max_value(N << 2), max_lazy(N << 2), max_all(N << 2) {
      |     ^~~~~~~~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
jumps.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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