Submission #647717

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
647717	2022-10-03T18:57:28 Z	DylanSmith	Monkey and Apple-trees (IZhO12_apple)	Java 11	100 / 100	892 ms	232608 KB

apple

import java.util.*;
import java.io.*;
public class apple {
    static int SIZE = 12000000;
    static int[] cnt = new int[SIZE], left = new int[SIZE], right = new int[SIZE];
    static boolean[] upd = new boolean[SIZE];
    static int size = 1;
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);

        Arrays.fill(left, -1);
        Arrays.fill(right, -1);
        
        int Q = in.nextInt();
        int C = 0;
        for (int q  = 0; q < Q; q++) {
            if (in.nextInt() == 1) {
                int l = in.nextInt() - 1 + C, r = in.nextInt() - 1 + C;
                int res = query(l, r, 0, 0, (1 << 30) - 1);
                out.println(res);
                C = res;
            } else {
                int l = in.nextInt() - 1 + C, r = in.nextInt() - 1 + C;
                update(l, r, 0, 0, (1 << 30) - 1);
            }
        }
        
        out.close();
    }
    static int query(int L, int R, int current, int l, int r) {
        if (l > r) {
            return 0;
        }
        push(current, l, r);
        if (R < l || r < L) {
            return 0;
        }
        if (L <= l && r <= R) {
            return cnt[current];
        }
        int res = query(L, R, left[current], l, (l + r) / 2) + query(L, R, right[current], (l + r) / 2 + 1, r);
        merge(current, l, r);
        return res;
    }
    static void update(int L, int R, int current, int l, int r) {
        if (l > r) {
            return;
        }
        push(current, l, r);
        if (R < l || r < L) {
            return;
        }
        if (L <= l && r <= R) {
            upd[current] = true;
            push(current, l, r);
            return;
        }
        update(L, R, left[current], l, (l + r) / 2);
        update(L, R, right[current], (l + r) / 2 + 1, r);
        merge(current, L, R);
    }
    static void push(int current, int l, int r) {
        if (l < r) {
            if (left[current] == -1) {
                left[current] = size++;
            }
            if (right[current] == -1) {
                right[current] = size++;
            }
        }
        if (upd[current]) {
            cnt[current] = r - l + 1;
            if (l < r) {
                upd[left[current]] = true;
                upd[right[current]] = true;
            }
            upd[current] = false;
        }
    }
    static void merge(int current, int l, int r) {
        cnt[current] = cnt[left[current]] + cnt[right[current]];
    }
    static class Reader {
        BufferedReader in;
        StringTokenizer st;
        public Reader() {
            in = new BufferedReader(new InputStreamReader(System.in));
            st = new StringTokenizer("");
        }
        public String nextLine() throws IOException {
            st = new StringTokenizer("");
            return in.readLine();
        }
        public String next() throws IOException {
            while (!st.hasMoreTokens()) {
                st = new StringTokenizer(in.readLine());
            }
            return st.nextToken();
        }
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
    public static void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	164 ms	162068 KB	Output is correct
2	Correct	168 ms	161716 KB	Output is correct
3	Correct	162 ms	161848 KB	Output is correct
4	Correct	430 ms	168632 KB	Output is correct
5	Correct	441 ms	169304 KB	Output is correct
6	Correct	422 ms	169380 KB	Output is correct
7	Correct	442 ms	169268 KB	Output is correct
8	Correct	657 ms	230188 KB	Output is correct
9	Correct	773 ms	230116 KB	Output is correct
10	Correct	765 ms	230204 KB	Output is correct
11	Correct	759 ms	230032 KB	Output is correct
12	Correct	767 ms	230304 KB	Output is correct
13	Correct	744 ms	230280 KB	Output is correct
14	Correct	732 ms	230152 KB	Output is correct
15	Correct	864 ms	230648 KB	Output is correct
16	Correct	850 ms	232440 KB	Output is correct
17	Correct	741 ms	232184 KB	Output is correct
18	Correct	764 ms	232316 KB	Output is correct
19	Correct	892 ms	232608 KB	Output is correct
20	Correct	858 ms	232456 KB	Output is correct