#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 2e18;
//persistant+sparse segment tree
struct segTree{
struct node{
int sum,l,r;
};
node *st;
node def;
int cr = 1;
int cpy(int ind){
st[++cr]=st[ind];
return cr;
}
segTree(int nodes){
st=new node[nodes];
def.sum=0;
def.l=0;
def.r=0;
fill(st,st+nodes,def);
}
void update(int l, int r, int i, int val, int ind){
if(l==r){
st[ind].sum+=val;
return;
}
int mid = (l+r)/2;
if(i<=mid){
st[ind].l=cpy(st[ind].l);
update(l,mid,i,val,st[ind].l);
}
else{
st[ind].r=cpy(st[ind].r);
update(mid+1,r,i,val,st[ind].r);
}
st[ind].sum=st[st[ind].l].sum+st[st[ind].r].sum;
}
int query(int l, int r, int s, int e, int ind){
if(e<l||s>r){
return 0;
}
if(s<=l&&r<=e){
return st[ind].sum;
}
int mid = (l+r)/2;
return query(l,mid,s,e,st[ind].l)+query(mid+1,r,s,e,st[ind].r);
}
};
long long solve(int n, int m, int w, vector<int> T, vector<int> X, vector<int> Y,
vector<int> A, vector<int> B, vector<int> C, vector<int> L,
vector<int> R) {
//could do sparse, might as well compress cause easier
vector<int>coords;
for(int i : A){
coords.push_back(i);
}
for(int i : B){
coords.push_back(i);
}
for(int i : X){
coords.push_back(i);
}
for(int i : Y){
coords.push_back(i);
}
for(int i : L){
coords.push_back(i);
}
for(int i : R){
coords.push_back(i);
}
coords.push_back(2e9);
coords.push_back(-1);
sort(coords.begin(),coords.end());
coords.erase(unique(coords.begin(),coords.end()),coords.end());
auto findcompress = [&] (int tim){
return lower_bound(coords.begin(),coords.end(),tim)-coords.begin();
};
//coords compressed
//make persistent segtree
//sort l,r pairs
map<int,vector<int>>meals;
for(int i = 0;i<w;i++){
meals[L[i]].push_back(R[i]);
}
//suffix sum cause prefix would require 2 logn per suffix search
segTree st(1e7);
vector<int>roots(coords.size());
roots.back()=1;
assert(meals[coords.back()].size()==0);
for(int i = coords.size()-2;i>=0;i--){
int tim = coords[i];
roots[i]=st.cpy(roots[i+1]);
for(int r : meals[tim]){
st.update(0,coords.size()-1,findcompress(r),1,roots[i]);
}
}
//make segtree query function
auto query = [&] (int a, int b){
a=findcompress(a);
b=findcompress(b);
///exactly at a and exactly at b excluded
a++;
b--;
if(a>b){
return 0;
}
return st.query(0,coords.size()-1,a,b,roots[a]);
};
//segtree created
//sort train arrival+departures
vector<array<int,3>>trains;
for(int i = 0;i<m;i++){
//time,arrival/departure,train index
trains.push_back({A[i],1,i});
trains.push_back({B[i],0,i});
}
sort(trains.begin(),trains.end());
//sorted
long long dp[m];
fill(dp,dp+m,inf);
deque<array<long long,3>>dq[n];
//{cost,time,opt interval start time};
dq[0].push_back({0,-1,-1});
for(int i = 1;i<n;i++){
dq[i].push_back({inf,-1,-1});
}
for(array<int,3>train:trains){
if(train[1]){
//departure
//must find cost of thingy
//must find which train to transition from
int v = X[train[2]];
int curtim = A[train[2]];
while(dq[v].size()>=2){
//compare first 2
int cost1 = dq[v][0][0]+T[v]*query(dq[v][0][1],curtim);
int cost2 = dq[v][1][0]+T[v]*query(dq[v][1][1],curtim);
if(cost1>=cost2){
dq[v].pop_front();
}
else{
break;
}
}
dp[train[2]] = C[train[2]]+dq[v][0][0]+T[v]*query(dq[v][0][1],curtim);
}
else{
//arrival
//cost is fixed just need to push this train into wherever it is arriving
int curtim = B[train[2]];
int v = Y[train[2]];
while(dq[v].size()){
//compare against last
array<long long,3>a = dq[v].back();
//check cost at last one opt interval start
if(dp[train[2]]+T[v]*query(curtim,a[2])<=a[0]+T[v]*query(a[1],a[2])){
dq[v].pop_back();
}
else{
break;
}
}
if(dq[v].size()==0){
dq[v].push_back({dp[train[2]],curtim,curtim});
}
else{
//bin search for opt start
int lo = 0;
int hi = coords.size()-1;
array<long long,3>a = dq[v].back();
while(lo<hi){
int mid = (lo+hi)/2;
if(dp[train[2]]+T[v]*query(curtim,coords[mid])<a[0]+T[v]*query(a[1],coords[mid])){
//this is a upper bound
hi=mid;
}
else{
lo=mid+1;
}
}
dq[v].push_back({dp[train[2]],curtim,coords[lo]});
}
}
}
long long ans = inf;
for(int i = 0;i<m;i++){
if(Y[i]==n-1){
//this train can be considered
ans=min(ans,dp[i]+T[n-1]*query(B[i],2e9));
}
}
if(ans>=inf){
return -1;
}
return ans;
}
