oj.uz

Submission #284182

# Submission time Handle Problem Language Result Execution time Memory
284182 2020-08-27T01:18:18 Z ijxjdjd Triple Jump (JOI19_jumps) Java 11
46 / 100
 4000 ms 228028 KB 
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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10376 KB Output is correct
2 Correct 95 ms 10652 KB Output is correct
3 Correct 113 ms 10672 KB Output is correct
4 Correct 112 ms 10484 KB Output is correct
5 Correct 98 ms 10632 KB Output is correct
6 Correct 96 ms 10648 KB Output is correct
7 Correct 107 ms 10616 KB Output is correct
8 Correct 96 ms 10600 KB Output is correct
9 Correct 95 ms 10496 KB Output is correct
10 Correct 95 ms 10360 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10376 KB Output is correct
2 Correct 95 ms 10652 KB Output is correct
3 Correct 113 ms 10672 KB Output is correct
4 Correct 112 ms 10484 KB Output is correct
5 Correct 98 ms 10632 KB Output is correct
6 Correct 96 ms 10648 KB Output is correct
7 Correct 107 ms 10616 KB Output is correct
8 Correct 96 ms 10600 KB Output is correct
9 Correct 95 ms 10496 KB Output is correct
10 Correct 95 ms 10360 KB Output is correct
11 Correct 1657 ms 107048 KB Output is correct
12 Correct 1456 ms 105280 KB Output is correct
13 Correct 1502 ms 106148 KB Output is correct
14 Correct 1732 ms 106840 KB Output is correct
15 Correct 1519 ms 107548 KB Output is correct
16 Correct 1422 ms 107012 KB Output is correct
17 Correct 1404 ms 106628 KB Output is correct
18 Correct 1499 ms 107024 KB Output is correct
19 Correct 1487 ms 106948 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 89436 KB Output is correct
2 Correct 846 ms 63696 KB Output is correct
3 Correct 820 ms 62960 KB Output is correct
4 Correct 1057 ms 93032 KB Output is correct
5 Correct 1064 ms 93428 KB Output is correct
6 Correct 1000 ms 65108 KB Output is correct
7 Correct 968 ms 68520 KB Output is correct
8 Correct 1018 ms 68416 KB Output is correct
9 Correct 1010 ms 64896 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10376 KB Output is correct
2 Correct 95 ms 10652 KB Output is correct
3 Correct 113 ms 10672 KB Output is correct
4 Correct 112 ms 10484 KB Output is correct
5 Correct 98 ms 10632 KB Output is correct
6 Correct 96 ms 10648 KB Output is correct
7 Correct 107 ms 10616 KB Output is correct
8 Correct 96 ms 10600 KB Output is correct
9 Correct 95 ms 10496 KB Output is correct
10 Correct 95 ms 10360 KB Output is correct
11 Correct 1657 ms 107048 KB Output is correct
12 Correct 1456 ms 105280 KB Output is correct
13 Correct 1502 ms 106148 KB Output is correct
14 Correct 1732 ms 106840 KB Output is correct
15 Correct 1519 ms 107548 KB Output is correct
16 Correct 1422 ms 107012 KB Output is correct
17 Correct 1404 ms 106628 KB Output is correct
18 Correct 1499 ms 107024 KB Output is correct
19 Correct 1487 ms 106948 KB Output is correct
20 Correct 1033 ms 89436 KB Output is correct
21 Correct 846 ms 63696 KB Output is correct
22 Correct 820 ms 62960 KB Output is correct
23 Correct 1057 ms 93032 KB Output is correct
24 Correct 1064 ms 93428 KB Output is correct
25 Correct 1000 ms 65108 KB Output is correct
26 Correct 968 ms 68520 KB Output is correct
27 Correct 1018 ms 68416 KB Output is correct
28 Correct 1010 ms 64896 KB Output is correct
29 Execution timed out 4048 ms 228028 KB Time limit exceeded
30 Halted 0 ms 0 KB -