aoc 2025 d5

#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#define ll unsigned long long

std::vector<string> split(std::string& s, std::string&& delim) {
    std::vector<string> tokens;
    int start = 0;
    int end;
    while( (end = s.find(delim, start)) != string::npos) {
        tokens.push_back(s.substr(start, end - start));
        start = end + delim.length();
    }
    if(start < s.length()) {
        tokens.push_back(s.substr(start));
    }
    return tokens;
}


ll solve(std::vector<ll> nums, std::vector<std::vector<ll>> ranges) {
    ll ans = 0;
    for(const auto& num : nums) {
        for(const auto& range : ranges) {
            if(num >= range[0] && num <= range[1]) {
                ans += 1;
                break;
            }
        }
    }
    return ans;
}

struct Marker {
    ll val;
    int type;
    bool operator<(const Marker& other) const {
        return val == other.val ? (type < other.type) : (val < other.val);
    }
};

ll solve2(std::vector<std::vector<ll>> ranges) {
    ll ans = 0;
    std::vector<Marker> markers;
    for(const auto& range : ranges) {
        markers.push_back({range[0],0});
        markers.push_back({range[1],1});
    }
    std::sort(markers.begin(), markers.end());

    int counter = 0;
    int start = 0;
    for(int i=0; i<markers.size(); i++) {
        if(counter == 0) {
            start = i;
        }
        counter = (markers[i].type == 0) ? counter + 1 : counter - 1;
        if(counter == 0) {
            ans += (markers[i].val - markers[start].val + 1);
        }
    }
    return ans;
}


int main() {
    ifstream inputFile("../data/day5.txt");
    std::string line;
    std::vector<std::vector<ll>> ranges;
    std::vector<ll> queries;
    bool readRanges = true;
    while(std::getline(inputFile, line)) {
        if(line == "") {
            readRanges = false;
            continue;
        }
        if(readRanges) {
            vector<string> strNums = split(line, "-");
            ranges.push_back({std::stoull(strNums[0]), std::stoull(strNums[1])});
        }
        else {
            queries.push_back(std::stoull(line));
        }
    }
    std::cout << solve2(ranges) << std::endl;
    return 0;
}