题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2216
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
const int MAXN = 500000+9;
const double EPS = 1e-8;
int arr[MAXN],n,f[MAXN],l[MAXN],r[MAXN],que[MAXN],head,tail;
inline int read(){
char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret;
}
inline double cal(int a, int b){
return sqrt(abs(a-b)) + arr[a];
}
int main(){
n = read();
for (int i=1;i<=n;i++) arr[i] = read();
l[tail=head=1] = 1; r[1] = n; que[1]=1;
for (int i=2;i<=n;i++) {
l[tail]++;
while (tail <= head && r[tail] < l[tail]) tail++;
f[i] = max(f[i], int(ceil(cal(que[tail],i))+EPS));
if (cal(i,r[head]) < cal(que[head],r[head])) continue;
else {
while (tail <= head && cal(i,l[head]) > cal(que[head],l[head])) head--;
if (tail <= head) {
int ls=l[head],rs=r[head],mid,ans=r[head]-1;
while (ls <= rs) {
mid = ls + rs >> 1;
if (cal(i,mid) < cal(que[head],mid)) ls = mid+1;
else ans = mid, rs = mid-1;
}
r[head] = ans; l[++head] = ans+1; r[head] = n; que[head] = i;
} else que[++head] = i, l[head] = i, r[head] = n;
}
}
l[tail=head=1] = n; r[1] = 1; que[1]=n; que[0]=1;
for (int i=n-1;i;i--) {
l[tail]--;
while (tail <= head && r[tail] > l[tail]) tail++;
f[i] = max(f[i], int(ceil(cal(que[tail],i))+EPS));
if (cal(i,r[head]) < cal(que[head],r[head])) continue;
else {
while (tail <= head && cal(i,l[head]) > cal(que[head],l[head])) head--;
if (tail <= head) {
int ls=l[head],rs=r[head],mid,ans=r[head]+1;
while (ls >= rs) {
mid = ls + rs >> 1;
if (cal(i,mid) < cal(que[head],mid)) ls = mid-1;
else ans = mid, rs = mid+1;
}
r[head] = ans; l[++head] = ans-1; r[head] = 1; que[head] = i;
} else que[++head] = i, l[head] = i, r[head] = 1;
}
}
for (int i=1;i<=n;i++) printf("%d\n",max(f[i]-arr[i],0));
return 0;
}
Very descriptive post, I liked that a lot. Will there be a part 2?
Wow, this post is fastidious, my sister is analyzing such things, thus I am going to tell her.
I like the helpful info you provide in your articles. I
will bookmark your blog and check again here frequently.
I’m quite certain I will learn lots of new stuff right here!
Good luck for the next!
An outstanding share! I have just forwarded this
onto a colleague who was doing a little research on this.
And he actually ordered me lunch due to the fact that I stumbled upon it for him…
lol. So allow me to reword this…. Thanks for the meal!!
But yeah, thanx for spending the time to discuss this matter here on your site.
It’s in fact very complex in this full of activity life to listen news on TV, thus I just use world wide web for that purpose, and obtain the most up-to-date news.
I’d like to find out more? I’d want to find out some additional
information.
I’m not sure exactly why but this website is loading very slow
for me. Is anyone else having this problem or is it a issue on my end?
I’ll check back later and see if the problem still exists.
Hi every one, here every person is sharing such knowledge, so
it’s pleasant to read this blog, and I used to pay a quick
visit this web site everyday.
Amazing blog! Is your theme custom made or did you download
it from somewhere? A theme like yours with a few simple adjustements would really make my blog shine.
Please let me know where you got your design. Kudos
Normally I don’t read article on blogs, however I would like to say that
this write-up very forced me to check out and do it!
Your writing taste has been surprised me. Thanks, very nice article.
Thanks for sharing your thoughts. I really appreciate
your efforts and I will be waiting for your further write ups thanks once again.
Hello there, just became alert to your blog through Google, and
found that it’s really informative. I am gonna watch out for brussels.
I will be grateful if you continue this in future.
Lots of people will be benefited from your writing. Cheers!
I’m not sure where you’re getting your information, but great topic.
I needs to spend some time learning much more or understanding more.
Thanks for magnificent info I was looking for this information for my mission.
Thanks for sharing such a pleasant opinion, paragraph
is pleasant, thats why i have read it entirely
Hi! I know this is kind of off topic but I was wondering which blog platform are you using for this website?
I’m getting fed up of WordPress because I’ve had issues with hackers and I’m looking at alternatives for another platform.
I would be fantastic if you could point me in the direction of a good platform.
No matter if some one searches for his necessary thing, therefore he/she needs
to be available that in detail, thus that thing is maintained over here.
I have been surfing online more than three hours today, yet I never found any interesting article like yours. It is pretty worth enough for me. Personally, if all website owners and bloggers made good content as you did, the internet will be a lot more useful than ever before.
I got this website from my friend who told me on the topic
of this site and now this time I am browsing this site and reading very informative articles
at this time.
Great information. Lucky me I came across your site by accident (stumbleupon).
I have book marked it for later!
I really like reading an article that will
make men and women think. Also, thank you for allowing for me to comment!
Hello to every single one, it’s genuinely a good
for me to pay a quick visit this site, it consists of precious Information.
Wow, this post is pleasant, my younger sister is analyzing
these kinds of things, thus I am going to let know her.
Hello to every body, it’s my first pay a quick visit of this blog; this
webpage includes awesome and genuinely fine information designed for readers.
Hey would you mind sharing which blog platform you’re using?
I’m going to start my own blog soon but I’m having a difficult time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems different then most blogs and I’m looking
for something completely unique. P.S Apologies for getting off-topic
but I had to ask!
I visited several web sites but the audio feature for audio songs present at this
site is genuinely marvelous.
I used to be suggested this website via my cousin. I am not certain whether or not this post is written through him as nobody else
realize such designated approximately my trouble. You’re wonderful!
Thanks!
I loved as much as you will receive carried out right here.
The sketch is tasteful, your authored subject matter stylish.
nonetheless, you command get got an impatience over
that you wish be delivering the following. unwell unquestionably come
more formerly again since exactly the same nearly very often inside case you shield this increase.
hello!,I love your writing so much! share we be in contact more approximately your article on AOL?
I need an expert on this area to unravel my problem.
May be that is you! Looking forward to peer you.
Very good post.Really looking forward to read more. Really Great.
This is one awesome article post.Really thank you! Really Great.