This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#include<algorithm>
#define M 2147483647000000000LL
using namespace std;
int cnt,t,w,m,n,c[100010],a[100010],b[100010];
long long dap=M,d[100010],l[1200010],r[1200010];
struct data2
{
int x,y;
bool operator<(const data2&r)const
{
return x<r.x;
}
}arr[300010];
void updatel(int p,long long x)
{
p+=(t-1); l[p]=min(l[p],x); p/=2;
while(p)
{
l[p]=min(l[p*2],l[p*2+1]);
p/=2;
}
}
void updater(int p,long long x)
{
p+=(t-1); r[p]=min(r[p],x); p/=2;
while(p)
{
r[p]=min(r[p*2],r[p*2+1]);
p/=2;
}
}
long long queryl(int x,int y,int k,int s,int e)
{
if(x>e || y<s) return M;
if(s<=x && y<=e) return l[k];
return min(queryl(x,(x+y)/2,k*2,s,e),queryl((x+y)/2+1,y,k*2+1,s,e));
}
long long queryr(int x,int y,int k,int s,int e)
{
if(x>e || y<s) return M;
if(s<=x && y<=e) return r[k];
return min(queryr(x,(x+y)/2,k*2,s,e),queryr((x+y)/2+1,y,k*2+1,s,e));
}
int main()
{
int i,st;
long long k1,k2;
scanf("%d %d",&m,&n);
arr[++w].x=n; arr[w].y=0; arr[++w].x=1; arr[w].y=-1;
for(i=1;i<=m;i++)
{
scanf("%d %d %d %lld",&a[i],&b[i],&c[i],&d[i]);
arr[++w].x=a[i]; arr[w].y=i*3-2; arr[++w].x=b[i]; arr[w].y=i*3-1; arr[++w].x=c[i]; arr[w].y=i*3;
}
sort(arr+1,arr+w+1);
for(i=1;i<=w;i++)
{
if(arr[i].x!=arr[i-1].x) cnt++;
if(arr[i].y==0) n=cnt;
else if(arr[i].y==-1) st=cnt;
else if(arr[i].y%3==1) a[arr[i].y/3+1]=cnt;
else if(arr[i].y%3==2) b[arr[i].y/3+1]=cnt;
else c[arr[i].y/3]=cnt;
}
for(t=1;t<=cnt;t*=2);
for(i=1;i<=t*2;i++) l[i]=r[i]=M;
updatel(st,0); updater(n,0);
for(i=1;i<=m;i++)
{
k1=queryl(1,t,1,a[i],b[i])+d[i];
k2=queryr(1,t,1,a[i],b[i])+d[i];
if(dap>k1+k2-d[i]) dap=k1+k2-d[i];
updatel(c[i],k1);
updater(c[i],k2);
}
if(dap>21474836470000LL) printf("-1");
else printf("%lld",dap);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |