#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
struct Seg
{
int l, r;
long long v;
Seg() : l(0), r(0), v(0x3f3f3f3f3f3f3f3fLL) {}
} tree[22222222];
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int SZ=1<<18;
vector<int> P;
vector<pair<int,int>> x, y;
vector<tuple<int,int,int,int,int>> A;
long long dist[100000];
int node_cnt=2*SZ, chk[100000], lx[200000], rx[200000], ly[200000], ry[200000];
void set_tree2(int n, long long v, int p, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
if(s==e) {
tree[p].v=v;
return;
}
if(n<=m) {
if(tree[p].l==0) tree[p].l=node_cnt++;
set_tree2(n,v,tree[p].l,s,m);
}
else {
if(tree[p].r==0) tree[p].r=node_cnt++;
set_tree2(n,v,tree[p].r,m+1,e);
}
tree[p].v=min(tree[tree[p].l].v,tree[tree[p].r].v);
}
void set_tree(int x, int y, long long v)
{
for(set_tree2(y,v,x+=SZ);x>>=1;) set_tree2(y,v,x);
}
long long get_min2(int n1, int n2, int p, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
if(n2<n1 || n2<s || e<n1 || p==0) return INF;
if(n1<=s && e<=n2) return tree[p].v;
return min(get_min2(n1,n2,tree[p].l,s,m),get_min2(n1,n2,tree[p].r,m+1,e));
}
long long get_min(int x1, int y1, int x2, int y2)
{
long long ret=INF;
for(x1+=SZ,x2+=SZ;x1<=x2;x1>>=1,x2>>=1) {
if(x1&1) ret=min(ret,get_min2(y1,y2,x1++));
if(~x2&1) ret=min(ret,get_min2(y1,y2,x2--));
}
return ret;
}
void get_pos2(int n1, int n2, long long v, int p, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
if(n2<n1 || n2<s || e<n1 || tree[p].v!=v) return;
if(s==e) {
P.push_back(y[m].second);
return;
}
get_pos2(n1,n2,v,tree[p].l,s,m);
get_pos2(n1,n2,v,tree[p].r,m+1,e);
}
void get_pos(int x1, int y1, int x2, int y2, long long v)
{
P.clear();
for(x1+=SZ,x2+=SZ;x1<=x2;x1>>=1,x2>>=1) {
if(x1&1) get_pos2(y1,y2,v,x1++);
if(~x2&1) get_pos2(y1,y2,v,x2--);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, M;
priority_queue<pair<long long,int>> Q;
long long ans;
cin>>N>>M; A.resize(M);
memset(dist,0x3f,sizeof(dist));
for(int i=0;i<M;i++) {
auto &[t,l,r,aa,c]=A[i];
cin>>t>>l>>r>>c;
if(l--==1) chk[i]=1;
else if(r==N) chk[i]=2;
x.emplace_back(l+t,i);
x.emplace_back(r+t,i);
y.emplace_back(l-t,i);
y.emplace_back(r-t,i);
t=l=r=aa=-1;
}
sort(x.begin(),x.end()); sort(y.begin(),y.end());
for(int i=0;i<2*M;i++) {
if(get<0>(A[x[i].second])==-1) get<0>(A[x[i].second])=i;
else get<2>(A[x[i].second])=i;
if(get<1>(A[y[i].second])==-1) get<1>(A[y[i].second])=i;
else get<3>(A[y[i].second])=i;
lx[i]=i && x[i-1].first==x[i].first ? lx[i-1]:i;
ly[i]=i && y[i-1].first==y[i].first ? ly[i-1]:i;
}
rx[2*M-1]=ry[2*M-1]=2*M-1;
for(int i=2*M-1;--i>=0;) {
rx[i]=x[i].first==x[i+1].first ? rx[i+1]:i;
ry[i]=y[i].first==y[i+1].first ? ry[i+1]:i;
}
for(int i=0;i<M;i++) if(chk[i]!=1) {
auto[x1,y1,x2,y2,c]=A[i];
set_tree(x1,y1,c);
set_tree(x2,y1,c);
set_tree(x1,y2,c);
set_tree(x2,y2,c);
}
for(int i=0;i<M;i++) if(chk[i]==1) {
auto[x1,y1,x2,y2,c]=A[i];
dist[i]=c; ans=get_min(lx[x1],ly[y1],rx[x2],ry[y2]);
if(ans<INF) Q.emplace(-dist[i]-ans,i);
}
while(!Q.empty()) {
auto[t,c]=Q.top();
Q.pop();
auto[x1,y1,x2,y2,d]=A[c];
ans=get_min(lx[x1],ly[y1],rx[x2],ry[y2]);
if(-t!=dist[c]+ans) {
if(ans<INF) Q.emplace(-dist[c]-ans,c);
continue;
}
get_pos(lx[x1],ly[y1],rx[x2],ry[y2],ans);
for(auto n: P) {
auto[x1,y1,x2,y2,nc]=A[n];
dist[n]=dist[c]+nc;
assert(nc==ans);
set_tree(x1,y1,INF);
set_tree(x2,y1,INF);
set_tree(x1,y2,INF);
set_tree(x2,y2,INF);
}
for(auto n: P) {
auto[x1,y1,x2,y2,nc]=A[n];
ans=get_min(lx[x1],ly[y1],rx[x2],ry[y2]);
if(ans<INF) Q.emplace(-dist[n]-ans,n);
}
ans=get_min(lx[x1],ly[y1],rx[x2],ry[y2]);
if(ans<INF) Q.emplace(-dist[c]-ans,c);
}
ans=INF;
for(int i=0;i<M;i++) if(chk[i]==2) ans=min(ans,dist[i]);
cout<<(ans<INF ? ans:-1)<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3070 ms |
357392 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
348892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
348892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3070 ms |
357392 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
