#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef vector<int> vi;
#define F first
#define S second
#define pb push_back
const int MN = 1e5+5;
int N, K, T, i, j, lo, hi, mid, arr[MN];
pdd a[MN];
struct SegmentTree{
struct nd{double mn, ans, lz; int sna;}st[6*MN];
int n, c;
void build(int i,int s,int e,vector<double> &vec){
if(s!=e){
build(2*i,s,(s+e)/2,vec);
build(2*i+1,(s+e)/2+1,e,vec);
st[i].mn = min(st[2*i].mn, st[2*i+1].mn);
st[i].ans = max(st[2*i].ans, st[2*i+1].ans);
st[i].sna = (st[i].ans==st[2*i].ans)?st[2*i].sna:st[2*i+1].sna;
}
else st[i].mn=st[i].ans=vec[s-1], st[i].sna=s;
st[i].lz=0;
}
void init(int N,vector<double> vec){
n = N; c = 1;
for(int i=1;i<vec.size();i++)
vec[i] += vec[i-1];
if(N) build(1,1,n,vec);
}
inline void upd_lz(int i,int s,int e){
if(st[i].lz){
st[i].mn += st[i].lz, st[i].ans += st[i].lz;
if(s!=e) st[2*i].lz += st[i].lz, st[2*i+1].lz += st[i].lz;
st[i].lz = 0;
}
}
void upd(int i,int s,int e,int ss,int se,double val){
if(ss>se) return;
upd_lz(i,s,e);
if(s>=ss&&e<=se) st[i].lz=val, upd_lz(i,s,e);
else{
if((s+e)/2<ss) upd(2*i+1,(s+e)/2+1,e,ss,se,val), upd_lz(2*i,s,(s+e)/2);
else if((s+e)/2>=se) upd(2*i,s,(s+e)/2,ss,se,val), upd_lz(2*i+1,(s+e)/2+1,e);
else upd(2*i,s,(s+e)/2,ss,se,val), upd(2*i+1,(s+e)/2+1,e,ss,se,val);
st[i].mn = min(st[2*i].mn, st[2*i+1].mn);
st[i].ans = max(st[2*i].ans, st[2*i+1].ans);
st[i].sna = (st[i].ans==st[2*i].ans)?st[2*i].sna:st[2*i+1].sna;
}
}
double get(int i,int s,int e,int ind){
upd_lz(i,s,e);
if(s==e) return st[i].ans;
else if((s+e)/2<ind) return get(2*i+1,(s+e)/2+1,e,ind);
else return get(2*i,s,(s+e)/2,ind);
}
pair<double,int> qu(int i,int s,int e,int ss,int se){
upd_lz(i,s,e);
if(ss>se) return make_pair(-1e9,-1);
if(s>=ss&&e<=se) return make_pair(st[i].ans,st[i].sna);
else if((s+e)/2<ss) return qu(2*i+1,(s+e)/2+1,e,ss,se);
else if((s+e)/2>=se) return qu(2*i,s,(s+e)/2,ss,se);
else{
pair<double,int> l=qu(2*i,s,(s+e)/2,ss,se), r=qu(2*i+1,(s+e)/2+1,e,ss,se);
pair<double,int> ret;
ret.F=max(l.F,r.F);
ret.S=l.F==ret.F?l.S:r.S;
return ret;
}
}
int qu2(int i,int s,int e,int ss,int se,double lim){
upd_lz(i,s,e);
if(ss>se) return -1;
if(s>=ss&&e<=se){
if(lim+st[i].mn>=0) return e;
else if(s==e) return -1;
}
else if((s+e)/2<ss) return qu2(2*i+1,(s+e)/2+1,e,ss,se,lim);
else if((s+e)/2>=se) return qu2(2*i,s,(s+e)/2,ss,se,lim);
int r=qu2(2*i,s,(s+e)/2,ss,se,lim);
if(r==(s+e)/2) return max(r,qu2(2*i+1,(s+e)/2+1,e,ss,se,lim));
else return r;
}
pair<double,int> qu(double t){
if(!n) return make_pair(-1e9,-1);
else return qu(1,1,n,c,qu2(1,1,n,c,n,t));
}
void upd(int idx){
upd(1,1,n,idx+1,n,-get(1,1,n,idx));
c=idx+1;
}
bool done(){return c>n;}
}L,R;
int main(){
scanf("%d%d%d",&N,&K,&T);
for(i=1;i<=N;i++)
scanf("%d",&arr[i]);
if(arr[N]==0){
printf("0\n");
return 0;
}
lo = 1, hi = 1e9;
while(lo<hi){
mid = (lo+hi)>>1;
vector<double> LL, RR;
for(i=K-1;i>=1;i--){
LL.pb(-(arr[i+1]-arr[i])/(double)(2*mid));
LL.pb(T);
}
L.init(LL.size(),LL);
for(i=K+1;i<=N;i++){
RR.pb(-(arr[i]-arr[i-1])/(double)(2*mid));
RR.pb(T);
}
R.init(RR.size(),RR);
int fl = 0; double t = T;
while(!L.done()||!R.done()){
auto lef = L.qu(t);
auto rit = R.qu(t);
if(t+lef.F>=0){
if(t+rit.F>=0){
if(lef.F>rit.F){
t += lef.F;
L.upd(lef.S);
}
else{
t += rit.F;
R.upd(rit.S);
}
}
else{
t += lef.F;
L.upd(lef.S);
}
}
else{
if(t+rit.F<0){fl=1; break;}
else{
t += rit.F;
R.upd(rit.S);
}
}
}
if(fl) lo=mid+1;
else hi=mid;
}
printf("%d\n",lo);
return 0;
}
Compilation message
sparklers.cpp: In member function 'void SegmentTree::init(int, std::vector<double>)':
sparklers.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<vec.size();i++)
~^~~~~~~~~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&N,&K,&T);
~~~~~^~~~~~~~~~~~~~~~~~~
sparklers.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&arr[i]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
