Click here to Skip to main content
14,981,456 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
Question : We have been given two arrays of size N with each element as hi, ai the elements are positive integers and random. We are Also Given with Q queries of 2 type. 

In query type 1 : we will be given with 2 positive integers b k and we have to update a[b] to k.

In query Type 2 : we will be given with 2 positive integers b c and we need to find out whether moving from h[b] to h[c] possible and if yes then we have to find a sum.

Now, there are rules to move in array h[i]. 

Rule 1 : We can only move from i to j if A[i] < A[j]. 

Rule 2 : We can only move to just next greatest element. i.e if array [1,5,4,8] and we want to move from 1 to 8, then path taken will be 1-->5-->8. we cannot take 1-->4-->8 as 4 is not the next greater element of 1.

Constraints :

1≤N,Q≤2⋅10^5 

1≤hi≤10^9 for each valid i

1≤ai≤10^9 for each valid i

1≤b,c≤N

1≤k≤10^9

For each query of type 2 if it is possible to go from b to c then we have to output the sum of elements from a[i] that were part of path.

For Example h[] = {1,5,4,8} , a[] = {1,2,3,4}, path taken : 1-->5-->8 (b=1,c=4)so sum will be 1+2+4 = 7.

And if we cannot reach to destination for example h[] = {1,5,4,4} b=1,c=4 so here we cannot reach to 4th index by following rules of movement hence output will be -1.


What I have tried:

So, Now I think Question is clear. What i need to know is how to pre-process all this. i mean for every query of type 2 i can just create a loop and find we reaching from b to c is possible or not. But due to very large Queries the time complexity becomes O(n^2) of my approach which gives TLE. I need to know how to pre-process everything so that for every query of type 2 i just calculate the answer in constant time.

My O(n^2) approach.

while(Q--) // Q is total Queries
{
 int q,b,c,k; cin >> q;
 if(q == 1) // query type 1 
 {
   cin >> b >> k;
   a[b]=k;
 }
 else // query type 2
 {
   cin >> b >> c;
   int sum = a[c],curr=a[b];bool flag = 0;
   for( int i = b+1 ; i < c-1 ; i++ ) // loop to find sum if possible
   {
    if( h[i] > curr ) // h[i] is the just next greater.
    {
      sum+=a[i];
      curr=h[i];
      flag=1;
    }
   }

   if(flag) 
     cout << sum << "\n";
   else 
     cout << "-1\n"; 
}
}

So, My above approach works Fine when Q and N are below 1000, but when they are increased to 200000, this program gives TLE as for each query i am traversing a loop.

I need to remove this inner Loop, by doing some pre-processing before Query loop (while(Q--){..}). The problem is that i cant figure out how to pre-process the input data such that i am able to know that reaching from b to c is possible or not and if it is then calculating desired sum.

Please Help me out, I am scratching my head on this from past few days.. 


Link to original problem: https://www.codechef.com/JULY20B/problems/DRGNDEN[^]
Posted
Updated 9-Jul-20 20:21pm
v2
Comments
Patrice T 9-Jul-20 14:41pm
   
Give link to page of this problem, exact wording can matter.
Patrice T 9-Jul-20 14:42pm
   
Give link to the problem page, exact wording often matters.
Patrice T 9-Jul-20 15:01pm
   
Giving link to problem's page is a good idea, exact wording matters often.
Giving code snipset that we can run is a good idea too.
HB World 9-Jul-20 15:11pm
   
https://www.codechef.com/JULY20B/problems/DRGNDEN link to original problem.
HB World 9-Jul-20 15:11pm
   
https://www.codechef.com/JULY20B/problems/DRGNDEN

1 solution

Q1 is an changing task, but it only changes one value. So you can store the Q2 results in an array and only make an update of the sum data in case of Q1 with the difference .

With memcpy you can copy a bunch of sum-elements of the result array. Pay attention to store the overwritten data at first.
   
Comments
HB World 10-Jul-20 6:04am
   
Can you tell how to make a Q2 results array, i cant figure it out ??

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900