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 intervals = new ArrayList<>(); for (int i = 0; i < intervalCount; i++) { intervals.add(new int[]{in.nextInt(), in.nextInt() + 1}); } Comparator comparator = new Comparator() { @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> queries = new ArrayList<>(); int[] queryAnswers = new int[queryCount]; int MAX = 1001000; Tree tree = new Tree(0, MAX); List 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); }*/ } }