#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define MOD 1000000007
typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ll,int>pli;
const ll INF=1e18;
const int mxn=1e5+5;
/* T_i<=T_j, L_j+T_j<=R_i+T_i
* T_i>=T_j, L_j-T_j<=R_i-T_i
* connect them with edge then perform Dij
* start from 1 -> n, note that the citizen 1 and n only affected by citizen 2 and n-1 respectively
*/
struct st{
int t,le,ri,cost;
st(int t,int le, int ri, int cost):t(t),le(le),ri(ri),cost(cost){};
};
struct point{
int m, p, ind;
point(int m, int p, int ind):m(m),p(p),ind(ind){};
bool operator < (const point &r)const {
return m<r.m;
}
};
struct node{
int ind; ll d;
bool operator < (const node &r) const {
return d>r.d;
}
};
vector<st>str;
vector<point>pt;
vector<pli>tree[mxn*4];
bool vis[mxn];
void build(int id, int le, int ri){
if(le==ri){
tree[id].eb(pt[le].p,pt[le].ind);
}else{
int mid=(le+ri)/2;
build(id*2,le,mid);
build(id*2+1,mid+1,ri);
tree[id].resize(tree[id*2].size()+tree[id*2+1].size());
merge(all(tree[id*2]),all(tree[id*2+1]),tree[id].begin());
sort(all(tree[id]));
tree[id].erase(unique(all(tree[id])),tree[id].end());
}
return;
}
void getnodes(int pos, int val, int id, int le, int ri, vi &v){
if(le>=pos)return;
if(ri<pos){
while(!tree[id].empty()){
//fi = point.p = le+t, val = ri+t, le+t<=ri+t for t_i<=t_j
if(tree[id][0].fi<=val){
int ind = tree[id][0].se;
if(!vis[ind])v.eb(ind);
tree[id].erase(tree[id].begin());
}else break;
}
return;
}
int mid=(le+ri)/2;
getnodes(pos,val,id*2,le,mid,v);
getnodes(pos,val,id*2+1,mid+1,ri,v);
return;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
//freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
int n,m; cin >> n >> m;
int t,le,ri,cost;
for(int i=0; i<m; i++){
cin >> t >> le >> ri >> cost;
str.eb(t,le,ri,cost);
pt.eb(le-t,le+t,i);
}
sort(all(pt));
build(1,0,m-1);
/*
for(int i=0; i<m; i++){
cout << i << ' ' << pt[i].m << ' ' << pt[i].p << ' ' << pt[i].ind << '\n';
}
*/
ll dist[m];
for(int i=0; i<m; i++)dist[i]=INF,vis[i]=0;
priority_queue<node>pq;
for(int i=0; i<m; i++){
if(str[i].le==1){
vis[i]=1;
dist[i]=str[i].cost;
pq.push({i,dist[i]});
}
}
while(!pq.empty()){
int u = pq.top().ind;
pq.pop();
vi vt;
int pos = upper_bound(all(pt),point(str[u].ri-str[u].t+2,-1,-1))-pt.begin();
int val = str[u].ri+str[u].t+1;
getnodes(pos,val,1,0,m-1,vt);
for(int v:vt){
if(vis[v])continue;
vis[v]=1;
dist[v] = dist[u]+str[v].cost;
pq.push({v,dist[v]});
}
}
ll ans = INF;
for(int i=0; i<m; i++){
if(str[i].ri==n){
ans = min(ans,dist[i]);
}
}
if(ans==INF)ans=-1;
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3088 ms |
47364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9728 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
9728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9728 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
9728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3088 ms |
47364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
