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
can you share the complete code and the problem also?
The complete code is long ... but it all follows the same pattern as the loop I mentioned. I tried running only that loop and it times out. Now that we have the problem statement, note that the code is MlogM and not NlogN since it only consider rows and columns that contain turbines and not all N rows and columns
Original statement: https://oj.vnoi.info/problem/voi24_three
Translated:
Alpha Country has a wind farm that is planned on a square grid of N rows and N columns. The rows are numbered from 1 to N from top to bottom, and the columns are numbered from 1 to N from left to right. The farm has M wind turbines numbered from 1 to M. The i-th turbine (1 ≤ i ≤ M) is located at the cell in row Ri and column Ci with a power output of Wi watts. The farm owner has just signed a contract to supply electricity to a partner. The farm will have to install three power lines, each passing through one row or one column of the grid. The lines can intersect but cannot overlap. The total power supplied to the partner is the sum of the power of the turbines located on at least one of the three lines. The farm needs to find a way to install three power lines so that the total power supplied is as large as possible.
In addition, the company has Q adjustment plans. The j-th adjustment plan (1 ≤ j ≤ Q) is to increase the power of the Tj-th turbine by Dj watts and keep the power Wi of all other turbines i different from Tj the same as the original initial state. Note that the plans are independent, meaning that each plan is only applied to the initial state of the farm.
Requirement: Determine the maximum possible total power when installing three power lines with the initial state of the farm and in each adjustment plan.
Input From the text file THREE.INP:
The first line contains a positive integer T indicating the number of test cases. Each group of lines in the T following groups describes a test case with the following structure: The first line contains three integers N, M, and Q representing the size of the grid, the number of turbines, and the number of adjustment plans (3 ≤ N ≤ 10^9; 3 ≤ M ≤ 10^5; 1 ≤ Q ≤ 10^5).
The i-th of the next M lines contains three integers Ri, Ci, and Wi representing the row, column, and power of the i-th turbine. The data ensures that no two turbines are placed in the same cell (1 ≤ Ri, Ci ≤ N; 1 ≤ Wi ≤ 10^9).
The i-th of the next Q lines contains two integers Tj and Dj representing the adjustment plan to increase the power of the Tj-th turbine by Dj watts (1 ≤ Tj ≤ M; 1 ≤ Dj ≤ 10^18).
Let ∑M and ∑Q be the sums of all values of M and Q in all T test cases. The data ensures 1 ≤ ∑M, ∑Q ≤ 2 × 10^5. The numbers on the same line are separated by spaces. Output Write to the text file THREE.OUT:
T groups of lines, each line is the result of the corresponding test case with the following structure:
The first line shows a positive integer which is the maximum total power found with the initial state of the farm.
The j-th of the next Q lines shows the maximum total power found with the j-th adjustment plan.
have you considered the fact that you may be accessing elements out of bound?
i checked for this and nothing goes out of bound'