Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- import java.util.Scanner;
- public class Main {
- public static class MyList implements Comparable<MyList> {
- private int y1;
- private int y2;
- private int x;
- private int value;
- MyList(int a, int b, int c, int d) {
- this.y1 = a;
- this.y2 = b;
- this.x = c;
- this.value = d;
- }
- @Override
- public int compareTo(MyList list) {
- return this.x - list.x;
- }
- }
- private static int[] t;
- private static int[] flags;
- // 0 - всё в порядке
- // 1 - нужно замодифицировать
- private static int[] toAdd;
- private static void push(int v) {
- if (flags[v] == 1) {
- t[v] += toAdd[v];
- flags[v] = 0;
- int left = v * 2 + 1;
- if (left + 1 < t.length) {
- if (flags[left] == 0) {
- toAdd[left] = toAdd[v];
- } else {
- toAdd[left] += toAdd[v];
- }
- flags[left] = 1;
- left++;
- if (flags[left] == 0) {
- toAdd[left] = toAdd[v];
- } else {
- toAdd[left] += toAdd[v];
- }
- flags[left] = 1;
- }
- }
- toAdd[v] = 0;
- }
- private static void setMax(int i) {
- if (2 * i + 2 < t.length) {
- push(i * 2 + 1);
- push(i * 2 + 2);
- t[i] = Math.max(t[i * 2 + 1], t[i * 2 + 2]);
- }
- }
- private static int[] getMax(int v, int left, int right, int a, int b) {
- if (left > b || right < a) return new int[]{Integer.MIN_VALUE, 0};
- push(v);
- if (a <= left && right <= b) return new int[]{t[v], v};
- int mid = (left + right) / 2;
- int t1[] = getMax(v * 2 + 1, left, mid, a, b);
- int t2[] = getMax(v * 2 + 2, mid + 1, right, a, b);
- if (t1[0] > t2[0]) return t1;
- return t2;
- }
- private static void actionInRange(int v, int left, int right, int a, int b, int value) {
- if (left > b || right < a)
- return;
- if (a <= left && right <= b) {
- if (flags[v] == 1) {
- toAdd[v] += value;
- } else {
- toAdd[v] = value;
- flags[v] = 1;
- }
- push(v);
- } else {
- push(v);
- int mid = (left + right) / 2;
- actionInRange(v * 2 + 1, left, mid, a, b, value);
- actionInRange(v * 2 + 2, mid + 1, right, a, b, value);
- setMax(v);
- }
- }
- public static void main(String[] args) {
- int max = 0;
- int ansX = 0;
- int ansY = 0;
- Scanner in = new Scanner(System.in);
- int n = in.nextInt();
- int newN = 262144 * 2;
- int len = newN * 2 - 1;
- t = new int[len];
- flags = new int[len];
- toAdd = new int[len];
- MyList megaList[] = new MyList[n * 2];
- int delta = 200004;
- for (int i = 0; i < n; i++) {
- int x1 = in.nextInt() + delta;
- int y1 = in.nextInt() + delta;
- int x2 = in.nextInt() + delta;
- int y2 = in.nextInt() + delta;
- megaList[i * 2] = new MyList(y1, y2, x1, 1);
- megaList[i * 2 + 1] = new MyList(y1, y2, x2, -1);
- }
- Arrays.sort(megaList);
- for (int i = 0; i < 2 * n; i++) {
- actionInRange(0, 0, newN - 1, megaList[i].y1, megaList[i].y2, megaList[i].value);
- int cur[] = getMax(0, 0, newN - 1, 0, newN - 1);
- if (cur[0] > max) {
- max = cur[0];
- ansX = megaList[i].x;
- ansY = getPosOfMaxByV(cur[1]) - newN + 1;
- }
- }
- System.out.println(max);
- System.out.print((ansX - delta) + " " + (ansY - delta));
- }
- private static int getPosOfMaxByV(int v) {
- int left = v * 2 + 1;
- if (left + 1 < t.length) {
- push(left);
- push(left + 1);
- if (t[left] > t[left + 1]) return getPosOfMaxByV(left);
- return getPosOfMaxByV(left + 1);
- }
- return v;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement