Submission #553191

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553191	2022-04-25T03:43:05 Z	tutest	Monkey and Apple-trees (IZhO12_apple)	Java 11	100 / 100	680 ms	15284 KB

apple

import java.io.*;
import java.util.StringTokenizer;

class FastIO {
    public static class InputClass {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputClass(InputStream inputSteam) {
            reader = new BufferedReader(new InputStreamReader(inputSteam));
            tokenizer = new StringTokenizer("");
        }

        public boolean hasNext() {
            try {
                while (!tokenizer.hasMoreTokens()) {
                    String line = reader.readLine();
                    if (line == null)
                        return false; // EOF
                    tokenizer = new StringTokenizer(line);
                }
            } catch (Exception e) {
            }
            return true;
        }

        public String next() {
            try {
                return hasNext() ? tokenizer.nextToken() : null;
            } catch (Exception e) {
            }
            return null;
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (Exception e) {
            }
            return null;
        }

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

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }

    public InputClass in;
    public PrintWriter out;

    public FastIO() {
        in = new InputClass(System.in);
        out = new PrintWriter(new OutputStreamWriter(System.out));
    }

    public FastIO(String inputFile, String outputFile) {
        try {
            in = inputFile == null ? new InputClass(System.in) : new InputClass(new FileInputStream(inputFile));
            out = outputFile == null ? new PrintWriter(new OutputStreamWriter(System.out)) :
                    new PrintWriter(new OutputStreamWriter(new FileOutputStream(outputFile)));
        } catch (Exception e) {
        }
    }
}


public class apple {

    // Tested by Leetcode 307
    static class SparseSegmentTreeRangeSum {
        private static class TreeNode {
            TreeNode left, right;
            long sum;
            long lazyValue;
        }

        private TreeNode root;
        private final long L, R;

        public SparseSegmentTreeRangeSum(long low, long high) {
            L = low;
            R = high;
            root = new TreeNode();
        }

        private void pushdown(TreeNode root, long L, long R, long value) {
            if (L >= R) return;
            if (root.left == null) root.left = new TreeNode();
            if (root.right == null) root.right = new TreeNode();
            if (root.lazyValue > 0) {
                long M = L + ((R - L) >>> 1);
                root.left.sum = (M - L + 1);
                root.left.lazyValue = value;

                root.right.sum = (R - (M + 1) + 1);
                root.right.lazyValue = value;

                root.lazyValue = 0;
            }
        }

        public void update(long low, long high, long value) {
            update(low, high, value, L, R, root);
        }

        private void update(long low, long high, long value, long L, long R, TreeNode root) {
            if (high < L || R < low) return;
            if (root.lazyValue > 0 || root.sum == R - L + 1) return;
            if (low <= L && R <= high) {
                root.sum = (R - L + 1) * value;
                root.lazyValue = value;
                return;
            }
            pushdown(root, L, R, 1);
            long M = L + ((R - L) >>> 1);
            update(low, high, value, L, M, root.left);
            update(low, high, value, M + 1, R, root.right);
            root.sum = root.left.sum + root.right.sum;
        }

        // Sum[low...high] inclusive
        public long getSum(long low, long high) {
            return getSum(low, high, L, R, root);
        }

        // low, high is range of query
        // L, R are range of TreeNode.
        private long getSum(long low, long high, long L, long R, TreeNode root) {
            if (low > high || root == null || high < L || R < low) return 0L;
            if (low <= L && R <= high) {
                return root.sum;
            }
            if (root.sum == R - L + 1) {
                return Math.min(high, R) - Math.max(low, L) + 1;
            }
            pushdown(root, L, R, 1);
            long M = L + ((R - L) >>> 1);
            return getSum(low, high, L, M, root.left) + getSum(low, high, M + 1, R, root.right);
        }
    }

    public static void main(String[] args) throws Exception {
        FastIO io = new FastIO();

        SparseSegmentTreeRangeSum tree = new SparseSegmentTreeRangeSum(1, 1_000_000_000 + 10);
        int M = io.in.nextInt();
        int D, X, Y, C;
        C = 0;
        while (M-- > 0) {
            D = io.in.nextInt();
            X = io.in.nextInt();
            Y = io.in.nextInt();

            if (D == 1) {
                C = (int) tree.getSum(X + C, Y + C);
                io.out.println(C);
            } else {
                tree.update(X + C, Y + C, 1);
            }
        }

        io.out.flush();
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	8400 KB	Output is correct
2	Correct	62 ms	8452 KB	Output is correct
3	Correct	67 ms	8224 KB	Output is correct
4	Correct	391 ms	13564 KB	Output is correct
5	Correct	491 ms	13724 KB	Output is correct
6	Correct	438 ms	13484 KB	Output is correct
7	Correct	465 ms	13532 KB	Output is correct
8	Correct	680 ms	14832 KB	Output is correct
9	Correct	579 ms	14932 KB	Output is correct
10	Correct	630 ms	15012 KB	Output is correct
11	Correct	618 ms	14952 KB	Output is correct
12	Correct	636 ms	14788 KB	Output is correct
13	Correct	625 ms	14976 KB	Output is correct
14	Correct	572 ms	15192 KB	Output is correct
15	Correct	626 ms	14976 KB	Output is correct
16	Correct	654 ms	15284 KB	Output is correct
17	Correct	588 ms	15028 KB	Output is correct
18	Correct	576 ms	15140 KB	Output is correct
19	Correct	649 ms	15260 KB	Output is correct
20	Correct	589 ms	14988 KB	Output is correct