#include <bits/stdc++.h>
#define L long long
using namespace std;
L N,K,T;
L loc[100010];
L a[100010];
L vlfdy[100010];
L gain[100010];
bool ok(L x,L det){
L t=x*T*2;
L i,s=K,e=K,health;
/*while(s>1&&e<N)
{
printf("%lld %lld %lld\n",s,e,left);
L t1=loc[s]-loc[s-1];
L t2=loc[e+1]-loc[e];
if(t1<t2)
{
if(t1>left) return 0;
left=left-t1+t;
s--;
}
else
{
if(t2>left) return 0;
left=left-t2+t;
e++;
}
}
while(s>1)
{
printf("%lld %lld %lld\n",s,e,left);
L t1=loc[s]-loc[s-1];
if(t1>left) return 0;
left=left-t1+t;
s--;
}
while(e<N)
{
printf("%lld %lld %lld\n",s,e,left);
L t2=loc[e+1]-loc[e];
if(t2>left) return 0;
left=left-t2+t;
e++;
}*/
for(i=1;i<=N;i++)
{
vlfdy[i]=gain[i]=0;
}
queue<L>lloc,lvlfdy,lgain;
queue<L>rloc,rvlfdy,rgain;
//printf("***%lld %lld***\n",x,t);
health=0;
for(i=K-1;i>=1;i--)
{
health+=loc[i+1]-loc[i];
vlfdy[i]=max(vlfdy[i+1],health);
health-=t;
gain[i]=-health;
if(gain[i]>0)
{
//printf("%lld %lld %lld\n",i,vlfdy[i],gain[i]);
lloc.push(i);
lvlfdy.push(vlfdy[i]);
lgain.push(gain[i]);
health=0;
vlfdy[i]=0;
}
}
health=0;
for(i=K+1;i<=N;i++)
{
health+=loc[i]-loc[i-1];
vlfdy[i]=max(vlfdy[i-1],health);
health-=t;
gain[i]=-health;
if(gain[i]>0)
{
//printf("%lld %lld %lld\n",i,vlfdy[i],gain[i]);
rloc.push(i);
rvlfdy.push(vlfdy[i]);
rgain.push(gain[i]);
health=0;
vlfdy[i]=0;
}
}
/*for(i=1;i<=N;i++)
{
printf("%lld %lld\n",vlfdy[i],gain[i]);
}*/
health=t;
while(!lloc.empty()&&!rloc.empty())
{
if(lvlfdy.front()<=health)
{
health+=lgain.front();
s=lloc.front();
lloc.pop();
lvlfdy.pop();
lgain.pop();
}
else if(rvlfdy.front()<=health)
{
health+=rgain.front();
e=rloc.front();
rloc.pop();
rvlfdy.pop();
rgain.pop();
}
else return 0;
}
while(!lloc.empty())
{
if(lvlfdy.front()<=health)
{
health+=lgain.front();
s=lloc.front();
lloc.pop();
lvlfdy.pop();
lgain.pop();
}
else return 0;
}
while(!rloc.empty())
{
if(rvlfdy.front()<=health)
{
health+=rgain.front();
e=rloc.front();
rloc.pop();
rvlfdy.pop();
rgain.pop();
}
else return 0;
}
//printf("%lld %lld\n",s,e);
if(det==1)
{
while(e<N)
{
//printf("%lld %lld %lld\n",s,e,left);
L t2=loc[e+1]-loc[e];
if(t2>health) return 0;
health=health-t2+t;
e++;
}
while(s>1)
{
//printf("%lld %lld %lld\n",s,e,left);
L t1=loc[s]-loc[s-1];
if(t1>health) return 0;
health=health-t1+t;
s--;
}
}
else
{
while(s>1)
{
//printf("%lld %lld %lld\n",s,e,left);
L t1=loc[s]-loc[s-1];
if(t1>health) return 0;
health=health-t1+t;
s--;
}
while(e<N)
{
//printf("%lld %lld %lld\n",s,e,left);
L t2=loc[e+1]-loc[e];
if(t2>health) return 0;
health=health-t2+t;
e++;
}
}
return 1;
}
L bin(L s,L e){
if(s==e) return s;
L mid=(s+e)/2;
if(ok(mid,1)||ok(mid,2)) return bin(s,mid);
else return bin(mid+1,e);
}
int main()
{
scanf("%lld %lld %lld",&N,&K,&T);
L i,st;
for(i=1;i<=N;i++)
{
scanf("%lld",&loc[i]);
}
st=loc[K];
for(i=1;i<=N;i++)
{
loc[i]-=st;
}
L temp=bin(0,1000000001);
if(temp==1000000001) while(1)
{
L asdf=10/0;
}
printf("%lld",temp);
}
Compilation message
sparklers.cpp: In function 'int main()':
sparklers.cpp:208:12: warning: division by zero [-Wdiv-by-zero]
L asdf=10/0;
~~^~
sparklers.cpp:208:5: warning: unused variable 'asdf' [-Wunused-variable]
L asdf=10/0;
^~~~
sparklers.cpp:194:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld",&N,&K,&T);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:198:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&loc[i]);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
3 ms |
424 KB |
Output is correct |
| 4 |
Correct |
2 ms |
448 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Correct |
2 ms |
564 KB |
Output is correct |
| 7 |
Correct |
3 ms |
568 KB |
Output is correct |
| 8 |
Correct |
3 ms |
572 KB |
Output is correct |
| 9 |
Correct |
3 ms |
628 KB |
Output is correct |
| 10 |
Correct |
3 ms |
628 KB |
Output is correct |
| 11 |
Correct |
3 ms |
632 KB |
Output is correct |
| 12 |
Incorrect |
4 ms |
664 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
3 ms |
424 KB |
Output is correct |
| 4 |
Correct |
2 ms |
448 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Correct |
2 ms |
564 KB |
Output is correct |
| 7 |
Correct |
3 ms |
568 KB |
Output is correct |
| 8 |
Correct |
3 ms |
572 KB |
Output is correct |
| 9 |
Correct |
3 ms |
628 KB |
Output is correct |
| 10 |
Correct |
3 ms |
628 KB |
Output is correct |
| 11 |
Correct |
3 ms |
632 KB |
Output is correct |
| 12 |
Incorrect |
4 ms |
664 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
3 ms |
424 KB |
Output is correct |
| 4 |
Correct |
2 ms |
448 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Correct |
2 ms |
564 KB |
Output is correct |
| 7 |
Correct |
3 ms |
568 KB |
Output is correct |
| 8 |
Correct |
3 ms |
572 KB |
Output is correct |
| 9 |
Correct |
3 ms |
628 KB |
Output is correct |
| 10 |
Correct |
3 ms |
628 KB |
Output is correct |
| 11 |
Correct |
3 ms |
632 KB |
Output is correct |
| 12 |
Incorrect |
4 ms |
664 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
