数据是否太水?

P2801 教主的魔法

Jr_Zlw @ 2021-03-13 11:39:43

接连发生各种sb错误竟然还能拿高分??

I. 调试代码忘删,80pt -_-

II. 统计散块答案时没算上标记,90pt -_-

#include<bits/stdc++.h>
#define rep(a,b,c) for(register int c=(a);c<=(b);++c) 
#define N 1000005
#define SN 1005
#define int long long
#define debug puts("aaaaa!");
using namespace std;
inline int read()
{
    int res=0;char ch=getchar();bool flag=0;
    while(ch<'0'||ch>'9'){if(ch=='-')flag=1;ch=getchar();}
    while(ch<='9'&&ch>='0')res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
    return flag?-res:res;
}
int n,m,block,sn;
int sum[SN],a[N],b[N],L[SN],R[SN],tag[SN];
inline int Cnt(int k,int des)
{
    int l=L[k],r=R[k],res=R[k]+1;
    while(l<=r){int mid=(l+r)>>1;(b[mid]+tag[k]<des)?l=mid+1:(r=mid-1,res=mid);}
    return R[k]-res+1;
}
inline void add(int l,int r,int val)
{
    rep(1,block,i)
    {
        if(R[i]<=r&&L[i]>=l){tag[i]+=val;continue;}
        else if(R[i]>=l&&R[i]<=r){rep(l,R[i],j)a[j]+=val;rep(L[i],R[i],j)b[j]=a[j];sort(b+L[i],b+R[i]+1);}
        else if(L[i]<=r&&L[i]>=l){rep(L[i],r,j)a[j]+=val;rep(L[i],R[i],j)b[j]=a[j];sort(b+L[i],b+R[i]+1);}
    }
}
inline void fnd(int l,int r,int c)
{
    int res=0;rep(1,block,i)
    {
        if(l<=L[i]&&R[i]<=r){res+=Cnt(i,c);continue;}
        else if(l<=R[i]&&R[i]<=r){rep(l,R[i],j)if(a[j]>=c)res++;cout<<res<<endl;}
        else if(l<=L[i]&&L[i]<=r){rep(L[i],r,j)if(a[j]>=c)res++;cout<<res<<endl;}
    }
    printf("%lld\n",res);
}

inline void setBlock()
{
    sn=sqrt(n);block=n/sn;if(n%sn)block++;
    rep(1,block,i)L[i]=(i-1)*sn+1,R[i]=i*sn;R[block]=n;
    rep(1,block,i)sort(b+L[i],b+R[i]+1);
}
signed main()
{
    n=read();m=read();rep(1,n,i)a[i]=b[i]=read();setBlock();
//  cout<<Cnt(1,4)<<endl;
    rep(1,m,i)
    {
        char ch;cin>>ch;
        int x=read(),y=read();
        switch(ch)
        {
            case 'M': add(x,y,read());break;
            case 'A': fnd(x,y,read());break;
        }
//      rep(1,5,i)cout<<a[i]<<' ';puts("");
//      rep(1,5,i)cout<<b[i]<<' ';puts("");
    }
    return 0;
}

看这份错漏百出的80pt代码,敢情只有最后两个n<6点会计算到散块

k该加强啦!


by Jr_Zlw @ 2021-03-13 11:43:26

违规紫杉


by MuYC @ 2021-03-13 11:44:12

你又没有 100pts ,所以数据不水。


by MuYC @ 2021-03-13 11:51:07

@Jr_zLiwen 我说你的错误做法过了没?


by MuYC @ 2021-03-13 11:51:39

@Jr_zLiwen 就算你的错误做法可以拿到80分,但是你就是没过,影响不大


by Jr_Zlw @ 2021-03-13 11:54:19

@Kac_木源崔 好像确实。。。

不过前面的数据一点都没有计算散块感觉有点怪


|