#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;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int SZ=1<<18;
set<pair<int,int>> xtree[2*SZ], ytree[2*SZ];
vector<int> P, x, y;
vector<tuple<int,int,int,int,int>> A;
long long dist[100000];
int chk[100000];
void set_tree(set<pair<int,int>> *tree, int s, int e, int p1, int p2, int i)
{
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) {
tree[s].emplace(p1,i);
tree[s++].emplace(p2,i);
}
if(~e&1) {
tree[e].emplace(p1,i);
tree[e--].emplace(p2,i);
}
}
}
void erase_tree(set<pair<int,int>> *tree, int s, int e, int p1, int p2, int i)
{
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) {
tree[s].erase({p1,i});
tree[s++].erase({p2,i});
}
if(~e&1) {
tree[e].erase({p1,i});
tree[e--].erase({p2,i});
}
}
}
void get_pos(set<pair<int,int>> *tree, int s, int e, int l, int r)
{
for(int n=s+SZ;n;n>>=1) for(auto L=tree[n].lower_bound({l,0}),R=tree[n].lower_bound({r+1,0});L!=R;++L) P.push_back(L->second);
for(int n=e+SZ;n;n>>=1) for(auto L=tree[n].lower_bound({l,0}),R=tree[n].lower_bound({r+1,0});L!=R;++L) P.push_back(L->second);
}
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;
if(r==N) chk[i]|=2;
x.push_back(l+t);
x.push_back(r+t);
y.push_back(l-t);
y.push_back(r-t);
tie(t,l,r,aa)=make_tuple(l+t,l-t,r+t,r-t);
}
sort(x.begin(),x.end()); x.resize(unique(x.begin(),x.end())-x.begin());
sort(y.begin(),y.end()); y.resize(unique(y.begin(),y.end())-y.begin());
for(int i=0;i<M;i++) {
auto &[x1,y1,x2,y2,c]=A[i];
x1=lower_bound(x.begin(),x.end(),x1)-x.begin();
y1=lower_bound(y.begin(),y.end(),y1)-y.begin();
x2=lower_bound(x.begin(),x.end(),x2)-x.begin();
y2=lower_bound(y.begin(),y.end(),y2)-y.begin();
if(chk[i]&1) Q.emplace(-(dist[i]=c),i);
else {
set_tree(xtree,x1,x2,y1,y2,i);
set_tree(ytree,y1,y2,x1,x2,i);
}
}
while(!Q.empty()) {
auto[t,c]=Q.top();
Q.pop();
P.clear();
auto[x1,y1,x2,y2,d]=A[c];
get_pos(xtree,x1,x2,y1,y2); get_pos(ytree,y1,y2,x1,x2);
for(auto n: P) if(dist[n]==INF) {
auto[x1,y1,x2,y2,d]=A[n];
dist[n]=dist[c]+d;
erase_tree(xtree,x1,x2,y1,y2,n);
erase_tree(ytree,y1,y2,x1,x2,n);
Q.emplace(-dist[n],n);
}
}
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 |
Correct |
294 ms |
82064 KB |
Output is correct |
| 2 |
Correct |
267 ms |
82120 KB |
Output is correct |
| 3 |
Execution timed out |
3083 ms |
239848 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
50272 KB |
Output is correct |
| 2 |
Incorrect |
32 ms |
50236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
50272 KB |
Output is correct |
| 2 |
Incorrect |
32 ms |
50236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
294 ms |
82064 KB |
Output is correct |
| 2 |
Correct |
267 ms |
82120 KB |
Output is correct |
| 3 |
Execution timed out |
3083 ms |
239848 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
