#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long inf=1e18;
long long ln,n,wg[100069],com[100069],nr[100069];
pair<long long,pair<long long,long long>> a[100069];
pair<long long,long long> xy[100069],as[100069];
priority_queue<pair<long long,long long>> pq;
struct segtree
{
long long l,r,nn;
vector<long long> vl,dsu;
segtree *p[2];
long long fd(long long x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
void bd(long long lh,long long rh)
{
l=lh;
r=rh;
nn=0;
vl.push_back(0);
dsu.push_back(0);
if(l<r)
{
long long ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
}
}
void ins(long long x,long long w)
{
if(l>x||r<x);
else
{
nn++;
vl.push_back(w);
dsu.push_back(nn);
if(!(l>=x&&r<=x))
{
long long ii;
for(ii=0;ii<2;ii++)
{
p[ii]->ins(x,w);
}
}
}
}
void qr(long long lh,long long rh,long long ub,long long w)
{
if(l>rh||r<lh);
else if(l>=lh&&r<=rh)
{
long long p;
for(;nn&&xy[vl[fd(1)]].sc<=ub;dsu[fd(1)]=fd((fd(1)+1)%(nn+1)))
{
p=vl[fd(1)];
if(w+wg[p]<nr[p])
{
pq.push({-w-wg[p],p});
nr[p]=w+wg[p];
}
}
}
else
{
long long ii;
for(ii=0;ii<2;ii++)
{
p[ii]->qr(lh,rh,ub,w);
}
}
}
}
sg;
int main()
{
long long i,k,l,w,ti,p,x,z=inf;
scanf("%lld%lld",&ln,&n);
xy[0]={inf,inf};
for(i=1;i<=n;i++)
{
scanf("%lld%lld%lld%lld",&ti,&k,&l,wg+i);
a[i]={ti,{k,l}};
xy[i]={k+ti,k-ti};
com[i]=k+ti;
as[i]={k-ti,i};
nr[i]=inf;
}
sort(com+1,com+n+1);
sort(as+1,as+n+1);
sg.bd(1,n);
for(i=1;i<=n;i++)
{
p=as[i].sc;
x=xy[p].fr;
sg.ins(lower_bound(com+1,com+n+1,x)-com,p);
}
for(i=1;i<=n;i++)
{
k=a[i].sc.fr;
if(k==1)
{
pq.push({-wg[i],i});
nr[i]=wg[i];
}
}
for(;!pq.empty();)
{
w=-pq.top().fr;
p=pq.top().sc;
pq.pop();
ti=a[p].fr;
l=a[p].sc.sc;
sg.qr(1,upper_bound(com+1,com+n+1,l+1+ti)-com-1,l+1-ti,w);
}
for(i=1;i<=n;i++)
{
l=a[i].sc.sc;
if(l==ln)
{
z=min(z,nr[i]);
}
}
if(z==inf)
{
z=-1;
}
printf("%lld\n",z);
}
Compilation message
treatment.cpp: In function 'int main()':
treatment.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%lld%lld",&ln,&n);
| ~~~~~^~~~~~~~~~~~~~~~~~~
treatment.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%lld%lld%lld%lld",&ti,&k,&l,wg+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
303 ms |
75740 KB |
Output is correct |
2 |
Correct |
264 ms |
75720 KB |
Output is correct |
3 |
Correct |
268 ms |
75280 KB |
Output is correct |
4 |
Correct |
244 ms |
75300 KB |
Output is correct |
5 |
Correct |
260 ms |
74332 KB |
Output is correct |
6 |
Correct |
288 ms |
77436 KB |
Output is correct |
7 |
Correct |
277 ms |
80664 KB |
Output is correct |
8 |
Correct |
158 ms |
72108 KB |
Output is correct |
9 |
Correct |
158 ms |
77364 KB |
Output is correct |
10 |
Correct |
216 ms |
80592 KB |
Output is correct |
11 |
Correct |
498 ms |
77924 KB |
Output is correct |
12 |
Correct |
367 ms |
77924 KB |
Output is correct |
13 |
Correct |
465 ms |
77780 KB |
Output is correct |
14 |
Correct |
473 ms |
77960 KB |
Output is correct |
15 |
Correct |
357 ms |
75744 KB |
Output is correct |
16 |
Correct |
329 ms |
75768 KB |
Output is correct |
17 |
Correct |
348 ms |
74960 KB |
Output is correct |
18 |
Correct |
420 ms |
77084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
308 KB |
Output is correct |
11 |
Correct |
1 ms |
284 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
312 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
324 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
308 KB |
Output is correct |
11 |
Correct |
1 ms |
284 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
312 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
324 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
16 ms |
3960 KB |
Output is correct |
21 |
Correct |
17 ms |
3948 KB |
Output is correct |
22 |
Correct |
17 ms |
3940 KB |
Output is correct |
23 |
Correct |
12 ms |
3916 KB |
Output is correct |
24 |
Correct |
21 ms |
4056 KB |
Output is correct |
25 |
Correct |
18 ms |
4032 KB |
Output is correct |
26 |
Correct |
17 ms |
4040 KB |
Output is correct |
27 |
Correct |
14 ms |
3980 KB |
Output is correct |
28 |
Correct |
14 ms |
4044 KB |
Output is correct |
29 |
Correct |
18 ms |
3944 KB |
Output is correct |
30 |
Correct |
14 ms |
3980 KB |
Output is correct |
31 |
Correct |
13 ms |
4004 KB |
Output is correct |
32 |
Correct |
27 ms |
4208 KB |
Output is correct |
33 |
Correct |
13 ms |
4172 KB |
Output is correct |
34 |
Correct |
14 ms |
3916 KB |
Output is correct |
35 |
Correct |
15 ms |
4172 KB |
Output is correct |
36 |
Correct |
14 ms |
4112 KB |
Output is correct |
37 |
Correct |
13 ms |
3916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
303 ms |
75740 KB |
Output is correct |
2 |
Correct |
264 ms |
75720 KB |
Output is correct |
3 |
Correct |
268 ms |
75280 KB |
Output is correct |
4 |
Correct |
244 ms |
75300 KB |
Output is correct |
5 |
Correct |
260 ms |
74332 KB |
Output is correct |
6 |
Correct |
288 ms |
77436 KB |
Output is correct |
7 |
Correct |
277 ms |
80664 KB |
Output is correct |
8 |
Correct |
158 ms |
72108 KB |
Output is correct |
9 |
Correct |
158 ms |
77364 KB |
Output is correct |
10 |
Correct |
216 ms |
80592 KB |
Output is correct |
11 |
Correct |
498 ms |
77924 KB |
Output is correct |
12 |
Correct |
367 ms |
77924 KB |
Output is correct |
13 |
Correct |
465 ms |
77780 KB |
Output is correct |
14 |
Correct |
473 ms |
77960 KB |
Output is correct |
15 |
Correct |
357 ms |
75744 KB |
Output is correct |
16 |
Correct |
329 ms |
75768 KB |
Output is correct |
17 |
Correct |
348 ms |
74960 KB |
Output is correct |
18 |
Correct |
420 ms |
77084 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
296 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
304 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
308 KB |
Output is correct |
29 |
Correct |
1 ms |
284 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
312 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
324 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
16 ms |
3960 KB |
Output is correct |
39 |
Correct |
17 ms |
3948 KB |
Output is correct |
40 |
Correct |
17 ms |
3940 KB |
Output is correct |
41 |
Correct |
12 ms |
3916 KB |
Output is correct |
42 |
Correct |
21 ms |
4056 KB |
Output is correct |
43 |
Correct |
18 ms |
4032 KB |
Output is correct |
44 |
Correct |
17 ms |
4040 KB |
Output is correct |
45 |
Correct |
14 ms |
3980 KB |
Output is correct |
46 |
Correct |
14 ms |
4044 KB |
Output is correct |
47 |
Correct |
18 ms |
3944 KB |
Output is correct |
48 |
Correct |
14 ms |
3980 KB |
Output is correct |
49 |
Correct |
13 ms |
4004 KB |
Output is correct |
50 |
Correct |
27 ms |
4208 KB |
Output is correct |
51 |
Correct |
13 ms |
4172 KB |
Output is correct |
52 |
Correct |
14 ms |
3916 KB |
Output is correct |
53 |
Correct |
15 ms |
4172 KB |
Output is correct |
54 |
Correct |
14 ms |
4112 KB |
Output is correct |
55 |
Correct |
13 ms |
3916 KB |
Output is correct |
56 |
Correct |
340 ms |
77772 KB |
Output is correct |
57 |
Correct |
335 ms |
77672 KB |
Output is correct |
58 |
Correct |
354 ms |
76356 KB |
Output is correct |
59 |
Correct |
320 ms |
76872 KB |
Output is correct |
60 |
Correct |
391 ms |
76152 KB |
Output is correct |
61 |
Correct |
385 ms |
76220 KB |
Output is correct |
62 |
Correct |
341 ms |
77732 KB |
Output is correct |
63 |
Correct |
320 ms |
77248 KB |
Output is correct |
64 |
Correct |
279 ms |
77280 KB |
Output is correct |
65 |
Correct |
318 ms |
75940 KB |
Output is correct |
66 |
Correct |
348 ms |
76148 KB |
Output is correct |
67 |
Correct |
630 ms |
76776 KB |
Output is correct |
68 |
Correct |
616 ms |
76676 KB |
Output is correct |
69 |
Correct |
470 ms |
76644 KB |
Output is correct |
70 |
Correct |
783 ms |
76836 KB |
Output is correct |
71 |
Correct |
617 ms |
76688 KB |
Output is correct |
72 |
Correct |
410 ms |
76548 KB |
Output is correct |
73 |
Correct |
718 ms |
76812 KB |
Output is correct |
74 |
Correct |
364 ms |
76588 KB |
Output is correct |
75 |
Correct |
299 ms |
76572 KB |
Output is correct |
76 |
Correct |
442 ms |
78624 KB |
Output is correct |
77 |
Correct |
720 ms |
79036 KB |
Output is correct |
78 |
Correct |
498 ms |
78556 KB |
Output is correct |
79 |
Correct |
879 ms |
76732 KB |
Output is correct |
80 |
Correct |
341 ms |
76524 KB |
Output is correct |
81 |
Correct |
430 ms |
76688 KB |
Output is correct |
82 |
Correct |
420 ms |
75928 KB |
Output is correct |
83 |
Correct |
440 ms |
76180 KB |
Output is correct |
84 |
Correct |
702 ms |
75984 KB |
Output is correct |
85 |
Correct |
432 ms |
76592 KB |
Output is correct |
86 |
Correct |
485 ms |
76584 KB |
Output is correct |
87 |
Correct |
459 ms |
76660 KB |
Output is correct |
88 |
Correct |
360 ms |
77360 KB |
Output is correct |
89 |
Correct |
505 ms |
76668 KB |
Output is correct |
90 |
Correct |
677 ms |
78864 KB |
Output is correct |
91 |
Correct |
642 ms |
78244 KB |
Output is correct |
92 |
Correct |
546 ms |
76788 KB |
Output is correct |
93 |
Correct |
727 ms |
76656 KB |
Output is correct |
94 |
Correct |
370 ms |
77876 KB |
Output is correct |
95 |
Correct |
572 ms |
76564 KB |
Output is correct |
96 |
Correct |
787 ms |
78884 KB |
Output is correct |
97 |
Correct |
673 ms |
78956 KB |
Output is correct |
98 |
Correct |
721 ms |
78824 KB |
Output is correct |
99 |
Correct |
742 ms |
78896 KB |
Output is correct |
100 |
Correct |
433 ms |
79112 KB |
Output is correct |
101 |
Correct |
692 ms |
78716 KB |
Output is correct |
102 |
Correct |
586 ms |
78772 KB |
Output is correct |
103 |
Correct |
553 ms |
77036 KB |
Output is correct |