#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
struct pr {
ll l, r, mid, cost;
};
struct segtree {
vector<ll> st, arr; ll n;
ll merge(ll a, ll b){
return min(a, b);
}
void init(ll x, vector<ll> y){
n = x;
arr = y;
st.assign(4 * n, 0);
build(1, 0, n - 1);
}
void build(ll idx, ll l, ll r){
if(l != r){
ll mid = l + (r - l) / 2;
build(2 * idx, l, mid);
build(2 * idx + 1, mid + 1, r);
st[idx] = merge(st[2 * idx], st[2 * idx + 1]);
}
else {
st[idx] = arr[l];
return;
}
}
void update1(ll idx, ll l, ll r, ll pos, ll val){
if(l != r){
ll mid = l + (r - l) / 2;
if(pos <= mid)
update1(2 * idx, l, mid, pos, val);
else
update1(2 * idx + 1, mid + 1, r, pos, val);
st[idx] = merge(st[2 * idx], st[2 * idx + 1]);
}
else {
st[idx] = val;
return;
}
}
void update2(ll pos, ll val){
update1(1, 0, n-1, pos, val);
}
ll query1(ll idx, ll r_l, ll r_r, ll q_l, ll q_r){
if(q_r >= r_r && q_l <= r_l)
return st[idx];
if(q_l > r_r || q_r < r_l)
return 1e18;
ll mid = r_l + (r_r - r_l) / 2;
return merge(query1(2 * idx, r_l, mid, q_l, q_r), query1(2 * idx + 1, mid + 1, r_r, q_l, q_r));
}
ll query2(ll q_l, ll q_r){
return query1(1, 0, n - 1, q_l, q_r);
}
};
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
ll m, n;
cin >> m >> n;
vector<pr> v(m);
set<ll> s;
s.insert(0);
for(ll i=0;i<m;i++){
cin >> v[i].l >> v[i].r >> v[i].mid >> v[i].cost;
--v[i].l; s.insert(v[i].l);
--v[i].mid; s.insert(v[i].mid);
--v[i].r; s.insert(v[i].r);
}
s.insert(n - 1);
map<ll, ll> pos;
ll new_pos = 0;
for(auto x : s)
pos[x] = new_pos++;
for(ll i=0;i<m;i++){
v[i].l = pos[v[i].l];
v[i].mid = pos[v[i].mid];
v[i].r = pos[v[i].r];
}
segtree ST;
vector<ll> dpL(m, 1e18);
ST.init(m, dpL);
for(ll i=0;i<m;i++){
if(v[i].l == 0){
dpL[i] = v[i].cost;
ST.update2(v[i].mid, dpL[i]);
continue;
}
ll val = ST.query2(v[i].l, v[i].r);
dpL[i] = min(dpL[i], val + v[i].cost);
ST.update2(v[i].mid, dpL[i]);
}
vector<ll> dpR(m, 1e18);
ST.init(m, dpR);
for(ll i=0;i<m;i++){
if(v[i].r == n - 1){
dpR[i] = v[i].cost;
ST.update2(v[i].mid, dpR[i]);
continue;
}
ll val = ST.query2(v[i].l, v[i].r);
dpR[i] = min(dpR[i], val + v[i].cost);
ST.update2(v[i].mid, dpR[i]);
}
ll ans = 1e18;
for(ll i=0;i<m;i++)
ans = min(ans, dpL[i] + dpR[i] - v[i].cost);
if(ans >= 1e18)
ans = -1;
cout << ans << "\n";
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
