java-competitive/archive/2017.09/2017.09.15 - unsorted/ValeraOtrezki.java

package chelper;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

import io.InputReader;
import io.OutputWriter;
import misc.SimpleSavingChelperSolution;


public class ValeraOtrezki extends SimpleSavingChelperSolution {

  public void solve(int testNumber, InputReader in, OutputWriter out) {
    wrapSolve(testNumber, in, out);
  }

  class Tree {
    final int l, r;

    final int m;

    int sum = 0;

    Tree cl, cr;

    public Tree(int l, int r) {
      this.l = l;
      this.r = r;

      m = (l + r) / 2;

//      if (r - l == 1) {
//        return;
//      }

//      cl = new Tree(l, m);
//      cr = new Tree(m, r);
    }

    void add(int x) {
      sum += 1;

      if (r - l == 1) {
        return;
      }

      if (x < m) {
        if (cl == null) {
          cl = new Tree(l, m);
        }
        cl.add(x);
      } else {
        if (cr == null) {
          cr = new Tree(m, r);
        }
        cr.add(x);
      }
    }

    int get(int ll, int rr) {
      if (ll == l && rr == r) {
        return sum;
      }

      int res = 0;

      if (ll < m && cl != null) {
        res += cl.get(ll, Math.min(m, rr));
      }

      if (rr > m && cr != null) {
        res += cr.get(Math.max(m, ll), rr);
      }

      return res;
    }
  }

  @Override
  public void solve(int testNumber) {
    int intervalCount = in.nextInt();
    int queryCount = in.nextInt();

    List<int[]> intervals = new ArrayList<>();

    for (int i = 0; i < intervalCount; i++) {
      intervals.add(new int[]{in.nextInt(), in.nextInt() + 1});
    }

    Comparator<int[]> comparator = new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        int t = Integer.compare(o1[1], o2[1]);
        if (t != 0) {
          return t;
        }
        return Integer.compare(o1[0], o2[0]);
      }
    };

    Collections.sort(intervals, comparator);

//    List<List<Integer>> queries = new ArrayList<>();
    int[] queryAnswers = new int[queryCount];

    int MAX = 1001000;
    Tree tree = new Tree(0, MAX);

    List<int[]> points = new ArrayList<>();

//    Tree tree = new Tree(0, 1000);

    for (int i = 0; i < queryCount; i++) {
      int pointCount = in.nextInt();
//      queries.add(new ArrayList<>());

      int prev = 0;

      for (int j = 0; j < pointCount; j++) {
        int point = in.nextInt();
//        queries.get(i).add(point);
        points.add(new int[]{i, point, prev});
        prev = point;

//        tree.add(point);
      }

      points.add(new int[]{i, MAX - 1, prev});
    }

    Collections.sort(points, comparator);


    int nextInterval = 0;

    for (int[] point : points) {
      int queryI = point[0];
      int x = point[1];
      int prevX = point[2];

      while (nextInterval < intervalCount && intervals.get(nextInterval)[1] <= x) {
        tree.add(intervals.get(nextInterval)[0]);

        nextInterval++;
      }

      int matching = tree.get(prevX + 1, x);

      queryAnswers[queryI] += matching;
    }

    for (int i = 0; i < queryCount; i++) {
      out.println(intervalCount - queryAnswers[i]);
    }

    /*Random random = new Random();

    for (int i = 0; i < 100; i++) {
      int l = random.nextInt(100) + 1;
      int r = random.nextInt(100) + 1;

      if (r < l) {
        int t = l;
        l = r;
        r = t;
      }

      int res1 = tree.get(l, r);
      int res2 = 0;

      for (int[] j : points) {
        if (j[1] < r && j[1] >= l) {
          res2++;
        }
      }

      out.println(res1 + " " + res2);
    }*/
  }
}