#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define F first
#define S second
const int MN = 1e5+5;
const ll inf = 1e12;
ll N, M, i, j, x, y, c, t, dis[MN], vs[MN], ans=1LL<<60;
struct idk{ll a,b,c,d;}arr[MN],go[MN];
map<ll,ll> mpx, mpy; vector<ll> ed;
struct pq{bool operator()(const pll&i,const pll&j){return i.S>j.S;}};
priority_queue<pll,vector<pll>,pq> q;
struct segtree{
set<pii> st[6*MN]; vector<pii> lz[6*MN]; ll n, c;
void init(ll N){n=N;}
inline void upd_lz(int i,int s,int e){
if(lz[i].size()){
for(auto v : lz[i]){
if(!vs[v.second]){
st[i].insert(v);
if(s^e) lz[2*i].push_back(v), lz[2*i+1].push_back(v);
}
}
lz[i].clear();
}
}
void upd(ll i,ll s,ll e,ll ss,ll se,ll val,ll id){
if(s>=ss&&e<=se) lz[i].push_back({val,id});
else{
if((s+e)/2<ss) upd(2*i+1,(s+e)/2+1,e,ss,se,val,id);
else if((s+e)/2>=se) upd(2*i,s,(s+e)/2,ss,se,val,id);
else upd(2*i,s,(s+e)/2,ss,se,val,id), upd(2*i+1,(s+e)/2+1,e,ss,se,val,id);
st[i].insert({val,id});
}
}
inline void update(ll s,ll e,ll c,ll id){
upd(1,1,n,s,e,c,id);
}
void qu(ll i,ll s,ll e,ll ss,ll se,ll a,ll b){
upd_lz(i,s,e);
if(s>=ss&&e<=se){
auto it=st[i].lower_bound({a,0});
while(it!=st[i].end()&&it->first<=b){
if(!vs[it->second]){
vs[it->second]=1;
q.push({it->second,c+arr[it->second].c});
}
auto it2=it; it++;
st[i].erase(it2);
}
}
else if((s+e)/2<ss) qu(2*i+1,(s+e)/2+1,e,ss,se,a,b);
else if((s+e)/2>=se) qu(2*i,s,(s+e)/2,ss,se,a,b);
else qu(2*i,s,(s+e)/2,ss,se,a,b),qu(2*i+1,(s+e)/2+1,e,ss,se,a,b);
}
inline void query(ll s,ll e,ll x,ll y,ll cur){
c = cur;
qu(1,1,n,s,e,x,y);
}
}stx, sty;
int main(){
scanf("%lld%lld",&N,&M);
for(i=1;i<=M;i++){
scanf("%lld%lld%lld%lld",&t,&x,&y,&c);
arr[i]={x,y,c,t};
if(x==1) q.push({i,c}), x=-inf, vs[i]=1;
if(y==N) ed.push_back(i), y=inf;
y++;
ll sx = t-y, ex = t-x;
ll sy = t+x, ey = t+y;
go[i]={sx,ex,sy,ey};
mpx[sx]=mpx[ex]=mpy[sy]=mpy[ey]=0;
}
i=0; stx.init(mpx.size());
for(auto it=mpx.begin();it!=mpx.end();it++)
it->second = ++i;
i=0; sty.init(mpy.size());
for(auto it=mpy.begin();it!=mpy.end();it++)
it->second = ++i;
for(i=1;i<=M;i++){
go[i].a=mpx[go[i].a]; go[i].b=mpx[go[i].b];
go[i].c=mpy[go[i].c]; go[i].d=mpy[go[i].d];
stx.update(go[i].a,go[i].b,go[i].c,i);
stx.update(go[i].a,go[i].b,go[i].d,i);
sty.update(go[i].c,go[i].d,go[i].a,i);
sty.update(go[i].c,go[i].d,go[i].b,i);
}
memset(dis,-1,sizeof(dis));
while(q.size()){
pll x=q.top(); q.pop();
dis[x.F]=x.S;
int id = x.F;
stx.query(go[id].a,go[id].b,go[id].c,go[id].d,x.S);
sty.query(go[id].c,go[id].d,go[id].a,go[id].b,x.S);
}
for(auto v : ed){
if(dis[v]!=-1) ans=min(ans,dis[v]);
}
printf("%lld\n",ans==1LL<<60?-1:ans);
return 0;
}
Compilation message
treatment.cpp: In function 'int main()':
treatment.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&N,&M);
~~~~~^~~~~~~~~~~~~~~~~~
treatment.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld",&t,&x,&y,&c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3066 ms |
440416 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
85624 KB |
Output is correct |
| 2 |
Correct |
52 ms |
85624 KB |
Output is correct |
| 3 |
Correct |
52 ms |
85624 KB |
Output is correct |
| 4 |
Correct |
63 ms |
85624 KB |
Output is correct |
| 5 |
Correct |
51 ms |
85624 KB |
Output is correct |
| 6 |
Correct |
61 ms |
85624 KB |
Output is correct |
| 7 |
Correct |
68 ms |
85624 KB |
Output is correct |
| 8 |
Correct |
50 ms |
85752 KB |
Output is correct |
| 9 |
Correct |
52 ms |
85752 KB |
Output is correct |
| 10 |
Correct |
52 ms |
85752 KB |
Output is correct |
| 11 |
Correct |
50 ms |
85624 KB |
Output is correct |
| 12 |
Correct |
52 ms |
85704 KB |
Output is correct |
| 13 |
Correct |
55 ms |
85752 KB |
Output is correct |
| 14 |
Correct |
51 ms |
85624 KB |
Output is correct |
| 15 |
Correct |
49 ms |
85624 KB |
Output is correct |
| 16 |
Correct |
49 ms |
85624 KB |
Output is correct |
| 17 |
Correct |
54 ms |
85624 KB |
Output is correct |
| 18 |
Correct |
57 ms |
85624 KB |
Output is correct |
| 19 |
Correct |
51 ms |
85720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
85624 KB |
Output is correct |
| 2 |
Correct |
52 ms |
85624 KB |
Output is correct |
| 3 |
Correct |
52 ms |
85624 KB |
Output is correct |
| 4 |
Correct |
63 ms |
85624 KB |
Output is correct |
| 5 |
Correct |
51 ms |
85624 KB |
Output is correct |
| 6 |
Correct |
61 ms |
85624 KB |
Output is correct |
| 7 |
Correct |
68 ms |
85624 KB |
Output is correct |
| 8 |
Correct |
50 ms |
85752 KB |
Output is correct |
| 9 |
Correct |
52 ms |
85752 KB |
Output is correct |
| 10 |
Correct |
52 ms |
85752 KB |
Output is correct |
| 11 |
Correct |
50 ms |
85624 KB |
Output is correct |
| 12 |
Correct |
52 ms |
85704 KB |
Output is correct |
| 13 |
Correct |
55 ms |
85752 KB |
Output is correct |
| 14 |
Correct |
51 ms |
85624 KB |
Output is correct |
| 15 |
Correct |
49 ms |
85624 KB |
Output is correct |
| 16 |
Correct |
49 ms |
85624 KB |
Output is correct |
| 17 |
Correct |
54 ms |
85624 KB |
Output is correct |
| 18 |
Correct |
57 ms |
85624 KB |
Output is correct |
| 19 |
Correct |
51 ms |
85720 KB |
Output is correct |
| 20 |
Correct |
1500 ms |
356052 KB |
Output is correct |
| 21 |
Correct |
1414 ms |
356120 KB |
Output is correct |
| 22 |
Correct |
255 ms |
118264 KB |
Output is correct |
| 23 |
Correct |
238 ms |
117760 KB |
Output is correct |
| 24 |
Correct |
1018 ms |
275704 KB |
Output is correct |
| 25 |
Incorrect |
821 ms |
260368 KB |
Output isn't correct |
| 26 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3066 ms |
440416 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
