Submission #284183

#	Time	Username	Problem	Language	Result	Execution time	Memory
284183		ijxjdjd	Triple Jump (JOI19_jumps)	Java	Compilation error	0 ms	0 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.util.Comparator;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    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());
        }

    }
}

Compilation message (stderr)

jumps.java:20: error: class Main is public, should be declared in a file named Main.java
public class Main {
       ^
1 error