Boxes

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>

#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,double> pid;

const int inf=0x3f3f3f3f;
const double eps=1e-8;

const int N=100010;

int n;
long double c;
long double w[N];

long double qpow(long double a,long long b){
    long double res=1;
    while(b){
        if(b&1)    res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}

int main(){
    scanf("%d%Lf",&n,&c);
    long double ans=0.0;
    for(int i=1;i<=n;i++){
        scanf("%Lf",&w[i]);
        ans=ans+(long double)w[i];
    }
    sort(w+1,w+n+1);
    n--;
    long double _ans=c;
    ll cnt=2;
    for(int i=n;i>=max(n-100,1);i--){
        _ans=_ans+(1.0-2.0/(long double)qpow(2,cnt))*w[i];
        cnt++;
    }
    for(int i=1;i<=max(n-100,1)-1;i++){
        _ans=_ans+1.0*w[i];
    }
    if(_ans-ans>eps)    _ans=ans;
    printf("%.16Lf",_ans);
}

King of Range

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>

#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,double> pid;

const int inf=0x3f3f3f3f;
const double eps=1e-8;

const int N=100010;

int n,m;
int k;
int a[N];
int q1[N],q2[N];
int hh1,hh2;
int tt1,tt2;
ll ans;

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    while(m--){
        scanf("%d",&k);
        hh1=hh2=0;
        tt1=tt2=-1;
        ans=1ll*n*(n+1)/2;
        for(int i=1,j=1;i<=n;i++){
            while(hh1<=tt1&&a[q1[tt1]]<a[i])    tt1--;
            while(hh2<=tt2&&a[q2[tt2]]>a[i])    tt2--;
            q1[++tt1]=i;
            q2[++tt2]=i;
            while(a[q1[hh1]]-a[q2[hh2]]>k){
                j++;
                if(q1[hh1]<j)    hh1++;
                if(q2[hh2]<j)    hh2++;
            }
            ans-=1ll*(i-j+2)*(i-j+1)/2;
            ans+=1ll*(i-j+1)*(i-j)/2;
        }
        printf("%lld\n",ans);
    }
}