Submission #553182

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553182	2022-04-25T02:58:55 Z	tutest	Monkey and Apple-trees (IZhO12_apple)	Java 11	100 / 100	1984 ms	197808 KB

apple

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

import java.util.*;

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 (root != null && L != R) {
                if (root.left == null) root.left = new TreeNode();
                if (root.right == null) root.right = new TreeNode();
            }
            if (root != null && root.lazyValue > 0 && L != R) {
                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) return 0L;
            if (low <= L && R <= high) {
                return root.sum;
            }
            pushdown(root, L, R, 1);
            long M = L + ((R - L) >>> 1);
            if (high <= M) {
                return getSum(low, high, L, M, root.left);
            } else if (M + 1 <= low) {
                return getSum(low, high, M + 1, R, root.right);
            } else {
                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	8564 KB	Output is correct
2	Correct	68 ms	8284 KB	Output is correct
3	Correct	73 ms	8128 KB	Output is correct
4	Correct	417 ms	17260 KB	Output is correct
5	Correct	525 ms	18500 KB	Output is correct
6	Correct	474 ms	18456 KB	Output is correct
7	Correct	538 ms	18340 KB	Output is correct
8	Correct	933 ms	61272 KB	Output is correct
9	Correct	1218 ms	102504 KB	Output is correct
10	Correct	1262 ms	107312 KB	Output is correct
11	Correct	1287 ms	112008 KB	Output is correct
12	Correct	1254 ms	113312 KB	Output is correct
13	Correct	1458 ms	137948 KB	Output is correct
14	Correct	1467 ms	139596 KB	Output is correct
15	Correct	1969 ms	195208 KB	Output is correct
16	Correct	1984 ms	196004 KB	Output is correct
17	Correct	1535 ms	140560 KB	Output is correct
18	Correct	1479 ms	140784 KB	Output is correct
19	Correct	1924 ms	197752 KB	Output is correct
20	Correct	1880 ms	197808 KB	Output is correct