#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 5e6 + 5;
ll seg1[mxn];
ll seg2[mxn];
void update(int k, int l, int r, int pos, ll val){
if(r < pos || pos < l) return;
if(l == r){
seg1[k] = val;
return;
}
int mid = (l + r) / 2;
update(k * 2, l, mid, pos, val);
update(k * 2 + 1, mid + 1, r, pos, val);
seg1[k] = min(seg1[k * 2], seg1[k * 2 + 1]);
}
ll query(int k, int l, int r, int x, int y){
if(r < x || y < l) return inf;
if(x <= l && r <= y){
return seg1[k];
}
int mid = (l + r) / 2;
return min(query(k * 2, l, mid, x, y), query(k * 2 + 1, mid + 1, r, x, y));
}
void update2(int k, int l, int r, int pos, ll val){
if(r < pos || pos < l) return;
if(l == r){
seg2[k] = val;
return;
}
int mid = (l + r) / 2;
update2(k * 2, l, mid, pos, val);
update2(k * 2 + 1, mid + 1, r, pos, val);
seg2[k] = min(seg2[k * 2], seg2[k * 2 + 1]);
}
ll query2(int k, int l, int r, int x, int y){
if(r < x || y < l) return inf;
if(x <= l && r <= y){
return seg2[k];
}
int mid = (l + r) /2 ;
return min(query2(k * 2, l, mid, x, y), query2(k * 2 + 1, mid + 1, r, x, y));
}
int maxbound = 1e5;
void solve(){
fr(i,0 , mxn){
seg1[i] = seg2[i] = inf;
}
int M, N;
cin >> M >> N;
int a[M], b[M], c[M], d[M];
vector<pair<int, pii> > v;
fr(i, 0, M){
cin >> a[i] >> b[i] >> c[i] >> d[i];
v.pb({a[i], {-1, i}});
v.pb({b[i], {1, i}});
v.pb({c[i], {0, i}});
}
sort(all(v));
int val = 0;
if(v[0].st != 1 || v.back().st != N){
cout << -1<<endl;
return;
}
if(v[0].nd.st == -1) a[v[0].nd.nd] = val;
else if(v[0].nd.st == 1) b[v[0].nd.nd] = val;
else c[v[0].nd.nd] = val;
fr(i, 1, (int)(v.size())){
if(v[i].st != v[i - 1].st) val ++;
if(v[i].nd.st == -1) a[v[i].nd.nd] = val;
else if(v[i].nd.st == 1) b[v[i].nd.nd] = val;
else c[v[i].nd.nd] = val;
}
maxbound = val;
ll ans = inf;
fr(i, 0, M){
int l = a[i], r = b[i], mid = c[i];
ll costleft = d[i];
if(l != 0){
costleft = min(inf, query(1, 0, maxbound, l, r) + d[i]);
}
update(1, 0, maxbound, mid, costleft);
ll costright = d[i];
if(r != maxbound){
costright = min(inf, query2(1, 0, maxbound, l, r) + d[i]);
}
update2(1, 0, maxbound, mid, costright);
ans = min(ans, costleft + costright - d[i]);
}
if(ans == inf) cout << -1 << endl;
else cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
78584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
78584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
78584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
78584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
