After escaping from prison, the Dalton brothers have turned to extracting 2D oil wells…
- User
After escaping from prison, the Dalton brothers have turned to extracting 2D oil wells to make ends meet. A two-dimensional oil well in the form of an infinite table with n n columns and 1 0 9 10 9 It is the line above the first line, the ground level. Each column consists of specific amounts of soil, oil and rock. Based on the way oil is formed over time, in each column of the oil well, there is oil in a correct interval of the depth of the earth, which is this interval for the column i I am with [ l i , r i ] [l i R i ] and it means that from depth l i l i to the depth r i r i From the column i It consists of oil. As a result, this column includes r i
l i r i -l i It is a unit of oil. We also know that always from the surface of the earth to the depth of the beginning of oil, that is, the interval [ 0 , l i ] [0, l i ], composed of soil, and from the depth of the end of the oil to the end of the oil well, that is, the interval [ r i , 1 0 9 ] [r i , 10 9 ], is made of stone. For example, if the oil interval in a column [ 1 , 3 ] [1,3], there is 1 unit of soil and 2 units of oil in that column.
The Dalton brothers, who do not have much time to extract oil from the wells, work to extract oil in this way by choosing a number of columns in a row and digging the ground to a certain depth using an oil rig. If there is even one unit of stone in the sub-rectangle of the oil well that the oil drilling machine digs, the machine will be damaged, and that's why the Dalton brothers don't want there to be any stone under the rectangle that they dig. After digging a sub-rectangle from an oil well, all its soil units are destroyed, but all the oil units in it come out of the oil rig and the Dalton brothers collect them.
After drilling a sub-rectangle of an oil well, Dalton brothers can extract oil from all the holes connected to the oil reservoir using an oil skimmer. Please note that pores are all reservoirs containing oil from the matrix that have been exposed to air after subrectangular drilling. In other words, all the regions in the table that are one of the neighboring regions (adjacency in this question means lateral proximity. It means that two regions have a common side). They were located inside the carved sub-rectangle. After being connected to a hole, the oil trap device sucks all the units of oil that reach the hole through the reservoirs containing oil and takes them out of the outlet for Dalton brothers to collect. An oil-containing reservoir has a route to a hole if there is a sequence of oil-containing reservoirs starting from that hole and ending at the hole, such that any two consecutive members in the sequence are adjacent.
What is the maximum amount of oil the Dalton brothers can collect?
input In the first line of the input n n is the number of oil well columns. in n n next line of input, two natural numbers in each line l i l i and r i r i It is stated that the beginning and end of the interval formed by oil in the column i They show iam. 1 ≤ n ≤ 200
000 1≤n≤200 000 1 ≤ l i ≤ r i ≤ 1 0 9 1≤l i ≤r i ≤10 9
output On the only output line, print the maximum amount of oil the Dalton brothers can collect.
Sub-issues Constraint score subproblem We don't have oil. l i
r i l i =r i ) We don't have 2 stones. r i
1 0 9 r i =10 9 ) We don't have soil l i
1 l i =1) 4 12 n ≤ 20 n≤20 5 21 n ≤ 2
000 n≤2000 6 61 without additional restrictions Pay attention that there is always a layer of soil on the oil well and in the third sub-problem it is meant without considering that layer.
Example Sample entry 1 11 2 2 2 4 3 4 3 3 4 5 4 5 3 4 3 5 4 6 3 5 1 2 Plain text Sample output 1 11 Plain text The sample input is the same as the first page of the question and shows the sub-rectangular red dashed line that Naftkan draws. c++
- Assistant
To solve the problem of maximizing the amount of oil the Dalton brothers can collect, we need to carefully analyze the structure of the oil wells and determine an optimal strategy for drilling. Here's a step-by-step explanation of how to approach this problem:
Problem Breakdown
-
Oil Well Structure:
- You have
ncolumns, each representing an oil well. - Each column
ihas oil in the interval[l_i, r_i]. - Above
l_iis soil and belowr_iis stone.
- You have
-
Drilling Constraints:
- When drilling a sub-rectangle (a consecutive set of columns up to a certain depth
d), there must be no stone in the dug area. This implies that the chosen depthdmust be less than or equal tor_ifor all columns in the sub-rectangle. - The goal is to maximize the amount of oil extracted, which includes oil in the dug area and any oil connected to it.
- When drilling a sub-rectangle (a consecutive set of columns up to a certain depth
Strategy
To maximize the oil extraction, we need to:
-
Determine the Optimal Depth (
d) and Interval[a, b]:- We need to choose a range of columns
[a, b]and a depthdsuch thatd <= min(r_i)for alliin[a, b]. - The amount of oil extracted from this sub-rectangle is the sum of
(d - l_i)for alliin[a, b]whered > l_i.
- We need to choose a range of columns
-
Use an Efficient Algorithm:
- We can use a stack-based approach (similar to the largest rectangle in histogram problem) to efficiently find the optimal
[a, b]for each possibled. - Precompute the prefix sums of
l_ito quickly calculate the sum of soil units in any interval.
- We can use a stack-based approach (similar to the largest rectangle in histogram problem) to efficiently find the optimal
-
Calculate the Maximum Oil:
- For each column
i, treatr_ias the potential depthd. - Use the stack to determine how far left and right you can extend the interval
[a, b]such that all columns in this interval haver_j >= r_i. - Calculate the oil extracted for each interval and keep track of the maximum.
- For each column
Implementation Steps
-
Precompute Prefix Sums:
- Calculate prefix sums of
l_ito efficiently compute the sum of soil units in any interval.
- Calculate prefix sums of
-
Determine Left and Right Boundaries:
- For each column
i, find the nearest column to the left and right wherer_j < r_i. These are your boundaries for the optimal interval.
- For each column
-
Compute Maximum Oil:
- For each column, compute the oil extracted in its optimal interval and keep track of the maximum value.
Example
Consider an example with columns and their
[l_i, r_i]:n = 11 Columns: [2,2], [2,4], [3,4], [3,3], [4,5], [4,5], [3,4], [3,5], [4,6], [3,5], [1,2]After applying the algorithm, the maximum oil that can be extracted is
11.Final Answer
The maximum amount of oil the Dalton brothers can collect is 11.
Implementation (C++)
Below is the C++ implementation of the above approach:
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<pair<ll, ll>> lr(n); for(auto &p: lr) cin >> p.first >> p.second; // Prefix sum of l_i vector<ll> prefix_sum_l(n+1, 0); for(int i=1;i<=n;i++) prefix_sum_l[i] = prefix_sum_l[i-1] + lr[i-1].first; // Find left boundaries vector<int> left(n, -1); stack<int> s; for(int i=0;i<n;i++){ while(!s.empty() && lr[s.top()].second >= lr[i].second){ s.pop(); } if(!s.empty()) left[i] = s.top(); else left[i] = -1; s.push(i); } // Find right boundaries vector<int> right(n, n); while(!s.empty()) s.pop(); for(int i=n-1;i>=0;i--){ while(!s.empty() && lr[s.top()].second >= lr[i].second){ s.pop(); } if(!s.empty()) right[i] = s.top(); else right[i] = n; s.push(i); } // Now for each i, calculate oil ll max_oil = 0; for(int i=0;i<n;i++){ ll d = lr[i].second; int l = left[i]+1; int r_bound = right[i]; ll width = r_bound - l; ll sum_li = prefix_sum_l[r_bound] - prefix_sum_l[l]; ll oil = d * width - sum_li; if(oil > max_oil) max_oil = oil; } cout << max_oil; }Conclusion
By leveraging a stack-based approach and prefix sums, we can efficiently determine the optimal sub-rectangle for drilling to maximize oil extraction. This solution ensures that the problem constraints are met, and it runs efficiently even for large values of
n. -