Submission #284182

#	Time	Username	Problem	Language	Result	Execution time	Memory
284182		ijxjdjd	Triple Jump (JOI19_jumps)	Java	46 / 100	4048 ms	228028 KiB

jumps

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.ArrayList;
import java.util.Vector;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class jumps {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TripleJumps solver = new TripleJumps();
        solver.solve(1, in, out);
        out.close();
    }

    static class TripleJumps {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            int[] F = new int[N];
            for (int i = 0; i < N; i++) {
                F[i] = in.nextInt();
            }
            Stack<Integer> stack = new Stack<>();
            ArrayList<Integer>[] pair = new ArrayList[N];
            for (int i = 0; i < N; i++) {
                pair[i] = new ArrayList<>();
            }
            stack.add(0);
            for (int i = 1; i < N; i++) {
                while (stack.size() > 0 && F[stack.peek()] <= F[i]) {
                    pair[stack.pop()].add(i);
                }
                if (!stack.isEmpty()) {
                    pair[stack.peek()].add(i);
                }
                stack.add(i);
            }
            int Q = in.nextInt();
            ArrayList<int[]>[] query = new ArrayList[N];
            for (int i = 0; i < Q; i++) {
                int l = in.nextInt() - 1;
                int r = in.nextInt() - 1;
                if (query[l] == null) {
                    query[l] = new ArrayList<>();
                }
                query[l].add(new int[]{r, i});
            }
            int[] ans = new int[Q];
            SegmentTree seg = new SegmentTree(F);
            for (int l = N - 2; l >= 0; l--) {
                if (pair[l] != null) {
                    for (int a : pair[l]) {
                        seg.upd(1, 0, N - 1, 2 * a - l, N - 1, F[a] + F[l]);
                    }
                }
                if (query[l] != null) {
                    for (int[] r : query[l]) {
                        ans[r[1]] = seg.query(1, 0, N - 1, l + 2, r[0]);
                    }
                }
            }
            for (int i : ans) {
                out.println(i);
            }
        }

        class SegmentTree {
            int[] max;
            int[] lzy;
            int[] oriMax;
            int[] arr;

            SegmentTree(int[] arr) {
                this.arr = arr;
                max = new int[4 * arr.length];
                oriMax = new int[4 * arr.length];
                lzy = new int[4 * arr.length];
                setOri(1, 0, arr.length - 1);
            }

            void setOri(int n, int tl, int tr) {
                if (tl == tr) {
                    oriMax[n] = arr[tl];
                } else {
                    int tm = (tl + tr) / 2;
                    setOri(2 * n, tl, tm);
                    setOri(2 * n + 1, tm + 1, tr);
                    oriMax[n] = Math.max(oriMax[2 * n], oriMax[2 * n + 1]);
                }
            }

            void push(int n) {
                lzy[2 * n] = Math.max(lzy[2 * n], lzy[n]);
                lzy[2 * n + 1] = Math.max(lzy[2 * n + 1], lzy[n]);
                max[2 * n] = Math.max(max[2 * n], oriMax[2 * n] + lzy[2 * n]);
                max[2 * n + 1] = Math.max(max[2 * n + 1], oriMax[2 * n + 1] + lzy[2 * n + 1]);
                lzy[n] = 0;
            }

            void upd(int n, int tl, int tr, int l, int r, int val) {
                if (l <= tl && tr <= r) {
                    max[n] = Math.max(max[n], oriMax[n] + val);
                    lzy[n] = Math.max(lzy[n], val);
                } else if (l > tr || r < tl) {
                    return;
                } else {
                    push(n);
                    int tm = (tl + tr) / 2;
                    upd(2 * n, tl, tm, l, r, val);
                    upd(2 * n + 1, tm + 1, tr, l, r, val);
                    max[n] = Math.max(max[2 * n], max[2 * n + 1]);
                }
            }

            int query(int n, int tl, int tr, int l, int r) {
                if (l <= tl && tr <= r) {
                    return max[n];
                } else if (l > tr || r < tl) {
                    return 0;
                } else {
                    push(n);
                    int tm = (tl + tr) / 2;
                    return Math.max(query(2 * n, tl, tm, l, r),
                            query(2 * n + 1, tm + 1, tr, l, r));
                }
            }

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

Compilation message (stderr)

Note: jumps.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

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