#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
const int N=100050;
const ll inf=9e18;
struct project{
int t,l,r,c;
project(){}
project(int a,int b,int d,int e):t(a),l(b),r(d),c(e){}
bool operator < (project b){return l+r<b.l+b.r||(l+r==b.l+b.r&&t<b.t);}
}pro[N];
ll dist[N];
set<pair<int,int>> bit[N];
vector<pair<int,pii>> save;
vector<int> cor;
void AddPt(int x,int y,int idx){
save.pb({idx,{x,y}});
cor.pb(x);
}
int Find(int x){return lower_bound(cor.begin(),cor.end(),x)-cor.begin()+1;}
void AddBIT(int x,int y,int idx){
//printf("Add %i %i %i\n",x,y,idx);
x=Find(x);
for(int i=x;i>=1;i-=i&-i)bit[i].insert({y,idx});
}
void DelBIT(int x,int y,int idx){
//printf("Del %i %i %i\n",x,y,idx);
x=Find(x);
for(int i=x;i>=1;i-=i&-i)bit[i].erase({y,idx});
}
void Build(){
sort(cor.begin(),cor.end());
cor.erase(unique(cor.begin(),cor.end()),cor.end());
for(auto o:save){
AddBIT(o.second.first,o.second.second,o.first);
}
}
int Get(pair<ll,pii> now){
//printf("%lld %i %i\n",now.first,now.second.first,now.second.second);
int x=Find(now.second.first);
for(int i=x;i<=cor.size();i+=i&-i){
auto it=bit[i].lower_bound({now.second.second,0});
if(it!=bit[i].end())return it->second;
}
return 0;
}
int n,m;
int main(){
scanf("%i %i",&n,&m);
for(int i=1;i<=m;i++)scanf("%i %i %i %i",&pro[i].t,&pro[i].l,&pro[i].r,&pro[i].c);
set<pair<ll,pii>> st;
for(int i=1;i<=m;i++){
if(pro[i].r==n){
st.insert({pro[i].c,{pro[i].l+pro[i].t,pro[i].l-pro[i].t}});
}else{
AddPt(pro[i].r+1+pro[i].t,pro[i].r+1-pro[i].t,i);
}
}
Build();
ll ans=inf;
while(st.size()){
int u=Get(*st.begin());
//printf("%i %lld\n",u,st.begin()->first);
if(u==0){
st.erase(st.begin());
continue;
}
DelBIT(pro[u].r+1+pro[u].t,pro[u].r+1-pro[u].t,u);
dist[u]=st.begin()->first+pro[u].c;
//printf("%i %lld\n",u,dist[u]);
if(pro[u].l==1)ans=min(ans,dist[u]);
st.insert({dist[u],{pro[u].l+pro[u].t,pro[u].l-pro[u].t}});
}
printf("%lld\n",ans==inf?-1:ans);
return 0;
}
Compilation message
treatment.cpp: In function 'int Get(std::pair<long long int, std::pair<int, int> >)':
treatment.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=x;i<=cor.size();i+=i&-i){
| ~^~~~~~~~~~~~
treatment.cpp: In function 'int main()':
treatment.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
51 | scanf("%i %i",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
treatment.cpp:52:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
52 | for(int i=1;i<=m;i++)scanf("%i %i %i %i",&pro[i].t,&pro[i].l,&pro[i].r,&pro[i].c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
500 ms |
47280 KB |
Output is correct |
| 2 |
Correct |
466 ms |
50428 KB |
Output is correct |
| 3 |
Correct |
336 ms |
37432 KB |
Output is correct |
| 4 |
Incorrect |
321 ms |
37292 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
500 ms |
47280 KB |
Output is correct |
| 2 |
Correct |
466 ms |
50428 KB |
Output is correct |
| 3 |
Correct |
336 ms |
37432 KB |
Output is correct |
| 4 |
Incorrect |
321 ms |
37292 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
