oj.uz

Submission #284184

# Submission time Handle Problem Language Result Execution time Memory
284184 2020-08-27T01:28:27 Z ijxjdjd Triple Jump (JOI19_jumps) Java 11
46 / 100
 4000 ms 176896 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.util.Comparator;
import java.util.Collections;
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<int[]> iter = new ArrayList<>();
            stack.add(0);
            for (int i = 1; i < N; i++) {
                while (stack.size() > 0 && F[stack.peek()] <= F[i]) {
                    iter.add(new int[]{stack.pop(), i});
                }
                if (!stack.isEmpty()) {
                    iter.add(new int[]{stack.peek(), i});
                }
                stack.add(i);
            }
            int Q = in.nextInt();
            for (int i = 0; i < Q; i++) {
                int l = in.nextInt() - 1;
                int r = in.nextInt() - 1;
                iter.add(new int[]{l, r, i});
            }
            Collections.sort(iter, new Comparator<int[]>() {

                public int compare(int[] ints, int[] t1) {
                    if (ints[0] == t1[0]) {
                        return Integer.compare(ints.length, t1.length);
                    } else {
                        return Integer.compare(t1[0], ints[0]);
                    }
                }
            });
            int[] ans = new int[Q];
            SegmentTree seg = new SegmentTree(F);
            for (int l = 0; l < iter.size(); l++) {
                int[] t = iter.get(l);
                if (iter.get(l).length == 2) {
                    seg.upd(1, 0, N - 1, 2 * t[1] - t[0], N - 1, F[t[1]] + F[t[0]]);
                } else {
                    ans[t[2]] = seg.query(1, 0, N - 1, t[0] + 2, t[1]);
                }
            }
            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());
        }

    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10532 KB Output is correct
2 Correct 114 ms 10512 KB Output is correct
3 Correct 96 ms 10620 KB Output is correct
4 Correct 99 ms 10636 KB Output is correct
5 Correct 99 ms 10616 KB Output is correct
6 Correct 101 ms 10504 KB Output is correct
7 Correct 111 ms 10552 KB Output is correct
8 Correct 98 ms 10600 KB Output is correct
9 Correct 107 ms 10596 KB Output is correct
10 Correct 104 ms 10352 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10532 KB Output is correct
2 Correct 114 ms 10512 KB Output is correct
3 Correct 96 ms 10620 KB Output is correct
4 Correct 99 ms 10636 KB Output is correct
5 Correct 99 ms 10616 KB Output is correct
6 Correct 101 ms 10504 KB Output is correct
7 Correct 111 ms 10552 KB Output is correct
8 Correct 98 ms 10600 KB Output is correct
9 Correct 107 ms 10596 KB Output is correct
10 Correct 104 ms 10352 KB Output is correct
11 Correct 1974 ms 106512 KB Output is correct
12 Correct 1883 ms 103772 KB Output is correct
13 Correct 2023 ms 105700 KB Output is correct
14 Correct 2033 ms 105860 KB Output is correct
15 Correct 1752 ms 105996 KB Output is correct
16 Correct 1892 ms 104700 KB Output is correct
17 Correct 1840 ms 106312 KB Output is correct
18 Correct 1854 ms 104492 KB Output is correct
19 Correct 2021 ms 106432 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 61924 KB Output is correct
2 Correct 680 ms 57736 KB Output is correct
3 Correct 674 ms 62080 KB Output is correct
4 Correct 1189 ms 60648 KB Output is correct
5 Correct 1029 ms 60720 KB Output is correct
6 Correct 1006 ms 60764 KB Output is correct
7 Correct 954 ms 63976 KB Output is correct
8 Correct 1033 ms 63860 KB Output is correct
9 Correct 1006 ms 60780 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10532 KB Output is correct
2 Correct 114 ms 10512 KB Output is correct
3 Correct 96 ms 10620 KB Output is correct
4 Correct 99 ms 10636 KB Output is correct
5 Correct 99 ms 10616 KB Output is correct
6 Correct 101 ms 10504 KB Output is correct
7 Correct 111 ms 10552 KB Output is correct
8 Correct 98 ms 10600 KB Output is correct
9 Correct 107 ms 10596 KB Output is correct
10 Correct 104 ms 10352 KB Output is correct
11 Correct 1974 ms 106512 KB Output is correct
12 Correct 1883 ms 103772 KB Output is correct
13 Correct 2023 ms 105700 KB Output is correct
14 Correct 2033 ms 105860 KB Output is correct
15 Correct 1752 ms 105996 KB Output is correct
16 Correct 1892 ms 104700 KB Output is correct
17 Correct 1840 ms 106312 KB Output is correct
18 Correct 1854 ms 104492 KB Output is correct
19 Correct 2021 ms 106432 KB Output is correct
20 Correct 1020 ms 61924 KB Output is correct
21 Correct 680 ms 57736 KB Output is correct
22 Correct 674 ms 62080 KB Output is correct
23 Correct 1189 ms 60648 KB Output is correct
24 Correct 1029 ms 60720 KB Output is correct
25 Correct 1006 ms 60764 KB Output is correct
26 Correct 954 ms 63976 KB Output is correct
27 Correct 1033 ms 63860 KB Output is correct
28 Correct 1006 ms 60780 KB Output is correct
29 Execution timed out 4476 ms 176896 KB Time limit exceeded
30 Halted 0 ms 0 KB -