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_木源崔 好像确实。。。
不过前面的数据一点都没有计算散块感觉有点怪