#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 1e5+10;
const lint LNF = 2e18;
inline lint _min(lint a, lint b){ return a<b ? a : b; }
/*
cost(i): 각 장치 i에 대해서, 이 장치가 마지막일 최소 비용.
L[x], R[x]를 관리한다.
L[x]: 1에서 x로 갈 최소 비용
R[x]: n에서 x로 갈 최소 비용
cost(i) = min_{A[i]<=k<=B[i]}(L[k]) + min_{A[i]<=k<=B[i]}(R[k]) + D[i]
만약 A[i]<=k<=B[i]에 대해서, L[k]<LNF이면 L[C[i]] = min(L[k]) + D[i]
*/
class Coord_t{
vector<int> P;
public:
void add(int p){
P.push_back(p);
}
int compress(){
sort(P.begin(), P.end());
int res = unique(P.begin(), P.end()) - P.begin();
P.resize(res);
return res;
}
int get_lo(int p){
// 이하인 최대
return upper_bound(P.begin(), P.end(), p) - P.begin() - 1 + 1;
}
int get_hi(int p){
// 이상인 최소
return lower_bound(P.begin(), P.end(), p) - P.begin() + 1;
}
int get(int p){
if(!binary_search(P.begin(), P.end(), p)){ cerr<<"SHIT\n"; exit(42); }
return get_lo(p);
}
} Coord;
class Seg_t{
int n;
lint T[1<<18];
void add(int v, int s, int e, int p, lint val){
if(s==e){ T[v] = _min(T[v], val); return; }
int mid = (s+e)/2;
if(p<=mid) add(v*2,s,mid,p,val);
else add(v*2+1,mid+1,e,p,val);
T[v] = _min(T[v*2], T[v*2+1]);
}
lint mn(int v, int s, int e, int l, int r){
if(e<l || r<s) return LNF;
if(l<=s && e<=r) return T[v];
return _min(mn(v*2,s,(s+e)/2,l,r), mn(v*2+1,(s+e)/2+1,e,l,r));
}
public:
void init(int sz){
n = sz;
for(int i=0; i<(1<<18); i++) T[i] = LNF;
}
void add(int p, lint val){
p = Coord.get(p);
if(p<1 || n<p){ cerr<<"SHIIT\n"; exit(42); }
add(1,1,n,p,val);
}
lint mn(int l, int r){
l = Coord.get_hi(l), r = Coord.get_lo(r);
if(l>n || r<1) return LNF;
return mn(1,1,n,l,r);
}
} LSeg, RSeg;
int main(){
ios::sync_with_stdio(0); cin.tie(0);
static int A[MAX], B[MAX], C[MAX], D[MAX];
int n, m; cin>>m>>n;
for(int i=1; i<=m; i++){
cin>>A[i]>>B[i]>>C[i]>>D[i];
Coord.add(C[i]);
}
Coord.add(1); Coord.add(n);
int sz = Coord.compress();
LSeg.init(sz); RSeg.init(sz);
LSeg.add(1, 0); RSeg.add(n, 0);
lint ans = LNF;
for(int i=1; i<=m; i++){
// for(int i=1; i<=sz; i++){
// int x = Coord.P[i-1];
// cout<<LSeg.mn(x,x)<<' '<<RSeg.mn(x,x)<<'\n';
// }
// cout<<'\n';
lint lft = LSeg.mn(A[i], B[i]);
lint rig = RSeg.mn(A[i], B[i]);
ans = min(ans, lft+rig+D[i]);
if(lft<LNF) LSeg.add(C[i], lft+D[i]);
if(rig<LNF) RSeg.add(C[i], rig+D[i]);
}
if(ans>=LNF) ans = -1;
cout<<ans<<'\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4480 KB |
Output is correct |
2 |
Correct |
6 ms |
4480 KB |
Output is correct |
3 |
Correct |
6 ms |
4480 KB |
Output is correct |
4 |
Correct |
5 ms |
4480 KB |
Output is correct |
5 |
Correct |
5 ms |
4480 KB |
Output is correct |
6 |
Correct |
5 ms |
4480 KB |
Output is correct |
7 |
Correct |
6 ms |
4480 KB |
Output is correct |
8 |
Correct |
5 ms |
4480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4480 KB |
Output is correct |
2 |
Correct |
6 ms |
4480 KB |
Output is correct |
3 |
Correct |
6 ms |
4480 KB |
Output is correct |
4 |
Correct |
5 ms |
4480 KB |
Output is correct |
5 |
Correct |
5 ms |
4480 KB |
Output is correct |
6 |
Correct |
5 ms |
4480 KB |
Output is correct |
7 |
Correct |
6 ms |
4480 KB |
Output is correct |
8 |
Correct |
5 ms |
4480 KB |
Output is correct |
9 |
Correct |
7 ms |
4480 KB |
Output is correct |
10 |
Correct |
6 ms |
4480 KB |
Output is correct |
11 |
Correct |
6 ms |
4480 KB |
Output is correct |
12 |
Correct |
6 ms |
4480 KB |
Output is correct |
13 |
Correct |
6 ms |
4480 KB |
Output is correct |
14 |
Correct |
6 ms |
4480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4480 KB |
Output is correct |
2 |
Correct |
6 ms |
4480 KB |
Output is correct |
3 |
Correct |
6 ms |
4480 KB |
Output is correct |
4 |
Correct |
5 ms |
4480 KB |
Output is correct |
5 |
Correct |
5 ms |
4480 KB |
Output is correct |
6 |
Correct |
5 ms |
4480 KB |
Output is correct |
7 |
Correct |
6 ms |
4480 KB |
Output is correct |
8 |
Correct |
5 ms |
4480 KB |
Output is correct |
9 |
Correct |
7 ms |
4480 KB |
Output is correct |
10 |
Correct |
6 ms |
4480 KB |
Output is correct |
11 |
Correct |
6 ms |
4480 KB |
Output is correct |
12 |
Correct |
6 ms |
4480 KB |
Output is correct |
13 |
Correct |
6 ms |
4480 KB |
Output is correct |
14 |
Correct |
6 ms |
4480 KB |
Output is correct |
15 |
Correct |
6 ms |
4480 KB |
Output is correct |
16 |
Correct |
6 ms |
4480 KB |
Output is correct |
17 |
Correct |
8 ms |
4480 KB |
Output is correct |
18 |
Correct |
9 ms |
4608 KB |
Output is correct |
19 |
Correct |
9 ms |
4480 KB |
Output is correct |
20 |
Correct |
8 ms |
4480 KB |
Output is correct |
21 |
Correct |
7 ms |
4608 KB |
Output is correct |
22 |
Correct |
8 ms |
4452 KB |
Output is correct |
23 |
Correct |
6 ms |
4480 KB |
Output is correct |
24 |
Correct |
8 ms |
4480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4480 KB |
Output is correct |
2 |
Correct |
6 ms |
4480 KB |
Output is correct |
3 |
Correct |
6 ms |
4480 KB |
Output is correct |
4 |
Correct |
5 ms |
4480 KB |
Output is correct |
5 |
Correct |
5 ms |
4480 KB |
Output is correct |
6 |
Correct |
5 ms |
4480 KB |
Output is correct |
7 |
Correct |
6 ms |
4480 KB |
Output is correct |
8 |
Correct |
5 ms |
4480 KB |
Output is correct |
9 |
Correct |
7 ms |
4480 KB |
Output is correct |
10 |
Correct |
6 ms |
4480 KB |
Output is correct |
11 |
Correct |
6 ms |
4480 KB |
Output is correct |
12 |
Correct |
6 ms |
4480 KB |
Output is correct |
13 |
Correct |
6 ms |
4480 KB |
Output is correct |
14 |
Correct |
6 ms |
4480 KB |
Output is correct |
15 |
Correct |
6 ms |
4480 KB |
Output is correct |
16 |
Correct |
6 ms |
4480 KB |
Output is correct |
17 |
Correct |
8 ms |
4480 KB |
Output is correct |
18 |
Correct |
9 ms |
4608 KB |
Output is correct |
19 |
Correct |
9 ms |
4480 KB |
Output is correct |
20 |
Correct |
8 ms |
4480 KB |
Output is correct |
21 |
Correct |
7 ms |
4608 KB |
Output is correct |
22 |
Correct |
8 ms |
4452 KB |
Output is correct |
23 |
Correct |
6 ms |
4480 KB |
Output is correct |
24 |
Correct |
8 ms |
4480 KB |
Output is correct |
25 |
Correct |
25 ms |
4992 KB |
Output is correct |
26 |
Correct |
65 ms |
6000 KB |
Output is correct |
27 |
Correct |
209 ms |
8496 KB |
Output is correct |
28 |
Correct |
210 ms |
10428 KB |
Output is correct |
29 |
Correct |
129 ms |
7516 KB |
Output is correct |
30 |
Correct |
228 ms |
10456 KB |
Output is correct |
31 |
Correct |
335 ms |
10368 KB |
Output is correct |
32 |
Correct |
316 ms |
10448 KB |
Output is correct |
33 |
Correct |
46 ms |
5564 KB |
Output is correct |
34 |
Correct |
108 ms |
7416 KB |
Output is correct |
35 |
Correct |
156 ms |
10328 KB |
Output is correct |
36 |
Correct |
295 ms |
10420 KB |
Output is correct |
37 |
Correct |
235 ms |
10384 KB |
Output is correct |
38 |
Correct |
221 ms |
10364 KB |
Output is correct |