Solution for Visiting Manhattan. [https://www.hackerrank.com/contests/booking-womenintech/challenges/visiting-manhattan] O(L+H+X+Y)

visiting_manhattan.cpp

#include <iostream>
#include <limits>
#include <vector>

using namespace std;

vector<long long> sum_distances(const vector<int> & a){ // O(|a|)

    vector<long long> result(a.size(),0);
    long long A = 0;
    long long B = 0;
    for(int i = 0; i < a.size(); ++i){ // O(|a|)
        result[i] = B;
        A += a[i];
        B += A;
    }
    A = 0;
    B = 0;
    for(int i = a.size()-1; i >=0; --i){ // O(|a|)
        result[i] += B;
        A += a[i];
        B += A;
    }
    return result;
}

int main() {
    int X, Y, L, H;
    cin >> X >> Y >> L >> H;

    vector<int> x_landmarks(X, 0);
    vector<int> y_landmarks(Y, 0);
    for(auto i = 0; i < L; i++) { // O(L)
        int x, y;
        cin >> x >> y;
        x_landmarks[x-1]++;
        y_landmarks[y-1]++;
    }

    auto x_distance = sum_distances(x_landmarks); // O(X)
    auto y_distance = sum_distances(y_landmarks); // O(Y)

    auto candidate = 0;
    auto min_distance = numeric_limits<long long>::max();
    for(auto i = 0; i < H; ++i) { // O(H)
        int x, y;
        cin >> x >> y;
        auto distance = x_distance[x-1] + y_distance[y-1];
        if (distance < min_distance){
            candidate = i + 1;
            min_distance = distance;
        }
    }

    cout << candidate << '\n';
    return 0;
}