Hi, I'm having trouble understanding why this loop times out even though its time complexity should be NlogN (N<=1e5) (Time limit: 2 seconds). The purpose of this loop is to modify "sum_row_set" (a multiset of pairs) , take the best element, and restore its initial state.
for (int j : list_col) {
for (auto p : col[j]) {
int i = p.fi, v = p.se;
sum_row_set.erase({sum_row[i], i});
sum_row_set.insert({sum_row[i] - 1ll * v, i});
}
auto it = sum_row_set.begin();
best_for_col[j] = {(*it).fi + sum_col[j], (*it).se};
best_for_col_set.insert({best_for_col[j].fi, j});
best_row[(*it).se].push_back(j);
it++;
second_best_for_col[j] = {(*it).fi + sum_col[j], (*it).se};
for (auto p : col[j]) {
int i = p.fi, v = p.se;
sum_row_set.erase({sum_row[i] - 1ll * v, i});
sum_row_set.insert({sum_row[i], i});
}
}
These nested loops (without doing anything inside of them) perform at most 1e5 operations,
for (int j : list_col) { for (auto p : col[j]) { } }
and all sets used here have a maximum size of 1e5.
I'ved tried deleting "sum_row_set.erase(); sum_row_set.insert(); " and the execution time significantly decreased. So I think the problem seems to be the use of "erase" and "insert". Is there a way I can optimize this ? Tysm