oj.uz

Submission #284179

# Submission time Handle Problem Language Result Execution time Memory
284179 2020-08-27T00:58:03 Z ijxjdjd Triple Jump (JOI19_jumps) Java 11
46 / 100
 4000 ms 192196 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.TreeSet;
import java.util.ArrayList;
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();
            ArrayList<Integer> A = new ArrayList<Integer>();
            int[] F = new int[N];
            for (int i = 0; i < N; i++) {
                F[i] = in.nextInt();
                A.add(i);
            }
            Collections.sort(A, new Comparator<Integer>() {

                public int compare(Integer integer, Integer t1) {
                    return Integer.compare(F[integer], F[t1]);
                }
            });
            TreeSet<Integer> set = new TreeSet<>();
            ArrayList<Integer>[] pair = new ArrayList[N];
            for (int i = 0; i < N; i++) {
                pair[i] = new ArrayList<>();
            }
            for (int i = N - 1; i >= 0; i--) {
                int cur = A.get(i);
                if (set.lower(cur) != null) {
                    pair[set.lower(cur)].add(cur);
                }
                if (set.higher(cur) != null) {
                    pair[cur].add(set.higher(cur));
                }
                set.add(cur);
            }
            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 85 ms 10592 KB Output is correct
2 Correct 100 ms 10600 KB Output is correct
3 Correct 98 ms 10608 KB Output is correct
4 Correct 102 ms 10932 KB Output is correct
5 Correct 108 ms 10660 KB Output is correct
6 Correct 113 ms 10652 KB Output is correct
7 Correct 102 ms 10756 KB Output is correct
8 Correct 100 ms 10956 KB Output is correct
9 Correct 107 ms 10844 KB Output is correct
10 Correct 104 ms 10744 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 10592 KB Output is correct
2 Correct 100 ms 10600 KB Output is correct
3 Correct 98 ms 10608 KB Output is correct
4 Correct 102 ms 10932 KB Output is correct
5 Correct 108 ms 10660 KB Output is correct
6 Correct 113 ms 10652 KB Output is correct
7 Correct 102 ms 10756 KB Output is correct
8 Correct 100 ms 10956 KB Output is correct
9 Correct 107 ms 10844 KB Output is correct
10 Correct 104 ms 10744 KB Output is correct
11 Correct 1740 ms 107048 KB Output is correct
12 Correct 1551 ms 107780 KB Output is correct
13 Correct 1444 ms 107240 KB Output is correct
14 Correct 1508 ms 108080 KB Output is correct
15 Correct 1756 ms 114532 KB Output is correct
16 Correct 1651 ms 106956 KB Output is correct
17 Correct 1620 ms 107752 KB Output is correct
18 Correct 1470 ms 106484 KB Output is correct
19 Correct 1732 ms 108012 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1789 ms 91280 KB Output is correct
2 Correct 1101 ms 99232 KB Output is correct
3 Correct 1068 ms 92552 KB Output is correct
4 Correct 1815 ms 92220 KB Output is correct
5 Correct 1987 ms 92744 KB Output is correct
6 Correct 1952 ms 91296 KB Output is correct
7 Correct 1936 ms 95708 KB Output is correct
8 Correct 2000 ms 95872 KB Output is correct
9 Correct 2052 ms 93388 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 10592 KB Output is correct
2 Correct 100 ms 10600 KB Output is correct
3 Correct 98 ms 10608 KB Output is correct
4 Correct 102 ms 10932 KB Output is correct
5 Correct 108 ms 10660 KB Output is correct
6 Correct 113 ms 10652 KB Output is correct
7 Correct 102 ms 10756 KB Output is correct
8 Correct 100 ms 10956 KB Output is correct
9 Correct 107 ms 10844 KB Output is correct
10 Correct 104 ms 10744 KB Output is correct
11 Correct 1740 ms 107048 KB Output is correct
12 Correct 1551 ms 107780 KB Output is correct
13 Correct 1444 ms 107240 KB Output is correct
14 Correct 1508 ms 108080 KB Output is correct
15 Correct 1756 ms 114532 KB Output is correct
16 Correct 1651 ms 106956 KB Output is correct
17 Correct 1620 ms 107752 KB Output is correct
18 Correct 1470 ms 106484 KB Output is correct
19 Correct 1732 ms 108012 KB Output is correct
20 Correct 1789 ms 91280 KB Output is correct
21 Correct 1101 ms 99232 KB Output is correct
22 Correct 1068 ms 92552 KB Output is correct
23 Correct 1815 ms 92220 KB Output is correct
24 Correct 1987 ms 92744 KB Output is correct
25 Correct 1952 ms 91296 KB Output is correct
26 Correct 1936 ms 95708 KB Output is correct
27 Correct 2000 ms 95872 KB Output is correct
28 Correct 2052 ms 93388 KB Output is correct
29 Execution timed out 4141 ms 192196 KB Time limit exceeded
30 Halted 0 ms 0 KB -