1 #include<bits/stdc++.h>

 2 using namespace std;

 3 typedef long long LL;

 4

 5 namespace IO{

 6     inline int read(){

 7         int x=0,f=1; char ch=getchar();

 8         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

 9         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

10         return x*f;

11     }

12     inline void write(int x,char sp){

13         char ch[20]; int len=0;

14         if(x<0){ putchar('-'); x=~x+1; }

15         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

16         for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

17     }

18 } using namespace IO;

19

20 const int NN=1<<18,p=1e9+7,inv=5e8+4;

21 LL k,ans,res,U,v[NN];

22

23 signed main(){

24     k=read(); ans=read(); U=(1<<k)-1;

25     for(int i=0;i<=U;i++) v[i]=read();

26     for(int i=0;i<=U;i++) (res+=abs(v[i]-v[ans]))%=p;

27     for(int i=1;i<=k;i++) (res*=inv)%=p;

28     write(res,'\n');

29     return 0;

30 }

 1 #include<bits/stdc++.h>

 2 #define int long long

 3 #define rin register signed

 4 using namespace std;

 5

 6 namespace IO{

 7     inline int read(){

 8         int x=0,f=1; char ch=getchar();

 9         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

10         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

11         return x*f;

12     }

13     inline void write(int x,char sp){

14         char ch[20]; int len=0;

15         if(x<0){ putchar('-'); x=~x+1; }

16         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

17         for(rin i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

18     }

19 } using namespace IO;

20

21 const int NN=1e5+5;

22 int n,a[NN],pre[NN],ans;

23

24 signed main(){

25     n=read();

26     for(rin i=1;i<=n;i++) ans+=a[i]=read();

27     sort(a+1,a+n+1);

28     for(rin i=1;i<=n;i++){

29         int tmp=a[i]+1>>1;

30         if(tmp>a[i-1]) ans-=tmp-a[i-1]-1;

31         a[i]+=a[i-1];

32     }

33     write(ans,'\n');

34     return 0;

35 }

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3

 4 namespace IO{

 5     inline int read(){

 6         int x=0,f=1; char ch=getchar();

 7         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

 8         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

 9         return x*f;

10     }

11     inline void write(int x,char sp){

12         char ch[20]; int len=0;

13         if(x<0){ putchar('-'); x=~x+1; }

14         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

15         for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

16     }

17 } using namespace IO;

18

19 const int NN=1e5+5;

20 int n,m,a[NN],bel[NN],ans[NN],lb[NN],rb[NN],len;

21 struct ask{ int l,r,id; }q[NN];

22 struct node{ int typ,pos,val; }stk[NN];

23 inline bool cmp(ask x,ask y){ return bel[x.l]==bel[y.l]?x.r<y.r:bel[x.l]<bel[y.l]; }

24

25 signed main(){

26     n=read(); m=read(); len=sqrt(n);

27     for(int i=1;i<=n;i++) a[i]=read(), bel[i]=i/len+1;

28     for(int i=1;i<=m;i++)

29         q[i].l=read(), q[i].r=read(), q[i].id=i;

30     sort(q+1,q+m+1,cmp);

31     for(int i=1,j=1;j<=bel[n];j++){

32         int r=j*len,sum=0;

33         for(int k=1;k<=n;k++) lb[k]=rb[k]=0;

34         for(;bel[q[i].l]==j;i++){

35             while(r<q[i].r){

36                 r++;

37                 lb[a[r]]=lb[a[r]-1]+1;

38                 rb[a[r]]=rb[a[r]+1]+1;

39                 int tmp=lb[a[r]]+rb[a[r]]-1;

40                 sum=max(sum,tmp);

41                 lb[a[r]+rb[a[r]]-1]=tmp;

42                 rb[a[r]-lb[a[r]]+1]=tmp;

43             }

44             int res=sum,top=0;

45             for(int l=q[i].l;l<=min(q[i].r,len*bel[q[i].l]);l++){

46                 lb[a[l]]=lb[a[l]-1]+1;

47                 rb[a[l]]=rb[a[l]+1]+1;

48                 stk[++top]=(node){0,a[l]+rb[a[l]]-1,lb[a[l]+rb[a[l]]-1]};

49                 stk[++top]=(node){1,a[l]-lb[a[l]]+1,rb[a[l]-lb[a[l]]+1]};

50                 int tmp=lb[a[l]]+rb[a[l]]-1;

51                 res=max(res,tmp);

52                 lb[a[l]+rb[a[l]]-1]=tmp;

53                 rb[a[l]-lb[a[l]]+1]=tmp;

54             }

55             ans[q[i].id]=res;

56             while(top){

57                 if(!stk[top].typ) lb[stk[top].pos]=stk[top].val;

58                 else rb[stk[top].pos]=stk[top].val;

59                 top--;

60             }

61             for(int l=q[i].l;l<=min(q[i].r,len*bel[q[i].l]);l++)

62                 lb[a[l]]=rb[a[l]]=0;

63         }

64     }

65     for(int i=1;i<=m;i++) write(ans[i],'\n');

66     return 0;

67 }