1487E - Cheap Dinner - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 150001
using namespace std;
const long long oo=round(1e18);
long long kq,st[4*N],f[N];
vector <int> a[5][N];
int sl[5],n,m,i,j,u,v,c[5][N];
void update(int id,int l,int r,int u,long long k)
{
    if(u<l || u>r) return ;
    if(l==r) { st[id]=k; return ; }
    int mid=(l+r)>>1;
    update(id*2,l,mid,u,k); update(id*2+1,mid+1,r,u,k);
    st[id]=min(st[id*2],st[id*2+1]);
}
long long get(int id,int l,int r,int u,int v)
{
    if(u>r || v<l || l>r) return oo;
    if(u<=l && r<=v) return st[id];
    int mid=(l+r)>>1;
    return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int main()
{
  //  freopen("ntu.inp","r",stdin);
  //  freopen("ntu.out","w",stdout);
    cin>>sl[1]>>sl[2]>>sl[3]>>sl[4];
    n=max(max(sl[1],sl[2]),max(sl[3],sl[4]));
    for(j=1;j<=4;j++)
        for(i=1;i<=sl[j];i++) cin>>c[j][i];
    for(j=2;j<=4;j++)
    {
        cin>>m;
        while(m--)
        {
            cin>>u>>v;
            a[j][v].push_back(u);
        }
    }
    for(i=1;i<=sl[1];i++) f[i]=c[1][i];
    kq=oo;
    for(j=2;j<=4;j++)
    {
        for(i=1;i<=4*n;i++) st[i]=oo;
        for(i=1;i<=sl[j-1];i++)
        {
            update(1,1,n,i,f[i]);
        }
        for(u=1;u<=sl[j];u++)
        {
            a[j][u].push_back(0); a[j][u].push_back(n+1);
            sort(a[j][u].begin(),a[j][u].end());
            f[u]=oo;
            for(i=1;i<a[j][u].size();i++)
            {
                f[u]=min(f[u],get(1,1,n,a[j][u][i-1]+1,a[j][u][i]-1)+c[j][u]);
                f[u]=min(f[u],oo);
            }
            if(j==4) kq=min(kq,f[u]);
        }
    }
    if(kq==oo) kq=-1;
    cout<<kq;
}