QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#122937 | #1808. Efficient Partitioning | JerryBlack | Compile Error | / | / | C++14 | 3.6kb | 2023-07-11 15:20:19 | 2023-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]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [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