Advertisement
IzhanVarsky

Untitled

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