#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int SIZE = 1<<19;
struct ST{
ll data[2*SIZE];
void init(){fill(data, data+2*SIZE, 1e18);}
void update(int x, ll v){
for(x+=SIZE; x; x>>=1) data[x] = min(data[x], v);
}
ll query(int s, int e){
ll ret = 1e18;
for(s+=SIZE, e+=SIZE; s<=e; s>>=1, e>>=1){
if( s&1) ret = min(ret, data[s++]);
if(~e&1) ret = min(ret, data[e--]);
}
return ret;
}
} seg1, seg2;
int A[100000], B[100000], C[100000], D[100000];
vector<int> xx;
int main(){
ios_base::sync_with_stdio(0), cin.tie(0);
int M, N; cin>>M>>N;
for(int i=0; i<M; ++i){
cin>>A[i]>>B[i]>>C[i]>>D[i];
xx.push_back(A[i]), xx.push_back(B[i]), xx.push_back(C[i]);
}
xx.push_back(1), xx.push_back(N);
sort(xx.begin(), xx.end()), xx.erase(unique(xx.begin(), xx.end()), xx.end());
for(int i=0; i<M; ++i){
A[i] = lower_bound(xx.begin(), xx.end(), A[i]) - xx.begin();
B[i] = lower_bound(xx.begin(), xx.end(), B[i]) - xx.begin();
C[i] = lower_bound(xx.begin(), xx.end(), C[i]) - xx.begin();
}
seg1.init(), seg2.init(), seg1.update(0, 0), seg2.update(xx.size()-1, 0);
long long ans = 1e18;
for(int i=0; i<M; ++i){
ll s = seg1.query(A[i], C[i]-1), t = seg2.query(C[i]+1, B[i]);
if(seg1.query(C[i], C[i]) > D[i] + s) seg1.update(C[i], D[i] + s);
if(seg2.query(C[i], C[i]) > D[i] + t) seg2.update(C[i], D[i] + t);
ans = min(ans, D[i] + s + t);
}
if(ans == 1e18) ans = -1;
cout<<ans;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 3 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 4 |
Correct |
17 ms |
16744 KB |
Output is correct |
| 5 |
Correct |
17 ms |
16820 KB |
Output is correct |
| 6 |
Correct |
18 ms |
16768 KB |
Output is correct |
| 7 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 8 |
Correct |
18 ms |
16768 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 3 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 4 |
Correct |
17 ms |
16744 KB |
Output is correct |
| 5 |
Correct |
17 ms |
16820 KB |
Output is correct |
| 6 |
Correct |
18 ms |
16768 KB |
Output is correct |
| 7 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 8 |
Correct |
18 ms |
16768 KB |
Output is correct |
| 9 |
Correct |
20 ms |
16768 KB |
Output is correct |
| 10 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 11 |
Incorrect |
16 ms |
16768 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 3 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 4 |
Correct |
17 ms |
16744 KB |
Output is correct |
| 5 |
Correct |
17 ms |
16820 KB |
Output is correct |
| 6 |
Correct |
18 ms |
16768 KB |
Output is correct |
| 7 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 8 |
Correct |
18 ms |
16768 KB |
Output is correct |
| 9 |
Correct |
20 ms |
16768 KB |
Output is correct |
| 10 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 11 |
Incorrect |
16 ms |
16768 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 3 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 4 |
Correct |
17 ms |
16744 KB |
Output is correct |
| 5 |
Correct |
17 ms |
16820 KB |
Output is correct |
| 6 |
Correct |
18 ms |
16768 KB |
Output is correct |
| 7 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 8 |
Correct |
18 ms |
16768 KB |
Output is correct |
| 9 |
Correct |
20 ms |
16768 KB |
Output is correct |
| 10 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 11 |
Incorrect |
16 ms |
16768 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
