poi2012 well

二分答案+单调队列。。main过了，bzoj无限tle。。。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int q[1000011];
int n,maxi=0;
int ansx,ansk;
ll m;
int a[1000011];
ll sum[1000011];
ll c[1000011],f[1000011],fr[1000011],fl[1000011],g[1000011];
inline ll min(ll a,ll b){return a<b? a:b;}
inline bool check(int xx){
	ll x=xx;
    int h=0,t=1;
    c[1]=a[1];
    q[t]=1;
    f[1]=0;
    sum[1]=a[1];
    for (int i=2;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
        c[i]=min(c[i-1]+x,a[i]);
        while (h<t&&c[q[t]]+x*q[t]>=c[i]+x*i) t--;
        int j=q[t];
        //printf("i=%d j=%d\n",i,j);
        if (h==t){ f[i]=sum[i]-(c[i]+c[i]+(i-1)*x)*i/2;}
        else { f[i]=sum[i]-sum[j]-(c[i]+c[i]+(i-j-1)*x)*(i-j)/2+f[j];}
        q[++t]=i;
    }
    //for (int i=1;i<=n;i++) printf("f[%d]=%I64d ",i,f[i]);
    //printf("\n");
    //for (int i=1;i<=n;i++) printf("c[%d]=%I64d\n",i,c[i]);
    h=0;  t=1;  q[1]=1; fl[1]=a[1];
    for (int i=2;i<=n;i++){
        while (h+1<t&&c[q[h+2]]+q[h+2]*x<=i*x) h++;
        int j=q[h+1];
        if (c[q[h+1]]+q[h+1]*x>i*x){fl[i]=sum[i]-(i-1)*x*i/2;}
        else {fl[i]=sum[i]-sum[j]-(i-j-1)*x*(i-j)/2+f[j];}
        while (h<t&&c[q[t]]+q[t]*x>=c[i]+i*x) t--;
        q[++t]=i;
    }
    //for (int i=1;i<=n;i++) printf("fl[%d]=%I64d ",i,fl[i]);
    //printf("\n");
    h=0; t=1; c[n]=a[n];  q[t]=n;  g[n]=0;
    sum[n]=a[n];
    for (int i=n-1;i>=1;i--){
        sum[i]=sum[i+1]+a[i];
        c[i]=min(c[i+1]+x,a[i]);
        while (h<t&&c[q[t]]-x*q[t]>=c[i]-x*i) t--;
        int j=q[t];
        if (h==t){ g[i]=sum[i]-(c[i]+c[i]+(n-i)*x)*(n-i+1)/2;}
        else { g[i]=sum[i]-sum[j]-(c[i]+c[i]+(j-i-1)*x)*(j-i)/2+g[j];}
        q[++t]=i;
    }
    //for (int i=1;i<=n;i++) printf("g[%d]=%I64d ",i,g[i]);
    //printf("\n");
    h=0;  t=1;  q[1]=n; fr[n]=a[n];
    ll ans=fr[n]+fl[n]-a[n];
    for (int i=n-1;i>=1;i--){
        while (h+1<t&&c[q[h+2]]-q[h+2]*x<=-i*x) h++;
        int j=q[h+1];
        if (c[q[h+1]]-q[h+1]*x>-i*x){fr[i]=sum[i]-(n-i)*x*(n-i+1)/2;}
        else {fr[i]=sum[i]-sum[j]-(j-i-1)*x*(j-i)/2+g[j];}
        while (h<t&&c[q[t]]-q[t]*x>=c[i]-i*x) t--;
        q[++t]=i;
        ans=min(ans,fl[i]+fr[i]-a[i]);
    }
    //printf("ans=%I64d\n",ans);
    if (ans>m) return false;
    if (x<ansx){
        ansx=x;
        for (int i=1;i<=n;i++){
            if (fr[i]+fl[i]-a[i]<=m){
                ansk=i;
                break;
            }
        }
    }
    return true;
}
inline void half(int l,int r){
    while (l!=r){
        int mm=(l+r)/2;
        //printf("%I64d\n",mm);
        if (check(mm)) r=mm;
        else l=mm+1;
    }
}
int main(){
	//freopen("stu.in","r",stdin);
	//freopen("stu.out","w",stdout);
    scanf("%d%lld",&n,&m);
    ansx=1000000000;  ansk=1000000000;
    for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		maxi=max(maxi,a[i]);
	}
	//printf("%d\n",maxi);
	if (maxi>20000000) maxi=20000000;
	half(0,maxi+1);
	if (ansx==1000000000) half(20000001,100000000);
    printf("%d %d\n",ansk,ansx);
    //printf("%d\n",check(1076));
}