【悬赏关注】两份代码一份95一份100,有何区别?
  • 板块P4849 寻找宝藏
  • 楼主lzyqwq
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/3/8 23:04
  • 上次更新2023/10/23 22:09:21
查看原帖
【悬赏关注】两份代码一份95一份100,有何区别?
539211
lzyqwq楼主2023/3/8 23:04

95:

#include<bits/stdc++.h>
#define N 100005
#define ll long long
#define mod 998244353
using namespace std;
int n,lsh,tot,g[N],cnt,tmp,sum[N];
set<int>s;
map<int,int>mp;
ll ans,f[N],maxn[N];
struct node{
    bool pos1,pos2;
    int a,b,c,d,id;
    ll w;
}u[N],v[N],p[N],q[N];
bool cmp1(node x,node y){
    return x.a^y.a?x.a<y.a:x.b^y.b?x.b<y.b:x.c^y.c?x.c<y.c:x.d<y.d;
}
bool cmp2(node x,node y){
    return x.b^y.b?x.b<y.b:x.c^y.c?x.c<y.c:x.d^y.d?x.d<y.d:x.a<y.a;
}
bool cmp3(node x,node y){
    return x.c^y.c?x.c<y.c:x.d^y.d?x.d<y.d:x.a^y.a?x.a<y.a:x.b<y.b;
}
void insert(int x,ll k,int j){
    for(int i=x;i<=lsh;i+=i&-i){
        if(k>maxn[i]){
            maxn[i]=k;
            sum[i]=j;
        }else if(k==maxn[i]){
            sum[i]+=j;
            sum[i]%=mod;
        }
    }
}
pair<ll,int>query(int x){
    ll fi=0;
    int se=0;
    for(int i=x;i;i-=i&-i){
        if(maxn[i]>fi){
            fi=maxn[i];
            se=sum[i];
        }else if(maxn[i]==fi){
            se+=sum[i];
            se%=mod;
        }
    }
    return make_pair(fi,se);
}
void clear(int x){
    for(int i=x;i<=lsh;i+=i&-i){
        maxn[i]=sum[i]=0;
    }
}
void cdq2(int l,int r){
    if(l^r){
        int m=(l+r)>>1;
        cdq2(l,m);
        for(int i=l;i<=r;++i){
            q[i]=p[i];
            q[i].pos2=(i>m);
        }
        sort(q+l,q+r+1,cmp3);
        for(int i=l;i<=r;++i){
            if(q[i].pos1&&q[i].pos2){
                auto[fi,se]=query(q[i].d);
                if(fi+q[i].w>f[q[i].id]){
                    f[q[i].id]=fi+q[i].w;
                    g[q[i].id]=se;
                }else if(fi+q[i].w==f[q[i].id]){
                    g[q[i].id]+=se;
                    g[q[i].id]%=mod;
                }
            }else if(!q[i].pos1&&!q[i].pos2){
                insert(q[i].d,f[q[i].id],g[q[i].id]);
            }
        }
        for(int i=l;i<=r;++i){
            if(!q[i].pos1&&!q[i].pos2){
                clear(q[i].d);
            }
        }
        cdq2(m+1,r);
    }
}
void cdq1(int l,int r){
    if(l^r){
        int m=(l+r)>>1;
        cdq1(l,m);
        for(int i=l;i<=r;++i){
            p[i]=v[i];
            p[i].pos1=(i>m);
        }
        sort(p+l,p+r+1,cmp2);
        cdq2(l,r);
        cdq1(m+1,r);
    }
}
int main(){
    scanf("%d%d",&n,&tmp);
    for(int i=1;i<=n;++i){
        scanf("%d%d%d%d%lld",&u[i].a,&u[i].b,&u[i].c,&u[i].d,&u[i].w);
        s.insert(u[i].d);
    }
    for(int i:s){
        mp[i]=++lsh;
    }
    for(int i=1;i<=n;++i){
        u[i].d=mp[u[i].d];
    }
    sort(u+1,u+1+n,cmp1);
    for(int i=1;i<=n;++i){//去重
        if(!tot||u[i].a^v[tot].a||u[i].b^v[tot].d||u[i].c^v[tot].c||u[i].d^v[tot].d){
            v[++tot]=u[i];
            v[tot].id=tot;
        }else{
            v[tot].w+=u[i].w;
        }
    }
    for(int i=1;i<=tot;++i){
        f[v[i].id]=v[i].w;
        g[v[i].id]=1;
    }
    cdq1(1,tot);
    for(int i=1;i<=tot;++i){
        if(f[i]>ans){
            ans=f[i];
            cnt=g[i];
        }else if(f[i]==ans){
            cnt+=g[i];
            cnt%=mod;
        }
    }
    printf("%lld\n%d",ans,cnt);
}

100:

#include<bits/stdc++.h>
#define N 100005
#define ll long long
#define mod 998244353
using namespace std;
int n,lsh,tot=1,g[N],tmp,sum[N],cnt;
set<int>s;
map<int,int>mp;
ll ans,f[N],maxn[N];
struct node{
    bool pos1,pos2;
    int a,b,c,d,id;
    ll w;
}v[N],p[N],q[N];
bool cmp1(node x,node y){
    return x.a^y.a?x.a<y.a:x.b^y.b?x.b<y.b:x.c^y.c?x.c<y.c:x.d<y.d;
}
bool cmp2(node x,node y){
    return x.b^y.b?x.b<y.b:x.c^y.c?x.c<y.c:x.d^y.d?x.d<y.d:x.a<y.a;
}
bool cmp3(node x,node y){
    return x.c^y.c?x.c<y.c:x.d^y.d?x.d<y.d:x.a^y.a?x.a<y.a:x.b<y.b;
}
void insert(int x,ll k,int j){
    for(int i=x;i<=lsh;i+=i&-i){
        if(k>maxn[i]){
            maxn[i]=k;
            sum[i]=j;
        }else if(k==maxn[i]){
            sum[i]+=j;
            sum[i]%=mod;
        }
    }
}
pair<ll,int>query(int x){
    ll fi=0;
    int se=0;
    for(int i=x;i;i-=i&-i){
        if(maxn[i]>fi){
            fi=maxn[i];
            se=sum[i];
        }else if(maxn[i]==fi){
            se+=sum[i];
            se%=mod;
        }
    }
    return make_pair(fi,se);
}
void clear(int x){
    for(int i=x;i<=lsh;i+=i&-i){
        maxn[i]=sum[i]=0;
    }
}
void cdq2(int l,int r){
    if(l^r){
        int m=(l+r)>>1;
        cdq2(l,m);
        for(int i=l;i<=r;++i){
            q[i]=p[i];
            q[i].pos2=(i>m);
        }
        sort(q+l,q+r+1,cmp3);
        for(int i=l;i<=r;++i){
            if(q[i].pos1&&q[i].pos2){
                auto[fi,se]=query(q[i].d);
                if(fi+q[i].w>f[q[i].id]){
                    f[q[i].id]=fi+q[i].w;
                    g[q[i].id]=se;
                }else if(fi+q[i].w==f[q[i].id]){
                    g[q[i].id]+=se;
                    g[q[i].id]%=mod;
                }
            }else if(!q[i].pos1&&!q[i].pos2){
                insert(q[i].d,f[q[i].id],g[q[i].id]);
            }
        }
        for(int i=l;i<=r;++i){
            if(!q[i].pos1&&!q[i].pos2){
                clear(q[i].d);
            }
        }
        cdq2(m+1,r);
    }
}
void cdq1(int l,int r){
    if(l^r){
        int m=(l+r)>>1;
        cdq1(l,m);
        for(int i=l;i<=r;++i){
            p[i]=v[i];
            p[i].pos1=(i>m);
        }
        sort(p+l,p+r+1,cmp2);
        cdq2(l,r);
        cdq1(m+1,r);
    }
}
int main(){
    scanf("%d%d",&n,&tmp);
    for(int i=1;i<=n;++i){
        scanf("%d%d%d%d%lld",&v[i].a,&v[i].b,&v[i].c,&v[i].d,&v[i].w);
        s.insert(v[i].d);
    }
    for(int i:s){
        mp[i]=++lsh;
    }
    for(int i=1;i<=n;++i){
        v[i].d=mp[v[i].d];
    }
    sort(v+1,v+1+n,cmp1);
    for(int i=2;i<=n;++i){//去重
        if(v[i].a==v[tot].a&&v[i].b==v[tot].b&&v[i].c==v[tot].c&&v[i].d==v[tot].d){
            v[tot].w+=v[i].w;
        }else{
            v[++tot]=v[i];
        }
    }
    for(int i=1;i<=tot;++i){
        f[v[i].id=i]=v[i].w;
        g[i]=1;
    }
    cdq1(1,tot);
    for(int i=1;i<=tot;++i){
        if(f[i]>ans){
            ans=f[i];
            cnt=g[i];
        }else if(f[i]==ans){
            cnt+=g[i];
            cnt%=mod;
        }
    }
    printf("%lld\n%d",ans,cnt);
}

仅仅去重不一样,为何前者会 WA on 12?

蒟蒻真心求助,快哭了

2023/3/8 23:04
加载中...