// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int> pli;
const int maxn = 1e5 + 10;
const ll inf = 1e18 + 10;
int L[maxn], R[maxn], T[maxn], C[maxn];
const int MAXN2 = maxn * 40;
int VERTID, m;
vector<int> v[MAXN2];
bool mark[MAXN2];
ll dis[MAXN2];
void add_edge(int a, int b){
v[a].PB(b);
}
struct Segment{
vector<pii> v[4 * maxn];
vector<int> L[4 * maxn], R[4 * maxn];
function<bool(int, int)> f1, f2, f3; // tartib dim1 // tartib dim2 // sould I connect?
int arr[maxn];
void restart(function<bool(int, int)> _f1, function<bool(int, int)> _f2, function<bool(int, int)> _f3){
f1 = _f1, f2 = _f2, f3 = _f3;
/* for(int i = 0; i < 4 * maxn; i++)
v[i].clear(), L[i].clear(), R[i].clear();
iota(arr, arr + m, 0);
sort(arr, arr + m, f1);
build();*/
}
void build(int l = 0, int r = m, int id = 1){
if(r-l == 1){
v[id].PB({arr[l], VERTID++});
return;
}
int mid = (l+r) >> 1;
build(l, mid, 2*id);
build(mid, r, 2*id+1);
int pt1 = 0, pt2 = 0;
while(pt1 + pt2 < sz(v[2*id]) + sz(v[2*id+1])){
L[id].PB(pt1), R[id].PB(pt2);
if(pt2 == sz(v[2*id+1]) || (pt1 != sz(v[2*id]) && f2(v[2*id][pt1].F, v[2*id+1][pt2].F)))
v[id].PB({v[2*id][pt1++].F, VERTID++});
else
v[id].PB({v[2*id+1][pt2++].F, VERTID++});
}
for(int i = 0; i < sz(v[id])-1; i++)
add_edge(v[id][i].S, v[id][i+1].S);
for(pii p : v[id])
add_edge(p.S, p.F);
}
void add(int x, int l = 0, int r = m, int id = 1, int pos = -1){
/* if(id == 1){
int L = -1, R = m;
while(R-L > 1){
int mid = (L+R) >> 1;
if(f2(x, v[1][mid].F))
R = mid;
else
L = mid;
}
pos = R;
}
if(pos >= sz(v[id]) || f3(x, arr[r-1]) == 0)
return;
if(f3(x, arr[l])){
add_edge(x, v[id][pos].S);
return;
}
int mid = (l+r) >> 1;
add(x, l, mid, 2*id, L[id][pos]);
add(x, mid, r, 2*id+1, R[id][pos]);
*/
for(int i = 0; i < m; i++){
if(f3(x, i) && f2(x, i))
add_edge(x, i);
}
}
};Segment seg;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
int n;
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> T[i] >> L[i] >> R[i] >> C[i];
}
VERTID = m;
int S = VERTID++, E = VERTID++;
for(int i = 0; i < m; i++){
if(L[i] == 1)
add_edge(S, i);
if(R[i] == n)
add_edge(i, E);
}
{
auto A = [](int i){ return R[i] + T[i]; };
auto B = [](int i){ return +T[i] + L[i] -1; };
seg.restart([&](int i, int j){ return B(i) > B(j); }, [](int i, int j){ return T[i] <= T[j]; }, [&](int x, int S){ return A(x) >= B(S); });
for(int i = 0; i < m; i++)
seg.add(i);
}
{
auto A = [](int i){ return R[i] - T[i]; };
auto B = [](int i){ return -T[i] + L[i] -1; };
seg.restart([&](int i, int j){ return B(i) > B(j); }, [](int i, int j){ return T[i] >= T[j]; }, [&](int x, int S){ return A(x) >= B(S); });
for(int i = 0; i < m; i++)
seg.add(i);
}
priority_queue<pli, vector<pli>, greater<pli> > pq;
fill(dis, dis + VERTID, inf);
pq.push({0, S});
dis[S] = 0;
while(sz(pq)){
int u = pq.top().S;
pq.pop();
if(mark[u])
continue;
mark[u] = 1;
for(int y : v[u]){
ll x = dis[u] + (y < m ? C[y] : 0);
if(dis[y] > x)
dis[y] = x, pq.push({dis[y], y});
}
}
ll ans = dis[E];
if(ans == inf)
ans = -1;
return cout << ans << endl, 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2113 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
122488 KB |
Output is correct |
2 |
Correct |
83 ms |
122488 KB |
Output is correct |
3 |
Correct |
87 ms |
122488 KB |
Output is correct |
4 |
Correct |
84 ms |
122488 KB |
Output is correct |
5 |
Correct |
82 ms |
122488 KB |
Output is correct |
6 |
Correct |
82 ms |
122488 KB |
Output is correct |
7 |
Correct |
95 ms |
122488 KB |
Output is correct |
8 |
Correct |
83 ms |
122488 KB |
Output is correct |
9 |
Correct |
82 ms |
122488 KB |
Output is correct |
10 |
Correct |
86 ms |
122632 KB |
Output is correct |
11 |
Correct |
87 ms |
122488 KB |
Output is correct |
12 |
Correct |
81 ms |
122488 KB |
Output is correct |
13 |
Correct |
84 ms |
122488 KB |
Output is correct |
14 |
Correct |
81 ms |
122520 KB |
Output is correct |
15 |
Correct |
82 ms |
122620 KB |
Output is correct |
16 |
Correct |
84 ms |
122488 KB |
Output is correct |
17 |
Correct |
84 ms |
122488 KB |
Output is correct |
18 |
Correct |
82 ms |
122484 KB |
Output is correct |
19 |
Correct |
83 ms |
122488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
122488 KB |
Output is correct |
2 |
Correct |
83 ms |
122488 KB |
Output is correct |
3 |
Correct |
87 ms |
122488 KB |
Output is correct |
4 |
Correct |
84 ms |
122488 KB |
Output is correct |
5 |
Correct |
82 ms |
122488 KB |
Output is correct |
6 |
Correct |
82 ms |
122488 KB |
Output is correct |
7 |
Correct |
95 ms |
122488 KB |
Output is correct |
8 |
Correct |
83 ms |
122488 KB |
Output is correct |
9 |
Correct |
82 ms |
122488 KB |
Output is correct |
10 |
Correct |
86 ms |
122632 KB |
Output is correct |
11 |
Correct |
87 ms |
122488 KB |
Output is correct |
12 |
Correct |
81 ms |
122488 KB |
Output is correct |
13 |
Correct |
84 ms |
122488 KB |
Output is correct |
14 |
Correct |
81 ms |
122520 KB |
Output is correct |
15 |
Correct |
82 ms |
122620 KB |
Output is correct |
16 |
Correct |
84 ms |
122488 KB |
Output is correct |
17 |
Correct |
84 ms |
122488 KB |
Output is correct |
18 |
Correct |
82 ms |
122484 KB |
Output is correct |
19 |
Correct |
83 ms |
122488 KB |
Output is correct |
20 |
Correct |
715 ms |
194268 KB |
Output is correct |
21 |
Correct |
743 ms |
194524 KB |
Output is correct |
22 |
Correct |
540 ms |
124760 KB |
Output is correct |
23 |
Correct |
535 ms |
124664 KB |
Output is correct |
24 |
Correct |
519 ms |
172280 KB |
Output is correct |
25 |
Correct |
402 ms |
158328 KB |
Output is correct |
26 |
Correct |
361 ms |
156756 KB |
Output is correct |
27 |
Correct |
393 ms |
163744 KB |
Output is correct |
28 |
Correct |
490 ms |
171768 KB |
Output is correct |
29 |
Correct |
402 ms |
157816 KB |
Output is correct |
30 |
Correct |
375 ms |
162040 KB |
Output is correct |
31 |
Correct |
373 ms |
166264 KB |
Output is correct |
32 |
Correct |
715 ms |
190072 KB |
Output is correct |
33 |
Correct |
728 ms |
232392 KB |
Output is correct |
34 |
Correct |
672 ms |
187896 KB |
Output is correct |
35 |
Correct |
732 ms |
190076 KB |
Output is correct |
36 |
Correct |
723 ms |
232232 KB |
Output is correct |
37 |
Correct |
694 ms |
187952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2113 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |