Educational codeforces round 126 (rated for Div. 2) f.teleporters (two sets and two points)

subject

The positive axis of the number axis has n(n<=2e5) On the hour ,

From the point of i To j The cost of is the square of the difference between the two , Given a

You need to get from 0 To , The cost does not exceed , Ask at least how many whole points to add , time limit 7 second

Source of ideas

Liangshen

Answer key

Before you think about the correct solution, you might as well consider how to do it with simplicity , Then consider how to optimize ,dp such , Line segment tree && The same goes for two points

n There are n Segment length distance , Consider giving the i Add a A little bit , And to the first i Add a+1 A little bit ,

Compare the two , Add a dot , There is a value corresponding to the cost reduction , Write it down as x,

If the priority queue can be maintained violently , Obviously every time I look x Maximum value ,

hold a out , Total cost minus x, And then a+1 Throw it back ,

Then you can consider the process of dichotomy , Bisect all segments , The value of incremental cost reduction >x The smallest that has been used up x,

Find out the x after , How many points are actually inserted into each line segment L, That makes it possible to add L Points minus plus L+1 The increment of points shall not exceed x, adopt L Calculate the contribution to the sum of costs

be equal to x The increment of may have used a part , Here is to consider x The increment of ,

At this time, it must be less than m, So you can consider going back delta/x A little bit ,

Because it is x The emergence of makes from >m become <=m, therefore x It must be enough , Direct division

Experience

Not complicated , But the greater than sign and greater than or equal sign have been adjusted for a long time , Lead to E There is no time to write after the title

Liangshen ： Can you really write binary search ？ I ： Obviously not. .

Code

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f,N=2e5+10;
#define dbg1(x) cerr<<(#x)<<" "<<(x)<<" ";
#define dbg2(x) cerr<<(#x)<<" "<<(x)<<" "<<endl;
typedef long long ll;
const ll mx=1e18;
int n,a[N];
ll b[N],m,ans,tot1,sum1;
ll sq(ll x){
    return x*x;
}
ll cal(ll x,ll a){// Long for x Divide into m The cost of the segment 
    if(a>x)return x;
    ll v=x%a,r=x/a;
    ll ans=v*sq(r+1)+(a-v)*sq(r);
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        b[i]=a[i]-a[i-1];
    }
    scanf("%lld",&m);
    ll l=0,r=mx;
    while(l<=r){
        ll mid=(l+r)/2,sum=0;
        for(int i=1;i<=n;++i){
            ll L=1,R=b[i];
            while(L<=R){
                ll M=(L+R)/2;
                if(cal(b[i],M)-cal(b[i],M+1)>=mid){
                    L=M+1;
                }
                else{
                    R=M-1;
                }
            }
            sum+=cal(b[i],L);
        }
        if(sum<=m){
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    for(int i=1;i<=n;++i){
        ll L=1,R=b[i];
        while(L<=R){
            ll M=(L+R)/2;
            if(cal(b[i],M)-cal(b[i],M+1)>=r){
                L=M+1;
            }
            else{
                R=M-1;
            }
        }
        sum1+=cal(b[i],L);
        tot1+=L-1;
    }
    printf("%lld\n",tot1-(m-sum1)/r);
    return 0;
}