// #include <bits/stdc++.h>
// #define int long long
// using namespace std;
// const int Nmax=100010, INF=1e18, S=(1<<18);
// int N, M, ans=INF, D[Nmax];
// struct Data {
// int t, l, r, c;
// }A[Nmax];
// vector<int> T, X;
// struct Seg2D {
// struct Seg1D {
// struct Node {
// int v; Node *l, *r;
// Node() {v=INF, l=r=NULL;}
// };
// Node *root;
// Seg1D() {root=new Node();}
// void Update(int k, int v) {Update(root, 1, S, k, v);}
// int Query(int l, int r) {return Query(root, 1, S, l, r);}
// void Update(Node *curr, int s, int e, int k, int v) {
// curr->v=min(curr->v, v);
// if(s==e) return;
// int m=(s+e)/2;
// if(k<=m) {
// if(!(curr->l)) curr->l=new Node();
// Update(curr->l, s, m, k, v);
// }
// else {
// if(!(curr->r)) curr->r=new Node();
// Update(curr->r, m+1, e, k, v);
// }
// }
// int Query(Node *curr, int s, int e, int l, int r) {
// if(!curr || s>r || l>e) return INF;
// if(l<=s && e<=r) return curr->v;
// int m=(s+e)/2;
// return min(Query(curr->l, s, m, l, r), Query(curr->r, m+1, e, l, r));
// }
// }Tree[2*S];
// void Update(int k, int x, int v) {Update(1, 1, S, k, x, v);}
// void Update(int node, int s, int e, int k, int x, int v) {
// Tree[node].Update(x, v);
// if(s==e) return;
// int lch=2*node, rch=lch+1, m=(s+e)/2;
// if(k<=m) Update(lch, s, m, k, x, v);
// else Update(rch, m+1, e, k, x, v);
// }
// int Query(int l, int r, int lo, int hi) {return Query(1, 1, S, l, r, lo, hi);}
// int Query(int node, int s, int e, int l, int r, int lo, int hi) {
// if(s>r || l>e) return INF;
// if(l<=s && e<=r) return Tree[node].Query(lo, hi);
// int lch=2*node, rch=lch+1, m=(s+e)/2;
// return min(Query(lch, s, m, l, r, lo, hi), Query(rch, m+1, e, l, r, lo, hi));
// }
// }P, P2;
// signed main() {
// ios_base::sync_with_stdio(0); cin.tie(0);
// cin>>N>>M;
// for(int i=1; i<=M; i++) {
// cin>>A[i].t>>A[i].l>>A[i].r>>A[i].c;
// A[i].r++;
// T.push_back(A[i].t);
// X.push_back(A[i].r-A[i].t), X.push_back(A[i].r+A[i].t);
// }
// sort(A+1, A+M+1, [](Data a, Data b) {return a.r<b.r;});
// sort(T.begin(), T.end()), T.erase(unique(T.begin(), T.end()), T.end());
// sort(X.begin(), X.end()), X.erase(unique(X.begin(), X.end()), X.end());
// fill(D+1, D+M+1, INF);
// for(int i=1; i<=M; i++) {
// //cout<<i<<": "<<A[i].l<<"~"<<A[i].r<<": "<<A[i].t<<", "<<A[i].c<<"\n";
// if(A[i].l==1) D[i]=A[i].c;
// else {
// //cout<<"aa"<<1<<"~"<<lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1<<", "<<lower_bound(X.begin(), X.end(), A[i].l+A[i].t)-X.begin()+1<<"~"<<X.size()<<"\n";
// int a=P.Query(1, lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, lower_bound(X.begin(), X.end(), A[i].l+A[i].t)-X.begin()+1, X.size());
// int b=P2.Query(lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, T.size(), lower_bound(X.begin(), X.end(), A[i].l-A[i].t)-X.begin()+1, X.size());
// D[i]=min(a, b)+A[i].c;
// }
// if(A[i].r==N+1) ans=min(ans, D[i]);
// //cout<<i<<": "<<D[i]<<"\n";
// //cout<<"aa"<<lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1<<", "<<lower_bound(X.begin(), X.end(), A[i].r+A[i].t)-X.begin()+1<<": "<<D[i]<<"\n";
// //cout<<"bb"<<lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1<<", "<<lower_bound(X.begin(), X.end(), A[i].r-A[i].t)-X.begin()+1<<": "<<D[i]<<"\n";
// P.Update(lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, lower_bound(X.begin(), X.end(), A[i].r+A[i].t)-X.begin()+1, D[i]);
// P2.Update(lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, lower_bound(X.begin(), X.end(), A[i].r-A[i].t)-X.begin()+1, D[i]);
// }
// if(ans==INF) cout<<-1;
// else cout<<ans;
// return 0;
// }
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Nmax=100010, INF=1e18;
int N, M, ans=INF, D[Nmax];
struct Data {
int t, l, r, c;
}A[Nmax];
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N>>M;
for(int i=1; i<=M; i++) {
cin>>A[i].t>>A[i].l>>A[i].r>>A[i].c;
A[i].r++;
}
sort(A+1, A+M+1, [](Data a, Data b) {return a.r<b.r;});
fill(D+1, D+M+1, INF);
for(int i=1; i<=M; i++) {
if(A[i].l==1) D[i]=A[i].c;
else {
for(int j=1; j<i; j++) {
if(A[j].t<=A[i].t && A[j].r+A[j].t>=A[i].l+A[i].t) D[i]=min(D[i], D[j]+A[i].c);
if(A[j].t>=A[i].t && A[j].r-A[j].t>=A[i].l-A[i].t) D[i]=min(D[i], D[j]+A[i].c);
}
}
if(A[i].r==N+1) ans=min(ans, D[i]);
}
if(ans==INF) cout<<-1;
else cout<<ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3096 ms |
4176 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3096 ms |
4176 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
