/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
const ll INF = 1e18;
int n, m;
array<ll, 4> a[N];
ll dp[N];
array<ll, 2> T[N][2];
bool check(int i, int j){ // i to j
return abs(a[i][2] - a[j][2]) <= a[i][1] - a[j][0] + 1;
}
void build(int l, int r, int k){
if(l == r){
T[k][0] = {a[l][1] - a[l][0], l};
T[k][1] = {a[l][1] + a[l][0], l};
return;
}
int mid = l+r>>1;
build(l, mid, k<<1);
build(mid+1, r, k<<1|1);
if(T[k<<1][0] <= T[k<<1|1][0]) T[k][0] = T[k<<1][0];
else T[k][0] = T[k<<1|1][0];
if(T[k<<1][1] <= T[k<<1|1][1]) T[k][1] = T[k<<1][1];
else T[k][1] = T[k<<1|1][1];
}
array<ll, 2> get(int l, int r, int ql, int qr, int k){
if(ql > r || l > qr) return array<ll, 2> {-1, -1};
if(ql <= l && r <= qr) return T[k][0];
int mid = l+r>>1;
auto L = get(l, mid, ql, qr, k<<1);
auto R = get(mid+1, r, ql, qr, k<<1|1);
if(L[0] == -1) return R;
if(R[0] == -1) return L;
if(L[0] >= R[0]) return R;
return L;
}
array<ll, 2> get2(int l, int r, int ql, int qr, int k){
if(ql > r || l > qr) return array<ll, 2> {-1, -1};
if(ql <= l && r <= qr) return T[k][1];
int mid = l+r>>1;
auto L = get2(l, mid, ql, qr, k<<1);
auto R = get2(mid+1, r, ql, qr, k<<1|1);
if(L[0] == -1) return R;
if(R[0] == -1) return L;
if(L[0] >= R[0]) return R;
return L;
}
void upd(int l, int r, int p, int k){
if(l == r){
T[k][0] = {-1, -1};
T[k][1] = {-1, -1};
return;
}
int mid = l+r>>1;
if(p <= mid) upd(l, mid, p, k<<1);
else upd(mid+1, r, p, k<<1|1);
if(T[k<<1][0][0] == -1) T[k][0] = T[k<<1|1][0];
else if(T[k<<1|1][0][0] == -1) T[k][0] = T[k<<1][0];
else if(T[k<<1][0] <= T[k<<1|1][0]) T[k][0] = T[k<<1][0];
else T[k][0] = T[k<<1|1][0];
if(T[k<<1][1][0] == -1) T[k][1] = T[k<<1|1][1];
else if(T[k<<1|1][1][0] == -1) T[k][1] = T[k<<1][1];
else if(T[k<<1][1] <= T[k<<1|1][1]) T[k][1] = T[k<<1][1];
else T[k][1] = T[k<<1|1][1];
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= m; ++i){
cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
}
sort(a+1, a+1+m);
ll ans = INF;
vector<ll> dist(m + 1, INF);
build(1, m, 1);
set<pair<ll, int>> S;
for(int i = 1; i <= m; ++i){
if(a[i][1] == 1){
dist[i] = a[i][3];
upd(1, m, i, 1); // just set it offline
S.insert({dist[i], i});
}
}
while(S.size()){
int v = (*S.begin()).ss;
S.erase(S.begin());
array<ll, 2> u = {-1, -1};
u = get(1, m, 1, v - 1, 1);
while(u[1] != -1 && u[0] <= a[v][2] - a[v][0] + 1){
upd(1, m, u[1], 1);
dist[u[1]] = a[u[1]][3] + dist[v];
S.insert({dist[u[1]], u[1]});
u = get(1, m, 1, v - 1, 1);
}
u = {-1, -1};
u = get2(1, m, v + 1, m, 1);
while(u[1] != -1 && u[0] <= a[v][2] + a[v][0] + 1){
upd(1, m, u[1], 1);
dist[u[1]] = a[u[1]][3] + dist[v];
S.insert({dist[u[1]], u[1]});
u = get2(1, m, v + 1, m, 1);
}
}
for(int i = 1; i <= m; ++i){
if(a[i][2] == n){
ans = min(ans, dist[i]);
}
}
if(ans==INF){
cout << -1;
}else{
cout << ans;
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
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... |