QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#122937#1808. Efficient PartitioningJerryBlackCompile Error//C++143.6kb2023-07-11 15:20:192023-07-11 15:20:20

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 15:20:20]
  • 评测
  • [2023-07-11 15:20:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define lowbit(x) (x&(-x))
const double eps=1e-12;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
int dcmp(double x){if(fabs(x)<eps)return 0;return x>0?1:-1;}

int P=998244353;
// int P=1e9+7;
namespace modint
{
    int norm(int x){if(x<0)x+=P;if(x>=P)x-=P;return x;}
    template<class T>
    T power(T a,ll n){T ans=1;while(n){if(n&1)ans=ans*a;a=a*a;n>>=1;}return ans;}
    struct Z
    {
        int x;
        Z(int x=0):x(norm(x)){}
        Z(ll x):x(norm(x%P)){}
        int val() const{return x;}
        Z operator-() const{return Z(norm(P-x));}
        Z inv() const{assert(x!=0);return power(*this,P-2);}
        Z&operator*=(const Z&rhs){x=(ll)x*rhs.x%P;return *this;}
        Z&operator+=(const Z&rhs){x=norm(x+rhs.x);return *this;}
        Z&operator-=(const Z&rhs){x=norm(x-rhs.x);return *this;}
        Z&operator/=(const Z&rhs){return *this*=rhs.inv();}
        friend Z operator*(const Z&lhs,const Z&rhs){Z res=lhs;res*=rhs;return res;}
        friend Z operator+(const Z&lhs,const Z&rhs){Z res=lhs;res+=rhs;return res;}
        friend Z operator-(const Z&lhs,const Z&rhs){Z res=lhs;res-=rhs;return res;}
        friend Z operator/(const Z&lhs,const Z&rhs){Z res=lhs;res/=rhs;return res;}
        friend istream&operator>>(istream&is,Z&a){ll v;is>>v;a=Z(v);return is;}
        friend ostream&operator<<(ostream&os,const Z&a){return os<<a.val();}
    };
}
using namespace modint;

#define int ll

int cnt;
int root;
int dp[200005];
struct node
{
    int a,b,ls,rs;
}tree[200005*400];
void update(int&p,int l,int r,int a,int b,int x)
{
    if(!p)
    {
        p=++cnt;
        tree[p].a=tree[p].b=-INF;
    }
    if(l==r)
    {
        tree[p].a=max(tree[p].a,a);
        tree[p].b=max(tree[p].b,b);
    }
    else
    {
        int mid=(l+r)>>1;
        if(x<=mid)update(tree[p].ls,l,mid,a,b,x);
        else update(tree[p].rs,mid+1,r,a,b,x);
        tree[p].a=max(tree[tree[p].ls].a,tree[tree[p].rs].a);
        tree[p].b=max(tree[tree[p].ls].b,tree[tree[p].rs].b);
    }
}
int query1(int p,int l,int r,int x,int y)
{
    if(!p)return -INF;
    if(x<=l&&r<=y)return tree[p].a;
    else
    {
        int mid=(l+r)>>1;
        int ans=-INF;
        if(x<=mid)ans=max(ans,query1(tree[p].ls,l,mid,x,y));
        if(mid<y)ans=max(ans,query1(tree[p].rs,mid+1,r,x,y));
        return ans;
    }
}
int query2(int p,int l,int r,int x,int y)
{
    if(!p)return -INF;
    if(x<=l&&r<=y)return tree[p].b;
    else
    {
        int mid=(l+r)>>1;
        int ans=-INF;
        if(x<=mid)ans=max(ans,query2(tree[p].ls,l,mid,x,y));
        if(mid<y)ans=max(ans,query2(tree[p].rs,mid+1,r,x,y));
        return ans;
    }
}

void solve()
{
    tree[0].a=-INF;
    tree[0].b=-INF;
    int n;
    cin>>n;
    vector<int>a(n+1),b(n+1),c(n+1),pre(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)cin>>c[i];
    int zero=1e18;
    int dif=0;
    int l=0,r=2e18;
    dp[0]=1e15;
    for(int i=1;i<=n;i++)
    {
        dif+=a[i]+c[i]-c[i-1];
        update(root,l,r,dp[i-1],b[i]+c[i-1]-pre[i-1],dp[i-1]-b[i]-c[i-1]+pre[i-1]+zero);
        dp[i]=max(query2(root,l,r,zero+dif,r)+dif,query1(root,l,r,l,zero+dif));
    }
    cout<<dp[n];
}

/*

*/

#undef int

int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    // cout<<fixed<<setprecision(15);



    // int _;cin>>_;while(_--)
    {
        solve();
    }
    return 0;
}

Details

/tmp/cc5FmEs1.o: in function `update(long long&, long long, long long, long long, long long, long long)':
answer.code:(.text+0x7f): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/cc5FmEs1.o
answer.code:(.text+0x8a): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/cc5FmEs1.o
/tmp/cc5FmEs1.o: in function `solve()':
answer.code:(.text+0x73a): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/cc5FmEs1.o
answer.code:(.text+0x756): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/cc5FmEs1.o
answer.code:(.text+0x7e7): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/cc5FmEs1.o
answer.code:(.text+0x801): relocation truncated to fit: R_X86_64_PC32 against symbol `root' defined in .bss section in /tmp/cc5FmEs1.o
answer.code:(.text+0x85f): relocation truncated to fit: R_X86_64_PC32 against symbol `root' defined in .bss section in /tmp/cc5FmEs1.o
answer.code:(.text+0xa7d): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/cc5FmEs1.o
answer.code:(.text+0xa84): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/cc5FmEs1.o
/tmp/cc5FmEs1.o: in function `_GLOBAL__sub_I__Z4dcmpd':
answer.code:(.text.startup+0x38): relocation truncated to fit: R_X86_64_PC32 against `.bss'
collect2: error: ld returned 1 exit status