#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
typedef pair<int,int> pii;
#define mp make_pair
#define eb emplace_back
const int mxm=100005,inf=1e17;
pair<pii,pii> pts[mxm];int nex=0;
vector<pair<int,pii> >endds;
struct inn{
int s,e,v=inf;
inn *l,*r;
inn(int ss,int ee){
s=ss;e=ee;
l=r=NULL;
}
int query(int p){
if(p<=s)return v;
int ans=inf;
if(p<=(s+e)/2){
if(l)ans=l->query(p);
}
if(r)ans=min(ans,r->query(p));
return ans;
}
void update(int p,int nv){
//cout<<"inn update "<<s<<' '<<e<<' '<<p<<'\n';
v=min(v,nv);
if(s==e){
return;
}
if(p<=(s+e)/2){
if(!l)l=new inn(s,(s+e)/2);
l->update(p,nv);
}else{
if(!r)r=new inn((s+e)/2+1,e);
r->update(p,nv);
}
}
};
struct node{
int s,e;
node *l,*r;
inn *inne;
node(int ss,int ee,int s2,int e2){//min queries...
s=ss;e=ee;
l=r=NULL;
inne=new inn(s2,e2);
}
void update(int a,int b,int c){
if(s==1 && e==2e9+2)b+=1e9+3;
inne->update(b,c);
if(s==e)return;
if(a<=(s+e)/2){
if(!l)l=new node(s,(s+e)/2,inne->s,inne->e);
l->update(a,b,c);
}else{
if(!r)r=new node((s+e)/2+1,e,inne->s,inne->e);
r->update(a,b,c);
}
}
int query(int a,int b){
if(s==1 && e==2e9+2)b+=1e9+3;
if(a<=s){
return inne->query(b);
}
int ans=inf;
if(a<=(s+e)/2){if(l)ans=l->query(a,b);}
if(r)ans=min(ans,r->query(a,b));
return ans;
}
} *root;
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int n,m,ans=inf;
cin>>n>>m;
root=new node(0,2e9+2,1,2e9+3);
for(int i=0;i<m;i++){
int t,l,r,c;
cin>>t>>l>>r>>c;r++;
if(l==1){
root->update(t+r,-t+r,c);//1 to 2e9, and -1e9 to 1e9
}else if(r==n+1){
endds.eb(c,mp(t+l,-t+l));
}
if(l==1 && r==n)ans=min(ans,c);
if(l>1 && r<n)pts[nex++]=mp(mp(r,l),mp(t,c));
}
sort(pts,pts+nex);//increasing r...
for(int i=0;i<nex;i++){
//query upper-right corner:(t+l,-t+l)
auto x=pts[i];
int dist=root->query(x.s.f+x.f.s,-x.s.f+x.f.s);//query from bottom left
root->update(x.s.f+x.f.f,-x.s.f+x.f.f,dist+x.s.s);//update on square top right corner...
}
for(auto x:endds){
ans=min(ans,x.f+root->query(x.s.f,x.s.s) );
}
if(ans==inf)cout<<"-1\n";
else cout<<ans<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
629 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
629 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
