# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1226505 | _rain_ | Sparklers (JOI17_sparklers) | C++20 | 12 ms | 1628 KiB |
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=(int)1e6;
const long double eps=1e-17;
int x[N+2];
int n,k;
LL X[N+2];
LL t;
bool maximize(LL &x,LL y){
if (x<=y) return x=y,true;
return false;
}
bool minimize(LL &x,LL y){
if (x>=y) return x=y,true;
return false;
}
bool possible(LL s){
if (s==0){
for(int i=2;i<=n;++i) if (x[i]!=x[i-1]) return false;
return true;
}
for(int i=1;i<=n;++i) X[i]=x[i]-s*t*2*i;
int l=k,r=k;
int gl=k,gr=k;
bool nxt=true;
while (nxt){
nxt=false;
LL mx;
int tmp_l=l,best_l=l;
mx=X[l];
while (tmp_l>=1 && X[tmp_l]>=X[r]){
if (maximize(mx,X[tmp_l])) best_l=tmp_l;
--tmp_l;
}
if (l!=best_l) {
l=best_l;
gl=l;
nxt=true;
}
int tmp_r=r,best_r=r;
mx=X[r];
while (tmp_r<=n && X[l]>=X[tmp_r]){
if (minimize(mx,X[tmp_r])) best_r=tmp_r;
++tmp_r;
}
if (best_r!=r){
r=best_r;
gr=r;
nxt=true;
}
}
l=1,r=n;
nxt=true;
while (nxt){
nxt=false;
LL mx;
int tmp_l=l,best_l=l;
mx=X[l];
while (tmp_l<=gl && X[tmp_l]>=X[r]){
if (maximize(mx,X[tmp_l])) best_l=tmp_l;
++tmp_l;
}
if (l!=best_l) {
l=best_l;
nxt=true;
}
int tmp_r=r,best_r=r;
mx=X[r];
while (tmp_r>=gr && X[l]>=X[tmp_r]){
if (minimize(mx,X[tmp_r])) best_r=tmp_r;
--tmp_r;
}
if (best_r!=r){
r=best_r;
nxt=true;
}
}
return l==gl && r==gr;
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
#define task "main"
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin>>n>>k>>t;
for(int i=1;i<=n;++i) cin>>x[i];
int low=0,high=*max_element(x+1,x+n+1),ans=-1;
while (low<=high){
int mid=(low+high)/2;
if (possible(mid)){
ans=mid;
high=mid-1;
}
else low=mid+1;
}
cout<<ans;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |