#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=1e5+9;
struct edg{
int time;
int l,r;
long long c;
bool operator < (const edg &p)const {
return time<p.time;
}
}a[maxn];
vector<int>g[maxn];
bool check(int i, int j) {
if (a[i].r == n)return 0;
if (a[i].time <= a[j].time) {
if (a[i].r+1+a[i].time>=a[j].l+a[j].time)return 1;
return 0;
} else {
//will infected from a[j].l-1
if (a[i].r+1-a[i].time>=a[j].l-a[j].time)return 1;
return 0;
}
}
int n,m;
long long d[maxn];
bool vis[maxn];
const long long inf=1e18;
struct line{
int u;
long long val;
bool operator < (const line &p)const {
return val>p.val;
}
};
vector<int>stx[maxn*4],sty[maxn*4];//x for case 1 y for case 2
void build(int id,int l,int r){
for1(i,l,r)stx[id].pb(i);
for1(i,l,r)sty[id].pb(i);
sort(all(stx[id]),[](int i,int j){
return a[i].l+a[i].time>a[j].l+a[j].time;
});
sort(all(sty[id]),[](int i,int j){
return a[i].l-a[i].time>a[j].l-a[j].time;
});
if (l==r)return;
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
priority_queue<line>t;
void get(int id,int l,int r,int u,int v,int root,bool fl){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
while (!stx[id].empty()){
if (fl)break;
int tmp=stx[id].back();
if (vis[tmp]){
stx[id].pop_back();
continue;
}
if (a[tmp].l+a[tmp].time<=a[root].r+1+a[root].time){
vis[tmp]=1;
d[tmp]=d[root]+a[tmp].c;
t.push({tmp,d[tmp]});
stx[id].pop_back();
}
else break;
}
while (!sty[id].empty()){
if (!fl)break;
int tmp=sty[id].back();
if (vis[tmp]){
sty[id].pop_back();
continue;
}
if (a[tmp].l-a[tmp].time<=a[root].r+1-a[root].time){
vis[tmp]=1;
d[tmp]=d[root]+a[tmp].c;
t.push({tmp,d[tmp]});
sty[id].pop_back();
}
else break;
}
return;
}
int mid=(l+r)/2;
get(id*2,l,mid,u,v,root,fl);
get(id*2+1,mid+1,r,u,v,root,fl);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("temp.INP","r",stdin);
//freopen("temp.OUT","w",stdout);
cin>>n>>m;
for1(i,1,m)cin>>a[i].time>>a[i].l>>a[i].r>>a[i].c;
sort(a+1,a+1+m);
build(1,1,m);
for1(i,1,m)d[i]=inf;
for1(i,1,m){
if (a[i].l==1){
t.push({i,a[i].c});
d[i]=a[i].c;
vis[i]=1;
}
}
while (!t.empty()){
auto u=t.top();
t.pop();
get(1,1,m,1,u.u-1,u.u,1);
get(1,1,m,u.u+1,m,u.u,0);
}
long long ans=inf;
for1(i,1,m)if (a[i].r==n)ans=min(ans,d[i]);
if (ans>=inf)ans=-1;
cout<<ans;
}
Compilation message
treatment.cpp: In function 'bool check(int, int)':
treatment.cpp:29:19: error: 'n' was not declared in this scope
29 | if (a[i].r == n)return 0;
| ^
