У меня странная проблема переполнения с Hackerrank Problem . Вот краткое изложение задачи.
Существует двумерный массив, и в каждой строке массива есть строки, начинающиеся в одной ячейке и заканчивающиеся в другой ячейке (слева направо в той же строке). Теперь в одном ряду может быть несколько строк, и они, безусловно, могут перекрывать друг друга. Задача состоит в том, чтобы найти количество незанятых ячеек в двумерном массиве.
Важно отметить, что размеры массива могут быть очень большими вплоть до 10^9. Так что это был мой подход
- Использовать карту, в которой в качестве ключа указан номер строки, а в качестве соответствующего значения - вектор пар. Пары - это не что иное, как начальный и конечный индексы строки в этой строке.
row -> vector<pair<int, int>> - Сортировать каждый такой вектор по первому элементу пары (то есть по начальному индексу интервала).
- Объединить перекрывающиеся интервалы для всех строк. Для каждого объединенного интервала рассчитайте его длину
wR - wL + 1, где wL и wR - начальный и конечный индексы интервала соответственно. Добавьте длину всех этих интервалов и сохраните в переменной sum - Наконец, вычтите это
sum из n*m, чтобы получить количество незанятых ячеек.
Здесь это соответствующий код
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define ulld unsigned long long int
#define ff first
#define ss second
using namespace std;
void sortMap(unordered_map<int, vector<pii>> &dict){
unordered_map<int, vector<pii>>::iterator it;
for(it=dict.begin(); it!=dict.end(); it++){
vector<pii> &temp = it->second;
sort(temp.begin(), temp.end());
}
}
ulld compute(unordered_map<int, vector<pii>> &dict, int n, int m){
unordered_map<int, vector<pii>>::iterator it;
ulld sum = 0;
for(it = dict.begin(); it != dict.end(); it++){
vector<pii> temp = it->second;
int n = temp.size();
int WL = temp[0].ff,
WR = temp[0].ss;
for(int i=0; i<n-1; i++){
if(WR >= temp[i+1].ff && WR < temp[i+1].ss){
// partial overlap
WR = temp[i+1].ss;
}else if(WL <= temp[i+1].ff && WR >= temp[i+1].ss){
// complete overlap
// nothing to consider here
}else{
// no overlap
// compute the exisiting window size so far
sum += WR - WL + 1;
WL = temp[i+1].ff;
WR = temp[i+1].ss;
}
}
sum += (WR - WL + 1);
}
ulld ans = ((ulld)n * (ulld)m) - sum;
return ans;
}
// Complete the gridlandMetro function below.
ulld gridlandMetro(int n, int m, int k, vector<vector<int>> track) {
unordered_map<int, vector<pii>> dict;
for(int i=0;i<k;i++){
int row = track[i][0]-1;
pii bounds = mp(track[i][1]-1,track[i][2]-1);
if(dict.find(row) == dict.end()){
vector<pii> temp;
temp.push_back(bounds);
dict.insert(pair<int, vector<pii>>(row, temp));
}else{
vector<pii> temp = dict[row];
temp.push_back(bounds);
dict[row]=temp;
}
}
sortMap(dict);
return compute(dict, n, m);
}
Я разблокировал конкретный контрольный пример, для которого код не удался. Этот тестовый набор состоит из больших чисел порядка 10^9, а результат - порядка 10^18, что соответствует ожиданиям.
Я не понимаю, почему я получаю отрицательные значения мусора при работе с большими числами, несмотря на использование соответствующих типов данных: long long, unsigned long long int?
Буду очень признателен за помощь в этом! Спасибо за проявленное терпение.