14,981,456 members
1.00/5 (1 vote)
See more:
```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.

Posted
Updated 9-Jul-20 20:21pm
v2
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

HB World 9-Jul-20 15:11pm

https://www.codechef.com/JULY20B/problems/DRGNDEN

## Solution 1

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.
HB World 10-Jul-20 6:04am

Can you tell how to make a Q2 results array, i cant figure it out ??