Submission #647711

#	Time	Username	Problem	Language	Result	Execution time	Memory
647711		DylanSmith	Monkey and Apple-trees (IZhO12_apple)	Java	0 / 100	698 ms	68220 KiB

apple

import java.util.*;
import java.io.*;
public class apple {
    static int SIZE = 3100000;
    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, Integer.MAX_VALUE);
                out.println(res);
                C = res;
            } else {
                int l = in.nextInt() - 1 + C, r = in.nextInt() - 1 + C;
                update(l, r, 0, 0, Integer.MAX_VALUE);
            }
        }
        
        out.close();
    }
    static int query(int L, int R, int current, int l, int r) {
        if (l > r) {
            return 0;
        }
        if (left[current] == -1) {
            left[current] = size++;
        }
        if (right[current] == -1) {
            right[current] = size++;
        }
        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, (int)(((long)l + r) / 2)) + query(L, R, right[current], (int)(((long)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;
        }
        if (left[current] == -1) {
            left[current] = size++;
        }
        if (right[current] == -1) {
            right[current] = size++;
        }
        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, (int)(((long)l + r) / 2));
        update(L, R, right[current], (int)(((long)l + r) / 2 + 1), r);
        merge(current, L, R);
    }
    static void push(int current, int l, int r) {
        if (upd[current]) {
            cnt[current] = r - l + 1;
            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: 0 / 100