This is my code:
#include<bits/stdc++.h>
#define NINF INT_MIN
using namespace std;
typedef long long int ll;
void addEdge(vector <pair<ll, ll> > adj[], ll u, ll v, ll wt)
{
adj[u].push_back(make_pair(v, wt));
}
void topologicalSortUtil(vector <pair<ll, ll> > adj[],ll v, bool visited[], stack<ll> &Stack)
{
visited[v] =true;
vector < pair <ll, ll> >::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[i->first])
topologicalSortUtil(adj,i->first, visited, Stack);
Stack.push(v);
}
ll longestPath(vector <pair<ll, ll> > adj[],ll s,ll ending,ll V)
{
stack<ll> Stack;
ll dist[V];
bool* visited = new bool[V];
for (ll i = 0; i < V; i++)
visited[i] = false;
if (visited[s] == false)
topologicalSortUtil(adj,s, visited, Stack);
for (ll i = 0; i < V; i++)
dist[i] = NINF;
dist[s] = 0;
while (Stack.empty() == false) {
ll u = Stack.top();
Stack.pop();
vector< pair <ll, ll> >::iterator i;
if (dist[u] != NINF) {
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (dist[i->first] < dist[u] + i->second)
dist[i->first] = dist[u] + i->second;
}
}
if(dist[ending] == NINF)
return -1 ;
else
return dist[ending];
delete [] visited;
}
void add(ll ans,ll start,ll den[])
{
if(ans==-1)
cout<<ans<<"\n";
else
{
ans+=den[start];
cout<<ans<<"\n";}
}
float slope(float x1,float x2,float y1,float y2)
{
return (y2-y1)/(x2-x1);
}
void create_directed_acyclic_graph(vector< pair <ll, ll> >adj[],float a[],ll den[],ll n)
{
for(ll i=0;i<n-1;i++)
{
if(i==0)
{
if((a[i]>a[i+1]))
{
float s=slope(i,i+1,a[i],a[i+1]);
addEdge(adj,i,i+1,den[i+1]);
for(ll j=i+2;j<n;j++)
{
if(a[j]<a[i])
{
if(slope(j,i,a[j],a[i])>s)
{
s=slope(j,i,a[j],a[i]);
addEdge(adj,i,j,den[j]);
}
}
else
break;
}
}
}
else
{
if((a[i]>a[i+1]&&a[i]>=a[i-1])||(a[i]<=a[i-1]&&a[i]>a[i+1]))
{
float s=slope(i,i+1,a[i],a[i+1]);
addEdge(adj,i,i+1,den[i+1]);
for(ll j=i+2;j<n;j++)
{
if(a[j]<a[i])
{
if(slope(j,i,a[j],a[i])>s)
{
s=slope(j,i,a[j],a[i]);
addEdge(adj,i,j,den[j]);
}
}
else
break;
}
}
}
}
return;
}
int main()
{
ll n,q;
cin>>n>>q;
float a[200000],ar[200000];
ll b[200000],br[200000];
for(ll i=0;i<n;i++)
{cin>>a[i];ar[n-1-i]=a[i];}
for(ll i=0;i<n;i++)
{cin>>b[i];br[n-1-i]=b[i];}
vector< pair <ll, ll> >adj1[n];
vector< pair <ll, ll> >adj2[n];
ll val,cho1,cho2;
while(q--)
{
cin>>val>>cho1>>cho2;
cho1--;
cho2--;
if(val==1)
{
ll temp=cho2+1;
b[cho1]=temp;
br[n-1-cho1]=temp;
}
else
{
create_directed_acyclic_graph(adj1,a,b,n);
create_directed_acyclic_graph(adj2,ar,br,n);
if(cho1<cho2)
add(longestPath(adj1,cho1,cho2,n),cho1,b);
else
add(longestPath(adj2,n-1-cho1,n-1-cho2,n),n-1-cho1,br);
}
}
return 0;
}