#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
constexpr ll INF = 1e18;
constexpr int INF2 = 2e9;
ll dist[100100];
struct Fenwick{
vector<pair<int, int>> tree[100100];
int sz;
void init(int n){sz = n;}
void init2(){for (int i=0;i<=sz;i++) sort(tree[i].begin(), tree[i].end(), greater<pair<int, int>>());}
void update(int x, int y, int i){
while(x<=sz){
tree[x].emplace_back(y, i);
x += x&-x;
}
}
pair<int, int> query(int x){
pair<int, int> ret = {INF2, 0};
while(x){
while(!tree[x].empty() && dist[tree[x].back().second]!=INF) tree[x].pop_back();
if (!tree[x].empty()) ret = min(ret, tree[x].back());
x -= x&-x;
}
return ret;
}
int pop(int x, int y){
auto [val, idx] = query(x);
if (val>y) return 0;
return idx;
}
}tree;
int T[100100], L[100100], R[100100], C[100100];
void compress(vector<int> &v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
inline int getidx(const vector<int> &v, int x) {return lower_bound(v.begin(), v.end(), x) - v.begin();}
inline int getidx2(const vector<int> &v, int x) {return upper_bound(v.begin(), v.end(), x) - v.begin() - 1;}
int main(){
int X, n;
scanf("%d %d", &X, &n);
vector<int> x;
x.push_back(-INF2);
for (int i=1;i<=n;i++){
scanf("%d %d %d %d", T+i, L+i, R+i, C+i);
x.push_back(L[i] + T[i]);
}
compress(x);
tree.init(n+2);
fill(dist+1, dist+n+1, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i=1;i<=n;i++){
tree.update(getidx(x, L[i]+T[i]), L[i]-T[i], i);
if (L[i]==1){
dist[i] = C[i];
pq.emplace(C[i], i);
}
}
tree.init2();
while(!pq.empty()){
auto [c, s] = pq.top(); pq.pop();
int xc = getidx2(x, R[s]+1+T[s]), yc = R[s]+1-T[s], v;
while(true){
v = tree.pop(xc, yc);
if (!v) break;
dist[v] = c + C[v];
pq.emplace(dist[v], v);
}
}
ll ans = INF;
for (int i=1;i<=n;i++) if (R[i]==X) ans = min(ans, dist[i]);
printf("%lld\n", ans==INF?-1:ans);
return 0;
}
Compilation message
treatment.cpp: In member function 'int Fenwick::pop(int, int)':
treatment.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
29 | auto [val, idx] = query(x);
| ^
treatment.cpp: In function 'int main()':
treatment.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | auto [c, s] = pq.top(); pq.pop();
| ^
treatment.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%d %d", &X, &n);
| ~~~~~^~~~~~~~~~~~~~~~~
treatment.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d %d %d %d", T+i, L+i, R+i, C+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
169 ms |
17340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
169 ms |
17340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
