52pts求调,玄学错误,复杂度nlogn
查看原帖
52pts求调,玄学错误,复杂度nlogn
978583
Kayisama楼主2024/10/20 12:36

RT,第14个至第最后一个测试点输出皆为1,前面全AC,感觉很玄学

代码如下:

#include <bits/stdc++.h>
using namespace std;
namespace MySpace{
    #ifdef ONLINE_JUDGE
    #define getchar getchar_unlocked
    #endif
    inline void read() {}
    template <typename T, typename... R>
    inline void read(T &x,R &... oth){
        x=0;T f=1;
        char c=getchar();
        while(c<'0' || c>'9') {
            if(c=='-') f=-1;
            c=getchar();
        }
        while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c&15),c=getchar();
        x*=f;
        read(oth...);
        return;
    }
}
using namespace MySpace;
//const int INF=0x66CCFF66;
#define int long long
const int mod=1e9+7;
const int maxn=2e5+5;
int n;
int m[maxn];
int a[maxn];
priority_queue<int,vector<int>,greater<int> > q;
int maxx=LLONG_MAX;
int ans,tot=1;
signed main(){
    read(n);
    for (int i=1;i<=n;i++) read(m[i]);
    for (int i=1;i<=n;i++) read(a[i]);
    for (int i=1;i<=n;i++){
        int l=a[i]-1,r=m[i]-a[i];
        q.push(min(l,r));
        maxx=min(maxx,max(l,r));
        tot<<=1ll;
    }
    int ptr=1;
    while (!q.empty() && ptr<=maxx){
        int t=q.top(); q.pop();
        t=min(t,maxx);
        ans+=tot*(t-ptr+1);
        ptr=t+1;tot>>=1ll;
        //printf("%d\n",ans);
    }
    ans+=max(maxx-ptr+1,0ll);
    printf("%lld\n",(ans+1)%mod);
    return 0;
}






求佬帮忙看看,拜托拜托QAQ

2024/10/20 12:36
加载中...