I had the same idea of having one segment tree for max height and other two for left and right direction. But i got stuck in the merging part in segment tree, where i needed to find closest point with height strictly greater than the highest point of the other part.
My solution is the same as in the editorial, but note that you do not need any kind of heavy light decomposition (I did not use it). When using a queue to assign the rightmost hill to the left which is > in height for each hill, use 4 queues instead. So for each assign rightmost hill to the left which is >, ‘’ ‘’ ‘’ which is >= and the mirror. Now you can use two segment trees to get your job done and use the >= one for checking purposes if a path exists.
1 Like
Hi Varun,
You could find the closest point to the left or right with height strictly greater height using Stacks.
Here, do refer this : Find the nearest smaller numbers on left side in an array - GeeksforGeeks
Also, you can try to solve : Problem - C2 - Codeforces
1 Like
The TL of 1 sec was brutal for me. I had to optimize my HLD code a lot because of the constant factors (and also I’m sure there is a lot of other redundant stuff because this was my first time trying HLD).
But I think the test cases are weak in subtask 3. Very weirdly my submission using the normal HLD code gave AC in subtask 1 and 3 but TLE in subtask 2.
Which makes no sense because the test cases of ST#2 should be a subset of ST#3. But who am I to argue when I can benefit from this XD
So I just copied the code I had submitted before for partial points of ST#2, called it void scam() (a fitting name), and put it in my HLD submission. If a test case didn’t have a query of type 1 within the first 1000 queries(a random heuristic) I would identify it as a test case from ST#2 and call void scam()
Surprisingly it works XD
Here is the first code
Here is the “improved one”
1 Like
It is working on this test case.
I tried same approach but instead of array I used set which store elements of a block only from current max till max of next block means storing only the path. But it is not working on test cases other than sample. Can you check my solution. here is link given
Good catch. Since there was an \mathcal{O}(\log n)-per-query solution (tree flattening instead of HLD) I was maybe more lax than I should have been with the strength of the test cases discriminating between the \mathcal{O}(\log^2 n) test cases. Oh well, bringing the constant factor down isn’t too bad anyway :))
1 Like
#include<bits/stdc++.h>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<string>
#define si(x) scanf("%d",&x);
#define ff first
#define ss second
#define vi vector<int>
#define vll vector<ll>
#define ll long long int
#define mod 1000000007
#define ld long double
#define llu unsigned long long int
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define tezz ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define f(i,n) for(int i=0;i<n;i++)
#define f1(i,j,n) for(int i=j;i<n;i++)
#define INF 1000000000
#define pll pair<ll,ll>
using namespace std;//fuck copying and ratings
int main(){
tezz;
int t=1;
//cin>>t;
while(t--){
ll n,q;
cin>>n>>q;
ll h[n+1]={0},a[n+1]={0};
f1(i,1,n+1)
cin>>h[i];
f1(i,1,n+1)
cin>>a[i];
while(q--){
ll o,b,c;
cin>>o>>b>>c;
if(o==1){
ll k=c;
a[b]=k;
}
else if(o==2){
if(b>c){
ll flag=0,diff=0;
vll v1;
for(int i=b-1;i>c;i--){
if(h[i]<=h[b] and h[i]>=h[c]){
v1.pb(i);
}
if(h[i]>=h[b])
flag=-1;
}
ll sum=0;
f(i,v1.size())
sum+=a[v1[i]];
sum+=(a[b]+a[c]);
if(v1.size()){
f(i,v1.size()-1){
if(h[v1[i]]<h[v1[i+1]]){
diff+=a[v1[i]];
}
}
}
else{
if(h[c]<h[b])
sum=a[b]+a[c];
else
sum=-1;
}
if(flag!=-1)
cout<<sum-diff<<endl;
else
cout<<-1<<endl;
}
else if(b<c){
ll flag=0,diff=0;
vll v2;
for(int i=b+1;i<c;i++){
if(h[i]<=h[b] and h[i]>=h[c]){
v2.pb(i);
// cout<<i<<" ";
}
if(h[i]>=h[b] )
flag=-1;
}
//cout<<endl;
ll sum=0;
f(i,v2.size()){
sum+=a[v2[i]];
}
sum+=(a[b]+a[c]);
if(v2.size()){
f(i,v2.size()-1){
if(h[v2[i]]>h[v2[i+1]])
diff+=a[v2[i]];
}
}
else{
if(h[c]<h[b])
sum=(a[b]+a[c]);
else
sum=-1;
}
if(flag!=-1)
cout<<sum-diff<<endl;
else
cout<<-1<<endl;
}
else{
cout<<-1<<endl;
}
}
}
}
return 0;
}
I tried a brute force approach for 10 pts but its failing though I see many wrote a similar solution which is given 10 pts,can you please help me where I am getting it wrong.
Can somebody explain why this soln using set is wrong for the first subtask
Submission link (CodeChef: Practical coding for everyone)
HLD (Heavy-Light Decomposition) ka name suna he?
does that kind of function have any specific name?
Graham scan is close i guess…
If you choose height 4 with taste 7,notice it is left one. After it, when you go to 2, the line will cut the mid mountain of height 4 .It is well said, the line shouldn’t go through inside the mountain. Make a drawing of it, you’ll get my point more clearly.
Yeah, If you scroll a bit down, I’ve said that I didn’t notice that it was supposed to be a line segment, which I realised eventually. Thanks for the clarification anyway. Cheers.
Thanks for the resources 
It’s just an application of stack; it’s actually somewhat of a classic problem.
If you’re referring to me declaring a function in the middle of another function in C++, they’re called lambda functions.
Your’e Welcome !!
I have also used the same approach with some tweaks and block size of 5k for large n.
My Solution: CodeChef: Practical coding for everyone
good problem
1 Like