Submission #1262764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262764		uranium235	trapezoid (balkan11_trapezoid)	Java	25 / 100	834 ms	118324 KiB

trapezoid

//package ojuz;

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

public class trapezoid {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        int[][] traps = new int[n][];
        Set<Integer> all = new HashSet<>(n);
        for (int i = 0; i < n; i++) {
            String[] line = reader.readLine().split(" ");
            int a = Integer.parseInt(line[0]), b = Integer.parseInt(line[1]), c = Integer.parseInt(line[2]), d = Integer.parseInt(line[3]);
            all.add(a);
            all.add(b);
            all.add(c);
            all.add(d);
            traps[i] = new int[] { a, b, c, d, i };
        }
        int[][] alt = traps.clone();
        Integer[] arr = all.toArray(new Integer[0]);
        Arrays.sort(arr);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) map.put(arr[i], i);
        for (int[] a : traps) for (int i = 0; i < 4; i++) a[i] = map.get(a[i]);

        Arrays.sort(traps, Comparator.comparingInt(i -> i[0]));
        Arrays.sort(alt, Comparator.comparingInt(i -> i[1]));

        SegTree tree = new SegTree(4 * n);
        int ptr = 0;
        int[] x = new int[n], y = new int[n];
        int[] temp = new int[2];
        for (int[] trap : traps) {
            while (ptr < n && alt[ptr][1] < trap[0]) {
                int idx = alt[ptr][4];
                tree.upd(alt[ptr][3], x[idx], y[idx]);
                ptr++;
            }
            tree.qry(0, trap[2] + 1, temp);
            x[trap[4]] = temp[0] + 1;
            y[trap[4]] = temp[1];
        }

        int l = -1, r = -1;
        for (int i = 0; i < n; i++) {
            if (l > x[i]) continue;
            if (l == x[i]) r = (r + y[i]) % 30013;
            else r = y[i];
            l = Math.max(l, x[i]);
        }

        System.out.println(l + " " + r);
    }

    static class SegTree {
        public final int[] a, b;
        public final int n;
        public SegTree(int n) {
            this.n = n;
            this.a = new int[2 * n];
            this.b = new int[2 * n];
            Arrays.fill(b, 1);
        }
        public void upd(int i, int x, int y) {
            for (a[i += n] = x, b[i] = y; i > 1; i /= 2) {
                a[i / 2] = Math.max(a[i], a[i ^ 1]);
                if (a[i] == a[i ^ 1]) b[i / 2] = (b[i] + b[i ^ 1]) % 30013;
                else if (a[i] > a[i ^ 1]) b[i / 2] = b[i];
                else b[i / 2] = b[i ^ 1];
            }
        }
        public void qry(int l, int r, int[] ret) {
            Arrays.fill(ret, -1);
            for (l += n, r += n; l < r; l /= 2, r /= 2) {
                if (l % 2 == 1) merge(ret, l++);
                if (r % 2 == 1) merge(ret, --r);
            }
        }
        public void merge(int[] ret, int i) {
            if (ret[0] == a[i]) ret[1] = (ret[1] + b[i]) % 30013;
            else if (ret[0] < a[i]) ret[1] = b[i];
            ret[0] = Math.max(ret[0], a[i]);
        }
    }
}

• Subtask 1: 25 / 100