SRM277, div2 level3, UnionOfIntervals. Solution using sweepline

topcoder_277_3.cpp

#include <bits/stdc++.h>
using namespace std;
class UnionOfIntervals {
public:
    int nthElement(vector <int> lowerBound, vector <int> upperBound, int n) {
        vector< pair<int, int> > events;
        for (int i = 0; i < lowerBound.size(); ++i) {
            events.push_back( make_pair(lowerBound[i], 1) );
            events.push_back( make_pair(upperBound[i]+1, -1) );
        }
        sort(events.begin(), events.end());
        long long h = 1;
        auto cur = events.front();
        auto prev = cur;
        for (int i = 1; i < events.size(); ++i) {
            prev = cur;
            cur = events[i];

            long long d = h * (1LL*cur.first - prev.first);
            if (n < d) {
                return prev.first + n/h;
            } else {
                n -= d;
            } 
            h += cur.second;
        }
		return -1;
    }
};