#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef pair<pii, int> piii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<" "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<" ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) return cout<<x<<"\n", 0;
#define SZ(x) ((int)x.size())
const int inf=1000010000;
const ll INF=10000000000100000ll; // 1e16
const int mod=1000000007;
const int MAXN=100010;
int n, m, q, k, u, v, x, y, t;
int L[MAXN], R[MAXN], T[MAXN], C[MAXN];
int T2[MAXN];
int mark[MAXN];
ll dist[MAXN], ans=INF;
priority_queue<pll, vector<pll>, greater<pll>> pq;
inline bool upd(ll &x, ll y){
if (x<=y) return 0;
x=y;
return 1;
}
struct Segment{
pii seg[MAXN<<1];
Segment(){
fill(seg, seg+2*MAXN, pii(2*inf, 0));
}
void Set(int pos, pll val){
for (seg[pos+=m]=val; pos>1; pos>>=1) seg[pos>>1]=min(seg[pos], seg[pos^1]);
}
pll Get(int l, int r){
pii res=seg[0];
for (l+=m, r+=m; l<r; l>>=1, r>>=1){
if (l&1) res=min(res, seg[l++]);
if (r&1) res=min(res, seg[--r]);
}
return res;
}
} seg1, seg2;
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
memset(dist, 63, sizeof(dist));
cin>>n>>m;
vector<pii> comp;
for (int i=1; i<=m; i++){
cin>>T[i]>>L[i]>>R[i]>>C[i];
L[i]--;
comp.pb({T[i], i});
}
sort(all(comp));
for (int i=0; i<n; i++) T2[comp[i].second]=i+1;
for (int i=1; i<=m; i++){
if (!L[i]) pq.push({dist[i]=C[i], i});
else{
seg1.Set(T2[i], {L[i]-T[i], i});
seg2.Set(T2[i], {L[i]+T[i], i});
}
}
while (pq.size()){
int v=pq.top().second;
pq.pop();
while (1){
int i=seg1.Get(1, T2[v]).second;
if (!i || L[i]-T[i]>R[v]-T[v]) break ;
seg1.Set(T2[i], seg1.seg[0]);
seg2.Set(T2[i], seg1.seg[0]);
pq.push({dist[i]=dist[v]+C[i], i});
}
while (1){
int i=seg2.Get(T2[v], m+1).second;
if (!i || L[i]+T[i]>R[v]+T[v]) break ;
seg1.Set(T2[i], seg1.seg[0]);
seg2.Set(T2[i], seg1.seg[0]);
pq.push({dist[i]=dist[v]+C[i], i});
}
}
for (int i=1; i<=m; i++) if (R[i]==n) upd(ans, dist[i]);
if (ans>=INF) ans=-1;
cout<<ans<<"\n";
return 0;
}
/*
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1
10 5
2 6 10 3
1 1 5 5
5 2 7 3
8 6 10 4
4 1 3 1
10 5
1 5 10 4
1 1 6 5
1 4 8 3
1 6 10 3
1 1 3 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
68 ms |
15420 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4172 KB |
Output is correct |
| 2 |
Runtime error |
13 ms |
8328 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4172 KB |
Output is correct |
| 2 |
Runtime error |
13 ms |
8328 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
68 ms |
15420 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
