社区讨论

WA #6 求助/ll

CF1788E Sum Over Zero参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lqgk3ngn
此快照首次捕获于
2023/12/22 19:36
2 年前
此快照最后确认于
2023/12/22 21:42
2 年前
查看原帖
一眼了然后 RT。
甚至玄学的达到过WA #8,但是发现这种玄学没法同时通过6和8。
就这么个题已经整一下午了,救命()
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+84;
int n,bun,f[maxn];
long long bu[maxn],sum[maxn];
inline int lowbit(register int x){
    return x&-x;
}
namespace Sherry_BiTre{
    int T[maxn];
    inline void Modify(int p,int val){
        while(p<=bun+1){
            T[p]=max(T[p],val);
            p+=lowbit(p);
        }
        return ;
    }
    inline int Query(int p){
        int res=-0x3f3f3f3f;
        while(p){
            res=max(res,T[p]);
            p-=lowbit(p);
        }
        return res;
    }
}
using namespace Sherry_BiTre;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&sum[i]);
        bu[i]=(sum[i]+=sum[i-1]);
    }
    sort(bu+1,bu+n+2);
    bun=unique(bu+1,bu+n+2)-bu-1;
    for(int i=1;i<=n;i++)
        sum[i]=lower_bound(bu+1,bu+bun+1,sum[i])-bu;
    memset(T,-0x3f,sizeof(T));
    T[lower_bound(bu+1,bu+bun+1,0)-bu]=0;
    for(int i=1;i<=n;i++)
        Modify(sum[i],(f[i]=max(f[i-1],Query(sum[i])+i))-i);
    printf("%d",f[n]);
    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...