the algorithm is correct as I tried using many test cases and the answer was correct everytime.. anyways, I'm giving you a detailed explanation, that wil help u better understand it...
Consider this test case :
Buildings are : 2 3 6 1 5 2 (represented by their heights)
Days are : 6 2 1 5 3 ( represents the nth day for which we have to find regions)
Hence, vector
hts will contain { 2,3,6,1,5,2 }
and vector
dts will contain {6, 2, 1 , 5, 3 }
Now, vector
dp is supposed to contain the "number of regions" "
"for every possible day" starting from day 0 to day N ( where N is the day after which all the "buildings" will be flooded  which means N=maximum height of all buildings. ) For our problem, let N= {0,1....6} (as 6 is the last day i.e. for any day > 6, the number of regions is 0 ).
So let us assume
dp.assign(7,0);
, that wil make it easier to understand.
So vector
dp contains: {0,0,0,0,0,0,0}
And we have a temporary variable "
cur" which tells the height of the building "just before" the current one.
Now here's what happens : (Note all "increments" are by 1 )
1 2 3 4 5 6 7 8 9 10 11 12

0 cur > 0
1 Run the loop from 0 to hts.size() (i.e. <number of buildings>)
2 If the current building's height is greater than "cur" (i.e. <height of prev. building>)
3 Set cur > hts[i]  1
4 Else
5 Increment all the values in "dp" from hts[i] to cur
6 Set cur > hts[i] 1
7 EndIf
8 end loop
9 Increment all the values in "dp" from 0 to "cur"
10 "dp" contains the number of regions of every possible day
11 extract from "dp" the "required" solutions only, and return them as "ans"
 
Now lets ur dry run this on our test case :
Initially,
hts ={ 2,3,6,1,5,2 }
dts = {6, 2, 1 , 5, 3 }
dp = {0,0,0,0,0,0,0}
cur=0
Now how my algo works is to go forward in hts array, until it finds a "drop" in height of the building.
In the given case, the drop occurs at (6 > 1) & (5 > 2)
Now take the 1st drop i.e " 6 > 1 " : increment all values from
dp[1] to
dp[5]
hence,
dp = { 0,1,1,1,1,1,0 }
Now take the 2nd drop i.e. "5 > 2" : increment all values from
dp[2] to
dp[4]
hence
dp = { 0,1,2,2,2,1,0 }
Finally, the LOOP ends here and STEP 9 is executed i.e. to increment all values from
dp[0] to
dp[cur] & cur=21=1
hence
dp= { 1,2,2,2,2,1,0 }
This is the final
dp, which means :
at day 0 : no. of regions=1
at day 1 : no. of regions = 2
.
.
.
at day 5 : no. of regions = 1
at day 6&above : no. of regions =0
finally, the
ans vector will contain : { 0,2,1,2,2 }
You can test run the algo on any test case,it works! But it looks to me the algorithm is quite efficient,, but not the implementation....