萌新求助。自闭了

回复帖子

@永远的呱太 2019-12-16 22:09 回复

50分
和一个满分的题解对拍之后就【如图】了,极其自闭。

#include<bits/stdc++.h>
using namespace std;
const int N=400005;
struct line{int x,y,w,fla,id;bool operator<(line a) {return y==a.y?w>a.w:y<a.y;}}a[N],b[N];
struct tree{int max,fla;void clear() {max=fla=0;}}t[N<<2];
int q,n,w,h,le[N],ri[N],ans,tot,cnt;
inline bool cmp(line a,line b) {return a.x<b.x;}
inline void allc(int x,int l,int r,int c) {if(c) {t[x].max+=c,t[x].fla+=c;}}
inline void down(int x,int l,int r) {allc(x<<1,l,(l+r)>>1,t[x].fla),allc(x<<1|1,((l+r)>>1)+1,r,t[x].fla),t[x].fla=0;}
inline void chang(int x,int l,int r,int dl,int dr,int dc)
{
    if(l>dr||dl>r);else if(dl<=l&&r<=dr) down(x,l,r),allc(x,l,r,dc);
    else down(x,l,r),chang(x<<1,l,(l+r)>>1,dl,dr,dc),chang(x<<1|1,((l+r)>>1)+1,r,dl,dr,dc),t[x].max=max(t[x<<1].max,t[x<<1|1].max);
}
inline int query(int x,int l,int r,int dl,int dr)
{
    if(l>dr||dl>r) return 0;else if(dl<=l&&r<=dr) return t[x].max;
    return down(x,l,r),max(query(x<<1,l,(l+r)>>1,dl,dr),query(x<<1|1,((l+r)>>1)+1,r,dl,dr));
}
signed main()
{
//  freopen("__tmp.in","r",stdin);
    for(scanf("%d",&q);q--;)
    {
        scanf("%d%d%d",&n,&w,&h),ans=0;
        for(int i=0;i<(N<<2);i++) t[i].clear();
        for(int i=1,x,y,wei;i<=n;i++)
        {
            scanf("%d%d%d",&x,&y,&wei);
            if(wei>0) a[i]=(line){x,y,wei,0,i},b[i]=(line){0,y,wei,0,i};
        }
        tot=n;
        for(int i=1;i<=n;i++) a[++tot]=(line){a[i].x+w-1,0,0,1,i};
        sort(a+1,a+tot+1,cmp),cnt=0;
        for(int i=1,t=0;i<=tot;i++)
        {
            if(a[i].x==a[i-1].x&&i!=1) t=cnt;else t=++cnt;
            if(!a[i].fla) le[a[i].id]=t;else ri[a[i].id]=t;
        }
        tot=n;
        for(int i=1;i<=n;i++) b[++tot]=(line){0,b[i].y+h-1,-b[i].w,0,b[i].id};
        sort(b+1,b+tot+1);
        for(int i=1;i<=tot;i++)
        {
            if(b[i].w>0) ans=max(ans,b[i].w+query(1,1,cnt,le[b[i].id],ri[b[i].id]));
            chang(1,1,cnt,le[b[i].id],ri[b[i].id],b[i].w);
        }
        printf("%d\n",ans);
    }
    return 0;
}

下:数据生成器。

#include<bits/stdc++.h>
#define ll long long
using namespace  std;
const ll Max=50005;
const ll T=10,M=10000,W=1000000,N=(1<<31);
ll t,n,m,a[Max];
ll rnd(ll a,ll t=0)
{
    for(int i=0;i<31;i++) t=t*2+rand()%2;
    if(a==0) return t;return t%a;
}
signed main()
{
    t=rnd(T);
    printf("%lld\n",t);
    while(t--)
    {
        n=rnd(M)+1;
        printf("%lld %lld %lld\n",n,rnd(W),rnd(W));
        for(ll i=1;i<=n;i++) printf("%lld %lld %lld\n",rnd(N),rnd(N),rnd(N)+1);
    }
    return 0;
}
@CYJian  舟学家 2020-01-08 08:39 回复 举报

@我不是箭毒蛙 生成器挂了。。。

int 类型的范围是 $[-2^{31}, 2^{31}-1]$,左移的时候 $1$ 是 int 类型,会爆掉。

const ll N = (1LL << 31)
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。