Advertisement
IzhanVarsky

Untitled

Mar 24th, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.27 KB | None | 0 0
  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.  
  6.     public static class MyList implements Comparable<MyList> {
  7.         private int y1;
  8.         private int y2;
  9.         private int x;
  10.         private int value;
  11.  
  12.         MyList(int a, int b, int c, int d) {
  13.             this.y1 = a;
  14.             this.y2 = b;
  15.             this.x = c;
  16.             this.value = d;
  17.         }
  18.  
  19.         @Override
  20.         public int compareTo(MyList list) {
  21.             return this.x - list.x;
  22.         }
  23.     }
  24.  
  25.     private static int[] t;
  26.     private static int[] flags;
  27.     // 0 - всё в порядке
  28.     // 1 - нужно замодифицировать
  29.     private static int[] toAdd;
  30.  
  31.     private static void push(int v) {
  32.         if (flags[v] == 1) {
  33.             t[v] += toAdd[v];
  34.             flags[v] = 0;
  35.             int left = v * 2 + 1;
  36.             if (left + 1 < t.length) {
  37.                 if (flags[left] == 0) {
  38.                     toAdd[left] = toAdd[v];
  39.                 } else {
  40.                     toAdd[left] += toAdd[v];
  41.                 }
  42.                 flags[left] = 1;
  43.                 left++;
  44.                 if (flags[left] == 0) {
  45.                     toAdd[left] = toAdd[v];
  46.                 } else {
  47.                     toAdd[left] += toAdd[v];
  48.                 }
  49.                 flags[left] = 1;
  50.             }
  51.         }
  52.         toAdd[v] = 0;
  53.     }
  54.  
  55.     private static void setMax(int i) {
  56.         if (2 * i + 2 < t.length) {
  57.             push(i * 2 + 1);
  58.             push(i * 2 + 2);
  59.             t[i] = Math.max(t[i * 2 + 1], t[i * 2 + 2]);
  60.         }
  61.     }
  62.  
  63.     private static int[] getMax(int v, int left, int right, int a, int b) {
  64.         if (left > b || right < a) return new int[]{Integer.MIN_VALUE, 0};
  65.         push(v);
  66.         if (a <= left && right <= b) return new int[]{t[v], v};
  67.         int mid = (left + right) / 2;
  68.         int t1[] = getMax(v * 2 + 1, left, mid, a, b);
  69.         int t2[] = getMax(v * 2 + 2, mid + 1, right, a, b);
  70.         if (t1[0] > t2[0]) return t1;
  71.         return t2;
  72.     }
  73.  
  74.     private static void actionInRange(int v, int left, int right, int a, int b, int value) {
  75.         if (left > b || right < a)
  76.             return;
  77.         if (a <= left && right <= b) {
  78.             if (flags[v] == 1) {
  79.                 toAdd[v] += value;
  80.             } else {
  81.                 toAdd[v] = value;
  82.                 flags[v] = 1;
  83.             }
  84.             push(v);
  85.         } else {
  86.             push(v);
  87.             int mid = (left + right) / 2;
  88.             actionInRange(v * 2 + 1, left, mid, a, b, value);
  89.             actionInRange(v * 2 + 2, mid + 1, right, a, b, value);
  90.             setMax(v);
  91.         }
  92.     }
  93.  
  94.     public static void main(String[] args) {
  95.         int max = 0;
  96.         int ansX = 0;
  97.         int ansY = 0;
  98.         Scanner in = new Scanner(System.in);
  99.         int n = in.nextInt();
  100.         int newN = 262144 * 2;
  101.         int len = newN * 2 - 1;
  102.         t = new int[len];
  103.         flags = new int[len];
  104.         toAdd = new int[len];
  105.         MyList megaList[] = new MyList[n * 2];
  106.         int delta = 200004;
  107.         for (int i = 0; i < n; i++) {
  108.             int x1 = in.nextInt() + delta;
  109.             int y1 = in.nextInt() + delta;
  110.             int x2 = in.nextInt() + delta;
  111.             int y2 = in.nextInt() + delta;
  112.             megaList[i * 2] = new MyList(y1, y2, x1, 1);
  113.             megaList[i * 2 + 1] = new MyList(y1, y2, x2, -1);
  114.         }
  115.         Arrays.sort(megaList);
  116.         for (int i = 0; i < 2 * n; i++) {
  117.             actionInRange(0, 0, newN - 1, megaList[i].y1, megaList[i].y2, megaList[i].value);
  118.             int cur[] = getMax(0, 0, newN - 1, 0, newN - 1);
  119.             if (cur[0] > max) {
  120.                 max = cur[0];
  121.                 ansX = megaList[i].x;
  122.                 ansY = getPosOfMaxByV(cur[1]) - newN + 1;
  123.             }
  124.         }
  125.         System.out.println(max);
  126.         System.out.print((ansX - delta) + " " + (ansY - delta));
  127.     }
  128.  
  129.     private static int getPosOfMaxByV(int v) {
  130.         int left = v * 2 + 1;
  131.         if (left + 1 < t.length) {
  132.             push(left);
  133.             push(left + 1);
  134.             if (t[left] > t[left + 1]) return getPosOfMaxByV(left);
  135.             return getPosOfMaxByV(left + 1);
  136.         }
  137.         return v;
  138.     }
  139. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement