用两个前缀和优化

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define LL long long
using namespace std;
template <class _T> inline void read(_T &_x) {
    int _t; bool _flag=false;
    while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
    if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
    while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
    if(_flag) _x=-_x;
}
const int maxn=200005;
LL le,ri,mid,s,sumn[maxn],sumv[maxn],ans=0x3f3f3f3f3f3f;
int n,m,w[maxn],v[maxn],l[maxn],r[maxn];
bool check(LL x){
    LL tmp=0;
    for(int i=1;i<=n;i++){
        sumn[i]=sumn[i-1]+(x<=w[i]? 1:0);
        sumv[i]=sumv[i-1]+(x<=w[i]? v[i]:0);
    }
    for(int i=1;i<=m;i++){
        tmp+=(sumv[r[i]]-sumv[l[i]-1])*(sumn[r[i]]-sumn[l[i]-1]);
    }
    if(ans>abs(s-tmp))ans=abs(s-tmp);
    if(s>tmp)return true;
    return false;
}
int main(){
    read(n),read(m),read(s);
    for(int i=1;i<=n;i++){
        read(w[i]),read(v[i]);
        if(w[i]>ri)ri=w[i];
    } 
    ri++;
    for(int i=1;i<=m;i++){
        read(l[i]),read(r[i]);
    }
    le=0;
    while(le<ri){
        mid=le+ri>>1;
        if(!check(mid))le=mid+1;
        else ri=mid;
    }
    printf("%lld",ans);
    
    return 0;
}

二分+一点点的优化

注意数据是比较大的,最大的检测值之和为2*10^6*10^6*2*10^6...

最好将不是循环变量的类型都弄成int64;

还有当算检测值之和时当>=s*3,就直接退出,因为这足以说明不可能为更优

二分+前缀和模拟

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
long long n,m,s,l,r,mid,t,ans=1e13,y=0;
long long w[200001],v[200001],ll[200001];
long longrr[200001],x[200001],vv[200001];
bool check(int mid)
{
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=mid)
        {
            x[i]=x[i-1]+1;
            v[i]=v[i-1]+vv[i];
        }
        else
        {
            x[i]=x[i-1];
            v[i]=v[i-1];
        }
    }
    for(int i=1;i<=m;i++)
    {
        y+=(x[rr[i]]-x[ll[i]-1])*(v[rr[i]]-v[ll[i]-1]);
    }
    t=s-y;
    y=0;
    if(t>0)
    {
        return true;
    }
    else if(t<0)
    {
        return false;
    }
    else
    {
        printf("0");
        exit(0);
    }
}
int main()
{
    scanf("%I64d%I64d%I64d",&n,&m,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&w[i],&vv[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&ll[i],&rr[i]);
    }
    l=0;
    r=1e6+1;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid)==true)
        {
            if(labs(t)<ans)
            {
                ans=labs(t);
            }
            r=mid-1;
        }
        else
        {
            if(labs(t)<ans)
            {
                ans=labs(t);
            }
            l=mid+1;
        }
    }
    printf("%lld",ans);
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
int w[200000+1];
int v[200000+1];
int le[200000+1];
int ri[200000+1];
double s;
double s_w[200000+1];
double s_v[200000+1];

double calc_1(int x)
{
    memset(s_w,0,sizeof(s_w));
    memset(s_v,0,sizeof(s_v));
    for (int i=1;i<=n;i++)
    {
        s_w[i]=s_w[i-1]+((w[i]>=x)?1:0);
        s_v[i]=s_v[i-1]+((w[i]>=x)?v[i]:0);
    }
    double ans=0;
    for (int i=1;i<=m;i++)
        ans+=((s_w[ri[i]]-s_w[le[i]-1])*(s_v[ri[i]]-s_v[le[i]-1]));
    return ans;
}

int main()
{
    while (~scanf("%d%d%lf",&n,&m,&s))
    {
        int l=oo_max,r=oo_min;
        memset(w,0,sizeof(w));
        memset(v,0,sizeof(v));
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&w[i],&v[i]);
            l=min(l,w[i]),r=max(r,w[i]);
        }
        memset(le,0,sizeof(le));
        memset(ri,0,sizeof(ri));
        for (int i=1;i<=m;i++)
            scanf("%d%d",&le[i],&ri[i]);
        while (r-l>1)
        {
            int mid=(l+r)/2;
            double sum=calc_1(mid);
            if (s<sum)
                l=mid;
            else
                r=mid;
        }
        double ans_l=fabs(s-calc_1(l)),ans_r=fabs(s-calc_1(r));
        double ans=min(ans_l,ans_r);
        printf("%.0lf\n",ans);
    }
}

树状数组计算检验二分结果
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;

const int N=2e5+5;
ll n,m,s;
ll sz[N][2];
ll L[N],R[N];
ll w[N],v[N];

void add(int x,ll a,int kind){
for(int i=x;i<=n;i+=i&-i){
sz[i][kind]+=a;
}
}

ll qiu(ll x,int kind){
ll cnt=0;
for(int i=x;i;i-=i&-i){
cnt+=sz[i][kind];
}
return cnt;
}

ll check(ll x){
memset(sz,0,sizeof(sz));
for(int i=1;i<=n;i++){
if(w[i]>=x) add(i,(ll)v[i],1),add(i,(ll)1,0);
}
ll ans=0;
for(int i=1;i<=m;i++){
int l=L[i],r=R[i];
ans+=(qiu(r,0)-qiu(l-1,0))*(qiu(r,1)-qiu(l-1,1));
}
return ans;
}

int main()
{
// freopen("test.in","r",stdin);
ll maxn=-1;
scanf("%lld%lld%lld",&n,&m,&s);
for(int i=1;i<=n;i++) scanf("%lld%lld",&w[i],&v[i]),maxn=max(maxn,w[i]);
for(int i=1;i<=m;i++){
scanf("%lld%lld",&L[i],&R[i]);
}
// for(int i=0;i<=maxn;i++) printf("%lld\n",check(i));
ll l=-1,r=maxn;
ll last=0x3f3f3f3f3f3f3f3f;
while(l<r){
ll mid=l+r>>1;
ll tt=check(mid),kk=fabs(tt-s);
last=min(last,kk);
if(tt<=s) r=mid;
else l=mid+1;
}
printf("%lld",last);
return 0;
}

二分，在求每次的W时先把整体算出来

#include<cstdio>
#include<iostream>
using namespace std;
long long n,m,w[200005],v[200005],L[200005],R[200005],sum[200005]={0},sumv[200005]={0};
long long s,Y,minin=0x3f3f3f3f;
long long lef=0x3f3f3f3f,righ=-1;
long long asb(long long a){
if(a>=0) return a;
return -a;
}
long long check(long long W){
long long temp=0,i;
for(i=1;i<=n;i++){
if(w[i]>=W) {
sum[i]=sum[i-1]+1;
sumv[i]=sumv[i-1]+v[i];
}
else{
sum[i]=sum[i-1];
sumv[i]=sumv[i-1];
}
}
for(i=1;i<=m;i++){
temp+=(sum[R[i]]-sum[L[i]-1])*(sumv[R[i]]-sumv[L[i]-1]);
}
return temp;
}
int main(){
//freopen("qc20.in","r",stdin);
long long i,j;
scanf("%lld %lld %lld",&n,&m,&s);
for(i=1;i<=n;i++){
scanf("%lld %lld",&w[i],&v[i]);
if(lef>w[i]) lef=w[i];
if(righ<w[i]) righ=w[i];
}
for(i=1;i<=m;i++){
scanf("%lld %lld",&L[i],&R[i]);
}
minin=asb(check(righ)-s);
while(1){
if(righ-lef==1){
long long t1=check(lef);
long long t2=check(righ);
t1=asb(t1-s);t2=asb(t2-s);
if(t1>t2) minin=t2;
else{
minin=t1;
}
break;
}
else{
long long mid=(lef+righ)>>1;
long long W=mid;
Y=0;
Y=check(W);
if(minin>asb(s-Y)) minin=asb(s-Y);
if(Y==s){
printf("0\n");
}
if(Y>s) lef=mid;
if(Y<s) righ=mid;
}
}
printf("%lld\n",minin);
return 0;
}


一眼二分题
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 200000 + 10;
const int maxw = 1000000 + 10;
typedef long long LL;

int n, m;
LL S;
int l[maxn], r[maxn];
int v[maxn], w[maxn];
LL pre_cnt[maxn], pre_sum[maxn];

LL clt (int W) {
LL ret = 0;

pre_cnt[0] = pre_sum[0] = 0;
for (int i = 1; i <= n; i++) {
pre_cnt[i] = pre_cnt[i-1];
pre_sum[i] = pre_sum[i-1];
if (w[i] >= W) {
pre_cnt[i]++;
pre_sum[i] += v[i];
}
}

for (int i = 0; i < m; i++)
ret += (pre_cnt[r[i]]-pre_cnt[l[i]-1]) * (pre_sum[r[i]]-pre_sum[l[i]-1]);

return ret;
}

int main ()
{
// freopen("in.txt", "r", stdin);
cin >> n >> m >> S;
for (int i = 1; i <= n; i++)
scanf("%d%d", &w[i], &v[i]);
for (int i = 0; i < m; i++)
scanf("%d%d", &l[i], &r[i]);

int L = *min_element(w+1, w+n+1);
int R = *max_element(w+1, w+n+1);
while (R - L > 1) {
int M = L + (R-L)/2;
if (clt(M) > S) L = M; else R = M;
}
LL ans = min(abs(clt(L)-S), abs(clt(R)-S));
cout << ans;
return 0;
}
```

超时了一次，竟然是因为c++的流太慢了（逃，也算是大意了吧最后一个点慢了三十多毫秒。一关闭同步就瞬间提到600ms；
这道题是经典的二分+前缀和啦~
二分思路应该是容易想到的，寻找w值
不断二分更新
关键就是怎样判断二分后继续二分范围
即二分依据
附上代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;

long long s[200004],sv[200004];
struct node
{
long long w,v;
}a[200004];
struct tion
{
long long x,y;
}b[200004];
long long n,m,S;

void work(long long r)
{
s[0]=sv[0]=0ll;
for(long long i=1;i<=n;i++)
if(a[i].w>=r)
s[i]=s[i-1]+1,sv[i]=sv[i-1]+a[i].v;
else
s[i]=s[i-1],sv[i]=sv[i-1];
}

long long cal(long long r)
{
long long ans=0ll;
for(long long i=1;i<=m;i++)
ans+=(s[b[i].y]-s[b[i].x-1])*(sv[b[i].y]-sv[b[i].x-1]);
return ans;
}

int main()
{
ios::sync_with_stdio(false);
long long start=0ll,end=0ll;
cin>>n>>m>>S;
for(int i=1;i<=n;i++)
{cin>>a[i].w>>a[i].v;
end=max(end,a[i].w);}
for(int i=1;i<=m;i++)
cin>>b[i].x>>b[i].y;
long long ans=9223372036854775807ll;
while(start<=end)
{
long long mid=(start+end)>>1;
work(mid);

long long t=cal(mid);
if(abs(t-S)<ans)
ans=abs(t-S);
if(ans==0)
break;
if(S<t)
start=mid+1;
else
end=mid-1;
}
cout<<ans<<endl;
return 0;
}

Powder原著

语文数学不好是硬伤。。。。
\(\sum_{j} 1\)不是区间大小，而是区间中满足条件的数的个数。。
我还是太渣QwQ。。

其实每个区间的检验值Yi就是区间内质量大于W的个数×它们的价值之和。
所以W和s有着单调的关系，预处理+二分，代码写的有点难看。。（数据有点大）
~~~
#include <cstdio>
const int INF=0x3f3f3f3f;
long long n,m,s,w[200005],v[200005],l[200005],r[200005],sum[200005],sumv[200005];
long long w_max=-1,w_min=INF;
long long best_w,dis=INF;
long long int test(long long W){
long long int Y=0;
for(int i=1;i<=n;i++)
if(w[i]>=W){
sum[i]=sum[i-1]+1;
sumv[i]=sumv[i-1]+v[i];
}
else{
sum[i]=sum[i-1];
sumv[i]=sumv[i-1];
}
for(int j=1;j<=m;j++)
Y+=(sum[r[j]]-sum[l[j]-1])*(sumv[r[j]]-sumv[l[j]-1]);
return Y;
}
int main(){
//freopen("input.txt","r",stdin);
scanf("%lld%lld%lld",&n,&m,&s);
for(int i=1;i<=n;i++){
scanf("%lld%lld",w+i,v+i);
if(w[i]>w_max)w_max=w[i];
if(w[i]<w_min)w_min=w[i];
}
w_min--;w_max++;
for(int i=1;i<=m;i++){
scanf("%lld%lld",l+i,r+i);
}
bool flag=true;
long long int s_max=test(w_min);
long long int s_min=test(w_max);
if(s_min>s){
flag=false;
dis=s_min-s;
}
if(s_max<s){
flag=false;
dis=s-s_max;
}
while(flag){
if(w_max-w_min<=1){
long long int t1=s-test(w_max);
long long int t2=s-test(w_min);
if(t1<0)t1=-t1;
if(t2<0)t2=-t2;
if(t1<t2) dis=t1;
else dis=t2;
break;
}
long long int W=(w_min+w_max)>>1;
long long int Y=test(W);
if(Y>s)w_min=W;
else w_max=W;
}
printf("%lld\n",dis);
return 0;
}

附：最后一个测试数据n=m=200000 s=9580200000

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
int n,m;
long long S;
long long sum[200010];
int w[200010],v[200010];
int suma[200010];
int ma=0;
long long ans=0;
int li[200010],ri[200010];
long long ok1=4611686018427387904;
long long ok2=4611686018427387904;

bool judge(int W)
{
ans=0;
memset(suma,0,sizeof(suma));
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
{
suma[i]=suma[i-1];
sum[i]=sum[i-1];
if(w[i]>=W){
suma[i]++;
sum[i]+=v[i];
}
}
for(int i=1;i<=m;i++){
ans+=(long long)(sum[ri[i]]-sum[li[i]-1])*(suma[ri[i]]-suma[li[i]-1]);
}
if(ans-S>0){
if(ans-S<ok1) ok1=ans-S;
return 0;
}
if(S-ans<ok2) ok2=S-ans;
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%lld",&S);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&v[i]);
ma=max(ma,v[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&li[i],&ri[i]);
}
int l=1,r=ma+1;
while(l<r){
int mid=(l+r)>>1;
if(!judge(mid)){
l=mid+1;
}
else {
r=mid;
}
}
if(ok1>ok2) cout<<ok2<<endl;
else cout<<ok1<<endl;
return 0;
}

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int MAXN = 200000 + 10;

long long n, m, s, w[MAXN], v[MAXN], l[MAXN], r[MAXN], bri[MAXN], num[MAXN], f[MAXN];

long long check(int x){
long long ans = 0;
for(int i=1; i<=n; i++){
if(w[i] >= x){
f[i] = f[i-1] + v[i];
num[i] = num[i-1] + 1;
}
else{
f[i] = f[i-1];
num[i] = num[i-1];
}
}
for(int i=1; i<=m; i++)
ans += (f[r[i]] - f[l[i] - 1]) * (num[r[i]] - num[l[i] - 1]);
return s - ans;
}

long long find(int s, int t){
if(s == t)
return abs(check(s));
long long mid = (s + t) / 2;
long long qiao = check(bri[mid]);
long long ans = abs(qiao);
if(qiao > 0)
ans = min(find(s, mid), ans);
else if(qiao < 0)
ans = min(find(mid+1, t), ans);
return ans;
}

int main()
{
scanf("%I64d%I64d%I64d", &n, &m, &s);
for(int i=1; i<=n; i++){
scanf("%I64d%I64d", &w[i], &v[i]);
bri[i] = w[i];
}
sort(&bri[1], &bri[1]+n);
for(int i=1; i<=m; i++)
scanf("%I64d%I64d", &l[i], &r[i]);

long long ans = find(1, n);
printf("%I64d", ans);
return 0;
}
二分答案 + long long

program p1740;
var
ans,s,tot1,tot2:int64;
i,j,l,r,mid,k,n,m,t,max:longint;
a,b,w,v,d:array[1..300000]of longint;
e:array[1..300000]of int64;
c:array[1..300000]of boolean;
begin
ans:=1000000000000000;
readln(n,m,s);
for i:=1 to n do begin readln(w[i],v[i]);
if v[i]>max then max:=v[i];end;
for i:=1 to m do readln(a[i],b[i]);
l:=1; r:=max; mid:=(l+r)shr 1;
repeat
tot2:=0;
fillchar(c,sizeof(c),false);
fillchar(d,sizeof(d),0);
fillchar(e,sizeof(e),0);
for i:=1 to n do
if w[i]>=mid then c[i]:=true;
for i:=1 to n do if c[i] then
begin d[i]:=d[i-1]+1;e[i]:=e[i-1]+v[i];end
else begin d[i]:=d[i-1];e[i]:=e[i-1];end;
for i:=1 to m do
tot2:=tot2+(d[b[i]]-d[a[i]-1])*(e[b[i]]-e[a[i]-1]);
if abs(tot2-s)<ans then ans:=abs(tot2-s);
if tot2<s then begin r:=mid-1;mid:=(l+r)shr 1;end;
if tot2>s then begin l:=mid+1;mid:=(l+r)shr 1;end;
if tot2=s then begin writeln(0);halt;end;
until r<l;
writeln(ans);
end.

1：给ans赋值成1 shl 32 40分
2：用了while循环 65分
3： AC

二分答案然后前缀和计算检验值。

var
n,m,s,i,mid,t:longint;
minans,tt,ss:int64;
w,v,l,r,sum,tot:Array[0..200000]of int64;
function check(mid:longint):int64;
var i:longint;
begin
for i:=1 to n do
if w[i]>=mid then begin tot[i]:=tot[i-1]+1; sum[i]:=sum[i-1]+v[i]; end
else begin tot[i]:=tot[i-1]; sum[i]:=sum[i-1]; end;
check:=0;
for i:=1 to m do
inc(check,(tot[r[i]]-tot[l[i]-1])*(sum[r[i]]-sum[l[i]-1]));
end;
begin
assign(input,'qc.in');
assign(output,'qc.out');
reset(input); rewrite(output);
readln(n,m,ss);
for i:=1 to n do readln(w[i],v[i]);
for i:=1 to m do readln(l[i],r[i]);
s:=0; t:=1000000; minans:=1<<62;
while s<t do
begin
mid:=(s+t)>>1;
tt:=check(mid);
if abs(ss-tt)<minans then minans:=abs(ss-tt);
if tt<ss then t:=mid-1 else s:=mid+1;
end;
tt:=check(s);
if abs(ss-tt)<minans then minans:=abs(ss-tt);
writeln(minans);
close(input); close(output);
end.

=.= 忘了int64
Var n,m,i,j:longint;
s,ans,left,right,mid:int64;
w,v,f,sum,l,r:array[0..200000] of longint;
Function min(a,b:int64):int64;
Begin
If a<b then exit(a) else exit(b);
End;
Procedure inity(minw:longint);
Var i:longint;
Begin
fillchar(f,sizeof(f),0);
fillchar(sum,sizeof(sum),0);
For i:=1 to n do
Begin
f[i]:=f[i-1];
sum[i]:=sum[i-1];
If w[i]>=minw then
Begin
inc(f[i]);
sum[i]:=sum[i]+v[i];
End;
End;
End;
Procedure init;
Var i,j:longint;
Begin
assign(input,'qc.in');
reset(input);
Readln(n,m,s);
For i:=1 to n do readln(w[i],v[i]);
For i:=1 to m do readln(l[i],r[i]);
End;
Function work(minw:longint):int64;
Var i,j:longint;
y:int64;
Begin
y:=0;
inity(minw);
For i:=1 to m do
y:=y+(f[r[i]]-f[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
work:=y;
End;
Procedure main;
Var i:longint;
Begin
left:=1; right:=1000000000;
while left+1<right do
begin
mid:=(left+right)div 2;
ans:=work(mid);
if ans>s then left:=mid
else right:=mid;
end;
writeln(min(abs(work(right)-s),abs(work(left)-s)));
End;
Begin
init;
main;
End.

var i,j,l,n,m:longint;
r,s,mid,ans,y:int64;
legal,sum,w,v:array[0..300000] of int64;
left,right:array[0..300000] of longint;

procedure setlegal(ww:longint);
var i,j:longint;
begin
for i:=1 to n do if w[i]>=ww then legal[i]:=legal[i-1]+1 else legal[i]:=legal[i-1];
end;

procedure setsum(ww:longint);
var i,j:longint;
begin
for i:=1 to n do if w[i]>=ww then sum[i]:=sum[i-1]+v[i] else sum[i]:=sum[i-1];
end;

begin
read(n,m,s);
for i:=1 to n do begin read(w[i],v[i]); if w[i]>r then r:=w[i];end;
for i:=1 to m do read(left[i],right[i]);
ans:=maxlongint*100;
l:=1;
while l<=r do
begin
mid:=(l+r)>>1;
setlegal(mid);
setsum(mid);
y:=0;
for i:=1 to m do
y:=y+(legal[right[i]]-legal[left[i]-1])*(sum[right[i]]-sum[left[i]-1]);
if ans>abs(y-s) then ans:=abs(y-s);
if y>s then l:=mid+1;
if y<s then r:=mid-1;
if l+1=r then break;
if y=s then break;
end;
writeln(ans);
end.

program happy;

var m,n,i,x,ll,rr,mm,max:longint;

    w,v,l,r:array[0..200100]of longint;

    ans,s,y:int64;

    t,vv:array[0..200100]of int64; //用数组计数避免重复计算

procedure tryy(k:longint);

var i,j:longint;

begin

 y:=0;

 for i:=1 to n do

 begin

  t[i]:=t;vv[i]:=vv;

  if w[i]>=k then

  begin

   t[i]:=t[i]+1;vv[i]:=vv[i]+v[i];

  end;

 end;

 for i:=1 to m do

 y:=y+(t[r[i]]-t[l[i]-1])*(vv[r[i]]-vv[l[i]-1]);

end;

begin

 readln(n,m,s);

 max:=0;

 for i:=1 to n do

 begin

  readln(w[i],v[i]);

  if w[i]>max then max:=w[i];

 end;

 for i:=1 to m do readln(l[i],r[i]);

 ans:=10000000000000000;

 ll:=0; rr:=max;

 repeat

  mm:=(ll+rr)shr 1;      //二分答案

  tryy(mm);

  if abs(y-s)

test

var

w,v,a,b,l,r:array[0..200000]of longint;

c:array[0..200000]of int64;

n,m,i,st,mid,en:longint;

k,uu:int64;

function min(x,y:int64):int64;

begin

if x=k then st:=mid+1 else en:=mid;

end;

if st=1 then writeln(k-deal(a[1],2))

else if deal(a[st],2)>=k then writeln(deal(a[st],2)-k)

else writeln(min(k-deal(a[st],2),deal(a[st-1],2)-k));

close(input);

close(output);

end.