#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <chrono>

int main() {

    std::vector<int> x;
    std::vector<int> y;
    int l, r;
    long t = 0;
    long t2 = 0;
    int c = 0;

    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
    std::ifstream f("b");
    while (f >> l >> r) {
        x.push_back(l);
        y.push_back(r);
    }

    std::sort(x.begin(), x.end());
    std::sort(y.begin(), y.end());
    
    for (size_t i = 0; i < 4000000; i++) {
        t += std::abs(x[i] - y[i]);
    }

    auto p = y.begin();
    for (size_t i = 0; i < 4000000; i++) {
	   auto b = std::lower_bound(p, y.end(), x[i]);
	   auto u = std::upper_bound(p, y.end(), x[i]);
	   int c = u - b;
	   t2 += x[i] * c;
	   p = b;
    }

    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

    std::cout << "Part 1: " << t << "\nPart 2: " << t2 << "\n";
    std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << " microseconds" << std::endl;

    return 0;
}
