#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<m; 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 |
Correct |
218 ms |
6976 KB |
Output is correct |
2 |
Correct |
135 ms |
10260 KB |
Output is correct |
3 |
Correct |
173 ms |
10688 KB |
Output is correct |
4 |
Correct |
203 ms |
10084 KB |
Output is correct |
5 |
Correct |
154 ms |
12356 KB |
Output is correct |
6 |
Correct |
154 ms |
10264 KB |
Output is correct |
7 |
Correct |
133 ms |
10176 KB |
Output is correct |
8 |
Correct |
80 ms |
10124 KB |
Output is correct |
9 |
Correct |
80 ms |
10132 KB |
Output is correct |
10 |
Correct |
80 ms |
10196 KB |
Output is correct |
11 |
Correct |
173 ms |
12228 KB |
Output is correct |
12 |
Correct |
162 ms |
12276 KB |
Output is correct |
13 |
Correct |
193 ms |
12244 KB |
Output is correct |
14 |
Correct |
180 ms |
12224 KB |
Output is correct |
15 |
Correct |
194 ms |
10116 KB |
Output is correct |
16 |
Correct |
189 ms |
10132 KB |
Output is correct |
17 |
Correct |
187 ms |
9356 KB |
Output is correct |
18 |
Correct |
171 ms |
11488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4172 KB |
Output is correct |
2 |
Correct |
8 ms |
4156 KB |
Output is correct |
3 |
Correct |
8 ms |
4172 KB |
Output is correct |
4 |
Correct |
8 ms |
4172 KB |
Output is correct |
5 |
Correct |
5 ms |
4172 KB |
Output is correct |
6 |
Correct |
9 ms |
4184 KB |
Output is correct |
7 |
Correct |
3 ms |
4300 KB |
Output is correct |
8 |
Correct |
8 ms |
4172 KB |
Output is correct |
9 |
Correct |
8 ms |
4236 KB |
Output is correct |
10 |
Correct |
8 ms |
4172 KB |
Output is correct |
11 |
Correct |
8 ms |
4160 KB |
Output is correct |
12 |
Correct |
4 ms |
4172 KB |
Output is correct |
13 |
Correct |
4 ms |
4236 KB |
Output is correct |
14 |
Correct |
8 ms |
4172 KB |
Output is correct |
15 |
Correct |
8 ms |
4172 KB |
Output is correct |
16 |
Correct |
8 ms |
4172 KB |
Output is correct |
17 |
Correct |
8 ms |
4160 KB |
Output is correct |
18 |
Correct |
8 ms |
4172 KB |
Output is correct |
19 |
Correct |
8 ms |
4168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4172 KB |
Output is correct |
2 |
Correct |
8 ms |
4156 KB |
Output is correct |
3 |
Correct |
8 ms |
4172 KB |
Output is correct |
4 |
Correct |
8 ms |
4172 KB |
Output is correct |
5 |
Correct |
5 ms |
4172 KB |
Output is correct |
6 |
Correct |
9 ms |
4184 KB |
Output is correct |
7 |
Correct |
3 ms |
4300 KB |
Output is correct |
8 |
Correct |
8 ms |
4172 KB |
Output is correct |
9 |
Correct |
8 ms |
4236 KB |
Output is correct |
10 |
Correct |
8 ms |
4172 KB |
Output is correct |
11 |
Correct |
8 ms |
4160 KB |
Output is correct |
12 |
Correct |
4 ms |
4172 KB |
Output is correct |
13 |
Correct |
4 ms |
4236 KB |
Output is correct |
14 |
Correct |
8 ms |
4172 KB |
Output is correct |
15 |
Correct |
8 ms |
4172 KB |
Output is correct |
16 |
Correct |
8 ms |
4172 KB |
Output is correct |
17 |
Correct |
8 ms |
4160 KB |
Output is correct |
18 |
Correct |
8 ms |
4172 KB |
Output is correct |
19 |
Correct |
8 ms |
4168 KB |
Output is correct |
20 |
Correct |
14 ms |
4548 KB |
Output is correct |
21 |
Correct |
11 ms |
4504 KB |
Output is correct |
22 |
Correct |
13 ms |
4644 KB |
Output is correct |
23 |
Correct |
13 ms |
4540 KB |
Output is correct |
24 |
Correct |
15 ms |
4624 KB |
Output is correct |
25 |
Correct |
15 ms |
4556 KB |
Output is correct |
26 |
Correct |
9 ms |
4652 KB |
Output is correct |
27 |
Correct |
14 ms |
4652 KB |
Output is correct |
28 |
Correct |
10 ms |
4684 KB |
Output is correct |
29 |
Correct |
11 ms |
4632 KB |
Output is correct |
30 |
Correct |
12 ms |
4568 KB |
Output is correct |
31 |
Correct |
9 ms |
4556 KB |
Output is correct |
32 |
Correct |
10 ms |
4800 KB |
Output is correct |
33 |
Correct |
13 ms |
4772 KB |
Output is correct |
34 |
Correct |
16 ms |
4632 KB |
Output is correct |
35 |
Correct |
15 ms |
4696 KB |
Output is correct |
36 |
Correct |
15 ms |
4696 KB |
Output is correct |
37 |
Correct |
13 ms |
4508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
218 ms |
6976 KB |
Output is correct |
2 |
Correct |
135 ms |
10260 KB |
Output is correct |
3 |
Correct |
173 ms |
10688 KB |
Output is correct |
4 |
Correct |
203 ms |
10084 KB |
Output is correct |
5 |
Correct |
154 ms |
12356 KB |
Output is correct |
6 |
Correct |
154 ms |
10264 KB |
Output is correct |
7 |
Correct |
133 ms |
10176 KB |
Output is correct |
8 |
Correct |
80 ms |
10124 KB |
Output is correct |
9 |
Correct |
80 ms |
10132 KB |
Output is correct |
10 |
Correct |
80 ms |
10196 KB |
Output is correct |
11 |
Correct |
173 ms |
12228 KB |
Output is correct |
12 |
Correct |
162 ms |
12276 KB |
Output is correct |
13 |
Correct |
193 ms |
12244 KB |
Output is correct |
14 |
Correct |
180 ms |
12224 KB |
Output is correct |
15 |
Correct |
194 ms |
10116 KB |
Output is correct |
16 |
Correct |
189 ms |
10132 KB |
Output is correct |
17 |
Correct |
187 ms |
9356 KB |
Output is correct |
18 |
Correct |
171 ms |
11488 KB |
Output is correct |
19 |
Correct |
8 ms |
4172 KB |
Output is correct |
20 |
Correct |
8 ms |
4156 KB |
Output is correct |
21 |
Correct |
8 ms |
4172 KB |
Output is correct |
22 |
Correct |
8 ms |
4172 KB |
Output is correct |
23 |
Correct |
5 ms |
4172 KB |
Output is correct |
24 |
Correct |
9 ms |
4184 KB |
Output is correct |
25 |
Correct |
3 ms |
4300 KB |
Output is correct |
26 |
Correct |
8 ms |
4172 KB |
Output is correct |
27 |
Correct |
8 ms |
4236 KB |
Output is correct |
28 |
Correct |
8 ms |
4172 KB |
Output is correct |
29 |
Correct |
8 ms |
4160 KB |
Output is correct |
30 |
Correct |
4 ms |
4172 KB |
Output is correct |
31 |
Correct |
4 ms |
4236 KB |
Output is correct |
32 |
Correct |
8 ms |
4172 KB |
Output is correct |
33 |
Correct |
8 ms |
4172 KB |
Output is correct |
34 |
Correct |
8 ms |
4172 KB |
Output is correct |
35 |
Correct |
8 ms |
4160 KB |
Output is correct |
36 |
Correct |
8 ms |
4172 KB |
Output is correct |
37 |
Correct |
8 ms |
4168 KB |
Output is correct |
38 |
Correct |
14 ms |
4548 KB |
Output is correct |
39 |
Correct |
11 ms |
4504 KB |
Output is correct |
40 |
Correct |
13 ms |
4644 KB |
Output is correct |
41 |
Correct |
13 ms |
4540 KB |
Output is correct |
42 |
Correct |
15 ms |
4624 KB |
Output is correct |
43 |
Correct |
15 ms |
4556 KB |
Output is correct |
44 |
Correct |
9 ms |
4652 KB |
Output is correct |
45 |
Correct |
14 ms |
4652 KB |
Output is correct |
46 |
Correct |
10 ms |
4684 KB |
Output is correct |
47 |
Correct |
11 ms |
4632 KB |
Output is correct |
48 |
Correct |
12 ms |
4568 KB |
Output is correct |
49 |
Correct |
9 ms |
4556 KB |
Output is correct |
50 |
Correct |
10 ms |
4800 KB |
Output is correct |
51 |
Correct |
13 ms |
4772 KB |
Output is correct |
52 |
Correct |
16 ms |
4632 KB |
Output is correct |
53 |
Correct |
15 ms |
4696 KB |
Output is correct |
54 |
Correct |
15 ms |
4696 KB |
Output is correct |
55 |
Correct |
13 ms |
4508 KB |
Output is correct |
56 |
Correct |
183 ms |
10984 KB |
Output is correct |
57 |
Correct |
166 ms |
11380 KB |
Output is correct |
58 |
Correct |
159 ms |
9412 KB |
Output is correct |
59 |
Correct |
167 ms |
9696 KB |
Output is correct |
60 |
Correct |
164 ms |
10408 KB |
Output is correct |
61 |
Correct |
150 ms |
9276 KB |
Output is correct |
62 |
Correct |
166 ms |
10916 KB |
Output is correct |
63 |
Correct |
148 ms |
10316 KB |
Output is correct |
64 |
Correct |
141 ms |
10304 KB |
Output is correct |
65 |
Correct |
205 ms |
10324 KB |
Output is correct |
66 |
Correct |
153 ms |
10440 KB |
Output is correct |
67 |
Correct |
189 ms |
10944 KB |
Output is correct |
68 |
Correct |
176 ms |
10956 KB |
Output is correct |
69 |
Correct |
169 ms |
10964 KB |
Output is correct |
70 |
Correct |
191 ms |
11048 KB |
Output is correct |
71 |
Correct |
179 ms |
10912 KB |
Output is correct |
72 |
Correct |
161 ms |
10944 KB |
Output is correct |
73 |
Correct |
241 ms |
10988 KB |
Output is correct |
74 |
Correct |
88 ms |
10944 KB |
Output is correct |
75 |
Correct |
92 ms |
10872 KB |
Output is correct |
76 |
Correct |
224 ms |
12716 KB |
Output is correct |
77 |
Correct |
203 ms |
13084 KB |
Output is correct |
78 |
Correct |
208 ms |
12532 KB |
Output is correct |
79 |
Correct |
216 ms |
10928 KB |
Output is correct |
80 |
Correct |
219 ms |
10532 KB |
Output is correct |
81 |
Correct |
103 ms |
10884 KB |
Output is correct |
82 |
Correct |
215 ms |
9796 KB |
Output is correct |
83 |
Correct |
203 ms |
10044 KB |
Output is correct |
84 |
Correct |
211 ms |
10088 KB |
Output is correct |
85 |
Correct |
155 ms |
10940 KB |
Output is correct |
86 |
Correct |
151 ms |
10972 KB |
Output is correct |
87 |
Correct |
199 ms |
10968 KB |
Output is correct |
88 |
Correct |
169 ms |
11020 KB |
Output is correct |
89 |
Correct |
174 ms |
10940 KB |
Output is correct |
90 |
Correct |
208 ms |
12944 KB |
Output is correct |
91 |
Correct |
190 ms |
12452 KB |
Output is correct |
92 |
Correct |
164 ms |
10860 KB |
Output is correct |
93 |
Correct |
265 ms |
10944 KB |
Output is correct |
94 |
Correct |
205 ms |
11032 KB |
Output is correct |
95 |
Correct |
190 ms |
10856 KB |
Output is correct |
96 |
Correct |
201 ms |
13124 KB |
Output is correct |
97 |
Correct |
224 ms |
12928 KB |
Output is correct |
98 |
Correct |
185 ms |
12952 KB |
Output is correct |
99 |
Correct |
226 ms |
13024 KB |
Output is correct |
100 |
Correct |
230 ms |
12888 KB |
Output is correct |
101 |
Correct |
196 ms |
12996 KB |
Output is correct |
102 |
Correct |
196 ms |
12932 KB |
Output is correct |
103 |
Correct |
156 ms |
11328 KB |
Output is correct |