#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
const ll INF = 1LL * 1e18;
inline int getc(vector<int> &V, int x) { return lower_bound(V.begin(), V.end(), x) - V.begin() + 1; }
ll D[100009];
deque<pii> PT[400009], QT[400009];
int T[100009], L[100009], R[100009], C[100009];
bool chk[100009];
void updP(int idx, int s, int e, int l, int r, int id) {
if(r < s || e < l) return;
if(l <= s && e <= r) {
PT[idx].push_back({T[id], id});
return;
}
int m = s+e >> 1;
updP(idx*2, s, m, l, r, id);
updP(idx*2+1, m+1, e, l, r, id);
}
void updQ(int idx, int s, int e, int l, int r, int id) {
if(r < s || e < l) return;
if(l <= s && e <= r) {
QT[idx].push_back({T[id], id});
return;
}
int m = s+e >> 1;
updQ(idx*2, s, m, l, r, id);
updQ(idx*2+1, m+1, e, l, r, id);
}
void getP(ll pc, priority_queue<pli> &pq, int idx, int s, int e, int p, int t) {
if(p < s || e < p) return;
while(PT[idx].size()) {
int ti, id; tie(ti, id) = PT[idx].back();
if(ti < t) break;
PT[idx].pop_back();
if(chk[id]) continue;
chk[id] = 1;
pq.push({-(pc + C[id]), id});
}
if(s == e) return;
int m = s+e >> 1;
getP(pc, pq, idx*2, s, m, p, t);
getP(pc, pq, idx*2+1, m+1, e, p, t);
}
void getQ(ll pc, priority_queue<pli> &pq, int idx, int s, int e, int p, int t) {
if(p < s || e < p) return;
while(QT[idx].size()) {
int ti, id; tie(ti, id) = QT[idx].front();
if(ti > t) break;
QT[idx].pop_front();
if(chk[id]) continue;
chk[id] = 1;
pq.push({-(pc + C[id]), id});
}
if(s == e) return;
int m = s+e >> 1;
getQ(pc, pq, idx*2, s, m, p, t);
getQ(pc, pq, idx*2+1, m+1, e, p, t);
}
int main() {
vector<int> PV, QV;
priority_queue<pli> pq;
int N, M; scanf("%d%d",&N,&M);
for(int i=1; i<=M; i++) {
scanf("%d%d%d%d", &T[i], &L[i], &R[i], &C[i]); --L[i];
if(L[i] == 0) {
pq.push({-C[i], i});
chk[i] = 1;
}
PV.push_back(L[i] + T[i]);
PV.push_back(R[i] + T[i]);
QV.push_back(L[i] - T[i]);
QV.push_back(R[i] - T[i]);
}
sort(PV.begin(), PV.end()); PV.resize(unique(PV.begin(), PV.end()) - PV.begin());
sort(QV.begin(), QV.end()); QV.resize(unique(QV.begin(), QV.end()) - QV.begin());
int PM = PV.size(), QM = QV.size();
for(int i=1; i<=M; i++) {
int pl = getc(PV, L[i] + T[i]), pr = getc(PV, R[i] + T[i]);
updP(1, 1, PM, pl, pr, i);
int ql = getc(QV, L[i] - T[i]), qr = getc(QV, R[i] - T[i]);
updQ(1, 1, QM, ql, qr, i);
}
for(int i=1; i<=4*PM; i++) sort(PT[i].begin(), PT[i].end());
for(int i=1; i<=4*QM; i++) sort(QT[i].begin(), QT[i].end());
memset(D, -1, sizeof(D));
while(pq.size()) {
ll c; int x; tie(c, x) = pq.top(); pq.pop(); c = -c;
D[x] = c;
getP(c, pq, 1, 1, PM, getc(PV, R[x] + T[x]), T[x]);
getQ(c, pq, 1, 1, QM, getc(QV, R[x] - T[x]), T[x]);
}
ll ans = INF;
for(int i=1; i<=M; i++) if(R[i] == N && D[i] != -1) ans = min(ans, D[i]);
if(ans != INF) printf("%lld", ans);
else puts("-1");
return 0;
}
Compilation message
treatment.cpp: In function 'void updP(int, int, int, int, int, int)':
treatment.cpp:21:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
treatment.cpp: In function 'void updQ(int, int, int, int, int, int)':
treatment.cpp:32:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
treatment.cpp: In function 'void getP(ll, std::priority_queue<std::pair<long long int, int> >&, int, int, int, int, int)':
treatment.cpp:48:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
treatment.cpp: In function 'void getQ(ll, std::priority_queue<std::pair<long long int, int> >&, int, int, int, int, int)':
treatment.cpp:64:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
treatment.cpp: In function 'int main()':
treatment.cpp:72:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N, M; scanf("%d%d",&N,&M);
~~~~~^~~~~~~~~~~~~~
treatment.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &T[i], &L[i], &R[i], &C[i]); --L[i];
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
272 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
269 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
269 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
272 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
