#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Plan{
ll t, l, r, cost;
Plan(){}
Plan(ll t, ll l, ll r, ll cost): t(t), l(l), r(r), cost(cost){}
};
struct Point{
ll x, y; int idx;
Point(){}
Point(ll x, ll y, int idx): x(x), y(y), idx(idx){}
bool operator<(const Point &r)const{
return y>r.y;
}
};
struct dat{
int x; ll y;
dat(){}
dat(int x, ll y): x(x), y(y){}
bool operator<(const dat &r)const{
return y>r.y;
}
};
vector<int> retVal;
struct segTree{
vector<Point> tree[400002];
void initialize(int i, int l, int r){
sort(tree[i].begin(), tree[i].end());
if(l==r) return;
int m = (l+r)>>1;
initialize(i*2, l, m), initialize(i*2+1, m+1, r);
}
void pushPoint(int i, int l, int r, Point p){
tree[i].push_back(p);
if(l==r) return;
int m = (l+r)>>1;
if(p.x <= m) pushPoint(i*2, l, m, p);
else pushPoint(i*2+1, m+1, r, p);
}
void rectQuery(int i, int l, int r, int xLim, ll yLim){
if(xLim < l) return;
if(r<=xLim){
while(!tree[i].empty() && tree[i].back().y <= yLim){
retVal.push_back(tree[i].back().idx);
tree[i].pop_back();
}
return;
}
int m = (l+r)>>1;
rectQuery(i*2, l, m, xLim, yLim), rectQuery(i*2+1, m+1, r, xLim, yLim);
}
} tree;
int n, m;
Plan arr[100002];
bool chk[100002];
ll ans = LLONG_MAX;
priority_queue<dat> pq;
vector<Point> pointVec;
vector<ll> renVec;
void makeSegTree(){
for(auto &x: pointVec) renVec.push_back(x.x);
sort(renVec.begin(), renVec.end());
renVec.erase(unique(renVec.begin(), renVec.end()), renVec.end());
for(auto &x: pointVec) x.x = lower_bound(renVec.begin(), renVec.end(), x.x) - renVec.begin() + 1;
for(auto &x: pointVec) tree.pushPoint(1, 1, n, x);
tree.initialize(1, 1, n);
}
int main(){
scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++){
scanf("%lld %lld %lld %lld", &arr[i].t, &arr[i].l, &arr[i].r, &arr[i].cost);
arr[i].r++;
if(arr[i].l == 1) pq.push(dat(i, arr[i].cost));
else pointVec.push_back(Point(arr[i].l + arr[i].t, arr[i].l - arr[i].t, i));
}
makeSegTree();
while(!pq.empty()){
auto tmp = pq.top(); pq.pop();
if(chk[tmp.x]) continue;
int tx = tmp.x; ll ty = tmp.y;
chk[tx] = 1;
if(arr[tx].r == n+1) ans = min(ans, ty);
int xLim = arr[tx].r + arr[tx].t; ll yLim = arr[tx].r - arr[tx].t;
xLim = upper_bound(renVec.begin(), renVec.end(), xLim) - renVec.begin();
retVal.clear(); retVal.shrink_to_fit();
tree.rectQuery(1, 1, n, xLim, yLim);
for(auto nxt: retVal){
if(chk[nxt]) continue;
pq.push(dat(nxt, ty+arr[nxt].cost));
}
}
printf("%lld", ans == LLONG_MAX ? -1 : ans);
}
Compilation message
treatment.cpp: In function 'int main()':
treatment.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
treatment.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
85 | scanf("%lld %lld %lld %lld", &arr[i].t, &arr[i].l, &arr[i].r, &arr[i].cost);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
111 ms |
36064 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 2 |
Runtime error |
19 ms |
19456 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 2 |
Runtime error |
19 ms |
19456 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
111 ms |
36064 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
