Submission #553189

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553189	2022-04-25T03:27:49 Z	tutest	Monkey and Apple-trees (IZhO12_apple)	Java 11	100 / 100	1370 ms	138760 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 (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	66 ms	8320 KB	Output is correct
2	Correct	64 ms	8112 KB	Output is correct
3	Correct	72 ms	8360 KB	Output is correct
4	Correct	384 ms	15672 KB	Output is correct
5	Correct	504 ms	16504 KB	Output is correct
6	Correct	407 ms	16676 KB	Output is correct
7	Correct	488 ms	16596 KB	Output is correct
8	Correct	745 ms	40920 KB	Output is correct
9	Correct	886 ms	60708 KB	Output is correct
10	Correct	945 ms	63016 KB	Output is correct
11	Correct	945 ms	73416 KB	Output is correct
12	Correct	948 ms	74872 KB	Output is correct
13	Correct	962 ms	82216 KB	Output is correct
14	Correct	930 ms	83140 KB	Output is correct
15	Correct	1349 ms	136660 KB	Output is correct
16	Correct	1358 ms	137908 KB	Output is correct
17	Correct	932 ms	85456 KB	Output is correct
18	Correct	964 ms	86228 KB	Output is correct
19	Correct	1370 ms	137940 KB	Output is correct
20	Correct	1343 ms	138760 KB	Output is correct