Submission #553184

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553184	2022-04-25T03:13:37 Z	tutest	Monkey and Apple-trees (IZhO12_apple)	Java 11	0 / 100	2000 ms	195764 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) 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	8252 KB	Output is correct
2	Correct	70 ms	8336 KB	Output is correct
3	Correct	83 ms	8276 KB	Output is correct
4	Correct	418 ms	17460 KB	Output is correct
5	Correct	556 ms	18576 KB	Output is correct
6	Correct	453 ms	18440 KB	Output is correct
7	Correct	556 ms	18600 KB	Output is correct
8	Correct	946 ms	60704 KB	Output is correct
9	Correct	1242 ms	100724 KB	Output is correct
10	Correct	1231 ms	105860 KB	Output is correct
11	Correct	1267 ms	110420 KB	Output is correct
12	Correct	1240 ms	111724 KB	Output is correct
13	Correct	1444 ms	136172 KB	Output is correct
14	Correct	1460 ms	137736 KB	Output is correct
15	Correct	1875 ms	193172 KB	Output is correct
16	Correct	1907 ms	194020 KB	Output is correct
17	Correct	1528 ms	138772 KB	Output is correct
18	Correct	1544 ms	138612 KB	Output is correct
19	Execution timed out	2001 ms	195764 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-