제출 #1079441

#제출 시각아이디문제언어결과실행 시간메모리
1079441isaachew치료 계획 (JOI20_treatment)C++17
0 / 100
31 ms7760 KiB
#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; int 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;}); return 0; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...