Submission #553186

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553186	2022-04-25T03:17:16 Z	tutest	Monkey and Apple-trees (IZhO12_apple)	Java 11	0 / 100	2000 ms	196148 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;
            }
            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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	8336 KB	Output is correct
2	Correct	66 ms	8568 KB	Output is correct
3	Correct	67 ms	8696 KB	Output is correct
4	Correct	425 ms	17244 KB	Output is correct
5	Correct	554 ms	18264 KB	Output is correct
6	Correct	431 ms	18036 KB	Output is correct
7	Correct	540 ms	18236 KB	Output is correct
8	Correct	930 ms	60512 KB	Output is correct
9	Correct	1228 ms	100580 KB	Output is correct
10	Correct	1270 ms	106004 KB	Output is correct
11	Correct	1287 ms	110212 KB	Output is correct
12	Correct	1307 ms	111676 KB	Output is correct
13	Correct	1457 ms	136132 KB	Output is correct
14	Correct	1522 ms	138020 KB	Output is correct
15	Correct	1911 ms	193500 KB	Output is correct
16	Correct	1920 ms	194696 KB	Output is correct
17	Correct	1538 ms	139020 KB	Output is correct
18	Correct	1438 ms	139420 KB	Output is correct
19	Execution timed out	2009 ms	196148 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-