From 956e0d50a9f0bea2752cc1a84ec26bc72416ce60 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 9 Dec 2018 21:03:28 -0600
Subject: Organize lottery done!

---
 PlaygroundCpp/Sources/Playground.cpp | 128 ++++++++++++++++++++++-------------
 1 file changed, 82 insertions(+), 46 deletions(-)

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index aff2024..dbb916c 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,61 +1,97 @@
-#include <vector>
+#include <algorithm>
 #include <iostream>
+#include <climits>
+#include <vector>
 //#include <gtest/gtest.h>
 
 using std::vector;
 
-long mergeInversionCount(vector<int> &B, vector<int> &C, vector<int> &D) {
-	long count = 0;
-	while (B.size() != 0 && C.size() != 0) {
-		int b = B[0];
-		int c = C[0];
-		if (b <= c) {
-			D.push_back(b);
-			B.erase(B.begin());
-		} else {
-			count += B.size();
-			D.push_back(c);
-			C.erase(C.begin());
-		}
+struct Segment {
+	int start, end;
+	bool operator==(const Segment &s1) {
+		return (start == s1.start && end == s1.end);
 	}
-	D.insert(D.end(), B.begin(), B.end());
-	D.insert(D.end(), C.begin(), C.end());
-	return count;
+};
+
+bool sortSeg(Segment i, Segment j) {
+	if (i.start == j.start) {
+		return i.end < j.end;
+	}
+	return i.start < j.start;
 }
-long getInversionCountFromList(vector<int> &A, vector<int> &D) {
-	long numberOfInversions = 0;
-	if (A.size() == 1) {
-		D.push_back(A[0]);
-		return 0;
+vector<int> fast_count_segments(vector<int> starts, vector<int> ends,
+		vector<int> points) {
+	// Implement algo described here, really clever:
+	// https://www.coursera.org/learn/algorithmic-toolbox/discussions/all/threads/QJ1jK9wNEeWdPBL2iFTrAw/replies/Ihiw4txhEeWK5g7mfcS2Xw/comments/oyAMaeIiEeWyqwpvChh66Q
+	// l->1, p->2, r->3 for Segment.end property
+	vector<Segment> s(starts.size() + ends.size() + points.size());
+	vector<Segment> p(points.size());
+	Segment tempSeg;
+	for (int i = 0; i < p.size(); i++) {
+		tempSeg = {points[i], i};
+		p[i] = tempSeg;
+		tempSeg = {points[i], 2};
+		s[2 * starts.size() + i] = tempSeg;
+	}
+	for (int i = 0; i < starts.size(); i++) {
+		tempSeg = {starts[i], 1};
+		s[i] = tempSeg;
+		tempSeg = {ends[i], 3};
+		s[i + starts.size()] = tempSeg;
+	}
+	std::sort(s.begin(), s.end(), sortSeg);
+	std::sort(p.begin(), p.end(), sortSeg);
+	vector<int> results(points.size());
+	int count = 0;
+	int j = 0;
+	for (int i = 0; i < s.size(); i++) {
+		if (s[i].end == 1) {
+			count = count + 1;
+		}
+		if (s[i].end == 2) {
+			results[j] = count;
+			j = j + 1;
+		}
+		if (s[i].end == 3) {
+			count = count - 1;
+		}
+	}
+	vector<int> finalResults(points.size());
+	for (int i = 0; i < finalResults.size(); i++) {
+		finalResults[p[i].end] = results[i];
 	}
-	int m = A.size() / 2;
-	vector<int> D1;
-	vector<int>::const_iterator first = A.begin();
-	vector<int>::const_iterator last = A.begin() + m;
-	vector<int> newVec(first, last);
-	numberOfInversions += getInversionCountFromList(newVec, D1);
-	vector<int> D2;
-	vector<int>::const_iterator ffirst = A.begin() + m;
-	vector<int>::const_iterator llast = A.end();
-	vector<int> newVecc(ffirst, llast);
-	numberOfInversions += getInversionCountFromList(newVecc, D2);
-	long mergeCount = mergeInversionCount(D1, D2, D);
-	return numberOfInversions + mergeCount;
+	return finalResults;
 }
 
-//TEST(InversionCount, test1) {
-//	vector<int> a = { 2, 3, 9, 2, 2 };
-//	vector<int> result(5);
-//	ASSERT_EQ(4, getInversionCountFromList(a, result));
+//TEST(SortSegment, Sort1) {
+//	vector<int> starts = { 0, 7 };
+//	vector<int> ends = { 5, 10 };
+//	vector<int> points = { 1, 6, 11 };
+//	vector<int> results = { 1, 0, 0 };
+//
+//	vector<int> cnt = fast_count_segments(starts, ends, points);
+//
+//	ASSERT_EQ(cnt[0], 1);
+//	ASSERT_EQ(cnt[1], 0);
+//	ASSERT_EQ(cnt[2], 0);
+//	ASSERT_EQ(cnt.size(), 3);
 //}
 
 int main() {
-  int n;
-  std::cin >> n;
-  vector<int> a(n);
-  for (size_t i = 0; i < a.size(); i++) {
-    std::cin >> a[i];
+  int n, m;
+  std::cin >> n >> m;
+  vector<int> starts(n), ends(n);
+  for (size_t i = 0; i < starts.size(); i++) {
+    std::cin >> starts[i] >> ends[i];
+  }
+  vector<int> points(m);
+  for (size_t i = 0; i < points.size(); i++) {
+    std::cin >> points[i];
+  }
+  //use fast_count_segments
+  vector<int> cnt = fast_count_segments(starts, ends, points);
+  for (size_t i = 0; i < cnt.size(); i++) {
+    std::cout << cnt[i] << ' ';
   }
-  vector<int> b(a.size());
-  std::cout << getInversionCountFromList(a, b) << '\n';
 }
+
-- 
cgit v1.2.3