#include <bits/stdc++.h>
/*
A project at L and R are necessary
Projects "chain"
Turn the projects into a graph?
35 points - Dijkstra from left project to right project
*/
struct project{
long long l,r,t,c;
};
struct segtree{
long long nl,nr;
segtree* left,*right;
std::vector<int> value;
bool isleaf;
segtree(long long l,long long r,int v=-2){
nl=l,nr=r;
isleaf=1;
left=right=NULL;
if(v!=-2)value.push_back(v);
}
~segtree(){
if(!isleaf){
delete left;
delete right;
}
}
void update(long long l,long long r,int v){
//std::cout<<"update "<<nl<<' '<<nr<<'\n';
if(l<=nl&&r>=nr){
value.push_back(v);
return;
}
if(r<=nl||l>=nr)return;
long long nm=(nl+nr)/2;
if(isleaf){
left=new segtree(nl,nm,-2);
right=new segtree(nm,nr,-2);
isleaf=0;
}
left->update(l,r,v);
right->update(l,r,v);
}
std::vector<int> query(long long pos,int from,bool neg){
std::vector<int> cur;
while(!value.empty()&&(neg?value.back()>from:value.back()<from)){
cur.push_back(value.back());
value.pop_back();
}
if(!isleaf){
long long nm=(nl+nr)/2;
if(pos<nm){
for(int i:left->query(pos,from,neg)){
cur.push_back(i);
}
}else{
for(int i:right->query(pos,from,neg)){
cur.push_back(i);
}
}
}
return cur;
}
};
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n,m;
std::cin>>n>>m;
std::vector<project> projs;
segtree pasts(-2e9,2e9);//stores left - time
segtree futures(-2e9,2e9);//stores left - time
for(int i=0;i<m;i++){
int a,b,c,d;
project pr;
std::cin>>a>>b>>c>>d;
pr.t=a;pr.l=b;pr.r=c;pr.c=d;
projs.push_back(pr);
}
std::sort(projs.begin(),projs.end(),[&](project a,project b){return a.t<b.t;});
for(int i=m;i--;){
pasts.update(projs[i].l-projs[i].t-1,projs[i].r-projs[i].t+1,i);
}
for(int i=0;i<m;i++){
futures.update(projs[i].l+projs[i].t-1,projs[i].r+projs[i].t+1,i);
}
std::vector<long long> dists(n,1e18);
std::priority_queue<std::pair<long long,int>> dijkstra;
for(int i=0;i<m;i++){
if(projs[i].l==1){
dijkstra.push({-projs[i].c,i});
}
}
while(!dijkstra.empty()){
std::pair<long long,int> cur=dijkstra.top();
dijkstra.pop();
if(dists[cur.second]<=-cur.first)continue;
dists[cur.second]=-cur.first;
int i=cur.second;
std::vector<int> eds=pasts.query(projs[i].r-projs[i].t,i,0);
std::vector<int> eds2=futures.query(projs[i].r+projs[i].t,i,1);
//std::cout<<"pasts\n";
for(int i:eds){
//std::cout<<i<<" from "<<cur.second<<'\n';
dijkstra.push({cur.first-projs[i].c,i});
}
//std::cout<<"futures\n";
for(int i:eds2){
//std::cout<<i<<" from "<<cur.second<<'\n';
dijkstra.push({cur.first-projs[i].c,i});
}
}
long long result=1e18;
for(int i=0;i<m;i++){
if(projs[i].r==n){
//std::cout<<i<<'\n';
result=std::min(result,dists[i]);
}
}
std::cout<<(result==1e18?-1:result)<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
614 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
203 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
203 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
614 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
