#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{
std::vector<std::vector<int>> value;
std::vector<int> left,right;
std::vector<int> isleaf;
segtree(){
value.push_back(std::vector<int>());
isleaf.push_back(1);
left.push_back(0);right.push_back(0);
}
void update(long long l,long long r,int v,long long nl=-2e9,long long nr=2e9,int ni=0){
//std::cout<<"update "<<nl<<' '<<nr<<' '<<ni<<' '<<left[ni]<<' '<<right[ni]<<'\n';
if(r<l)return;//??
if(r<=nl||l>=nr)return;
if(l<=nl&&r>=nr){
value[ni].push_back(v);
return;
}
long long nm=(nl+nr)/2;
if(isleaf[ni]){
left[ni]=value.size();
value.push_back(std::vector<int>());
isleaf.push_back(1);left.push_back(0);right.push_back(0);
right[ni]=value.size();
value.push_back(std::vector<int>());
isleaf.push_back(1);left.push_back(0);right.push_back(0);
isleaf[ni]=0;
}
update(l,r,v,nl,nm,left[ni]);
update(l,r,v,nm,nr,right[ni]);
}
void query(long long pos,int from,bool neg,std::vector<int>& vec,long long nl=-2e9,long long nr=2e9,int ni=0){
while(!value[ni].empty()&&(neg?value[ni].back()>from:value[ni].back()<from)){
vec.push_back(value[ni].back());
value[ni].pop_back();
}
if(!isleaf[ni]){
long long nm=(nl+nr)/2;
if(pos<nm){
query(pos,from,neg,vec,nl,nm,left[ni]);
}else{
query(pos,from,neg,vec,nm,nr,right[ni]);
}
}
}
};
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;//stores left - time
segtree futures;//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,eds);
futures.query(projs[i].r+projs[i].t,i,1,eds);
//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";
}
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 |
654 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
185 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
185 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
654 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
