#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5, INF = 1e15;
int m, n;
vector<vector<int> > devices;
int seg[2][N * 12];
int lastLeft[N * 3], lastRight[N * 3];
map<int, int> cc;
void Build(int left, int right, int pos, int d2) {
if((left == 1 && d2 == 0) || (right == cc[n] && d2 == 1)) {
//cout << "left = " << left << ", d2 = " << d2 << ", right = " << right << ", cc[n] = " << cc[n] << "\n";
seg[d2][pos] = 0;
}
else {
seg[d2][pos] = INF;
}
//cout << "left = " << left << ", right = " << right << ", d2 = " << d2 << ", val = " << seg[d2][pos] << "\n";
//cout << "cc[n] = " << cc[n] << "\n";
if(left == right)
return;
int mid = (left + right) >> 1;
Build(left, mid, pos * 2, d2);
Build(mid + 1, right, pos * 2 + 1, d2);
}
int Query(int left, int right, int pos, int d2, int qleft, int qright) {
if(qleft <= left && right <= qright)
return seg[d2][pos];
if(qleft > right || left > qright)
return INF;
int mid = (left + right) >> 1;
return min(Query(left, mid, pos * 2, d2, qleft, qright), Query(mid + 1, right, pos * 2 + 1, d2, qleft, qright));
}
void Update(int left, int right, int pos, int d2, int qpos, int qval) {
if(left == right) {
seg[d2][pos] = min(seg[d2][pos], qval);
return;
}
int mid = (left + right) >> 1;
if(mid >= qpos) {
Update(left, mid, pos * 2, d2, qpos, qval);
}
else {
Update(mid + 1, right, pos * 2 + 1, d2, qpos, qval);
}
seg[d2][pos] = min(seg[d2][pos * 2], seg[d2][pos * 2 + 1]);
}
/*void GetMyUpdate(int left, int right, int pos, int d2) {
cout << "left = " << left << ", right = " << right << ", d2 = " << d2 << ", val = " << seg[d2][pos] << "\n";
if(left == right)
return;
int mid = (left + right) >> 1;
GetMyUpdate(left, mid, pos * 2, d2);
GetMyUpdate(mid + 1, right, pos * 2 + 1, d2);
}*/
void Solve() {
cin >> m >> n;
vector<int> inputDevices(4);
bool f1 = false, f2 = false;
devices.push_back({INF, INF, INF, INF});
for(int i = 1; i <= m; i++) {
cin >> inputDevices[0] >> inputDevices[1] >> inputDevices[2] >> inputDevices[3];
//cout << inputDevices[0] << " " << inputDevices[1] << " " << inputDevices[2] << " " << inputDevices[3] << "\n";
cc[inputDevices[0]]++;
cc[inputDevices[1]]++;
cc[inputDevices[2]]++;
if(inputDevices[0] == 1) {
f1 = true;
}
if(inputDevices[1] == n) {
f2 = true;
}
devices.push_back(inputDevices);
}
if(!f1 || !f2) {
cout << "-1\n";
return;
}
int cnt = 1;
for(auto i: cc) {
cc[i.first] = cnt++;
//cout << "i.first = " << i.first << ", cnt = " << cnt - 1 << "\n";
}
/*cout << "Outputting the compressed values of devices[][]\n";
for(int i = 1; i <= m; i++) {
for(int j = 0; j < 3; j++) {
devices[i][j] = cc[devices[i][j]];
cout << devices[i][j] << " ";
}
cout << "\n";
}*/
Build(1, cnt - 1, 1, 0);
Build(1, cnt - 1, 1, 1);
int ans = INF;
for(int i = 1; i <= m; i++) {
int minToGetLeft = Query(1, cnt - 1, 1, 0, devices[i][0], devices[i][1]);
int minToGetRight = Query(1, cnt - 1, 1, 1, devices[i][0], devices[i][1]);
if(minToGetLeft != INF) {
Update(1, cnt - 1, 1, 0, devices[i][2], minToGetLeft + devices[i][3]);
}
if(minToGetRight != INF) {
Update(1, cnt - 1, 1, 1, devices[i][2], minToGetRight + devices[i][3]);
}
ans = min(ans, Query(1, cnt - 1, 1, 0, devices[i][2], devices[i][2]) + Query(1, cnt - 1, 1, 1, devices[i][2], devices[i][2]) - devices[i][3]);
/*cout << "---------------------------------------------------\n";
cout << "Operation i = " << i << "\n";
GetMyUpdate(1, cnt - 1, 1, 0);
GetMyUpdate(1, cnt - 1, 1, 1);
cout << "---------------------------------------------------\n";*/
}
if(ans >= INF - 1e9) {
cout << "-1\n";
}
else {
cout << ans << "\n";
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) {
Solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
