fuck_karl

pcl5 · 2025-10-06 12:25:23 · 个人记录

#include <iostream>
#include <queue>
#include <map>
#define int long long
using namespace std;
struct node
{
    int l,r;
    int min()
    {
        if(l<r)return l;
        else return r;
    }
};
bool operator >(node a,node b)
{
    if(a.r-a.l!=b.r-b.l)return a.r-a.l>b.r-b.l;
    return a.l<b.l;
}
bool operator <(node a,node b)
{
    return !(a>b);
}
int n,m,a[1000005],ans;
map<int,node>pk;
map<int,int>cr;
priority_queue<node>q;
signed main()
{
    freopen("parking.in","r",stdin);
    freopen("parking.out","w",stdout);
    cin >> n >> m;
    for(int i = 1;i<=m;i++)scanf("%lld",&a[i]);
    q.push({0ll,n+1});
    for(int i = 1;i<=m;i++)
    {
        int l=q.top().l;
        int r=q.top().r;
        int mid=(l+r)>>1;
        q.pop();
        pk[i]={mid-l,r-mid};
        if(l==0)pk[i].l=1e18;
        if(r==n+1)pk[i].r=1e18;
        cr[mid]=i;
        pk[cr[l]].r=mid-l;
        pk[cr[r]].l=r-mid;
        if(r-mid>1)q.push({mid,r});
        if(mid-l>1)q.push({l,mid});
    }
    for(int i = 1;i<=m;i++)
    {
        ans+=max(0ll,a[i]-pk[i].min()+1);
    }
    cout << ans;
    return 0;
}