如果你30pts(警钟撅烂)
  • 板块P9519 pay
  • 楼主TMM233
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/19 01:14
  • 上次更新2023/11/19 10:07:17
查看原帖
如果你30pts(警钟撅烂)
807361
TMM233楼主2023/11/19 01:14

可能是你的二分区间开太大了,r开到了1e18就会让累计的sum爆炸,把r改成1e10就好了。

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll; 
typedef pair<ll,ll> p;
const int N=1e6+5;
ll a[N],b[N];ll n,m;
bool judge(ll x)
{
    ll pos=1;
    deque<ll> q,q2;
    ll sum=0,ct=0,ct2=0;
    for(ll i=1;i<=n;i++)
    {
        sum+=ct;
        sum-=ct2;
        while(pos<=m&&b[pos]<=i+x)
        q.push_back(b[pos]),sum+=x-(b[pos]-i),ct++,pos++;
        while(!q.empty()&&q.front()<=i)
        {
            q2.push_back(q.front());
            ct2++;
            ct--;
            q.pop_front();
        }
        while(!q2.empty()&&q2.front()<=i-x)
        {
            q2.pop_front();
            ct2--;
        }
        if(sum<a[i])
        return false;
    }
    return true;
}
signed main()
{
    IOS;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    cin>>b[i];
    sort(b+1,b+1+m);
    ll l=0,r=1e10,ans=0;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(judge(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else
        l=mid+1;
    }
    cout<<ans<<'\n';
}
2023/11/19 01:14
加载中...