QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #647930 | #5069. Vacation | Kevin5307 | WA | 561ms | 199932kb | C++23 | 6.6kb | 2024-10-17 16:16:14 | 2024-10-17 16:16:20 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
ll a[500500];
class segt1
{
#define ls (x<<1)
#define rs (ls|1)
struct node
{
ll s,l,r,a;
node(){}
node(ll _s,ll _l,ll _r,ll _a):s(_s),l(_l),r(_r),a(_a){}
node(ll v):s(v),l(max(v,0ll)),r(max(v,0ll)),a(max(v,0ll)){}
const node operator +(const node &x){return node(s+x.s,max(l,x.l+s),max(r+x.s,x.r),max({x.a,a,r+x.l}));}
};
vector<node> segt;
public:
segt1(int s){init(s);}
segt1(){}
void init(int n){segt.resize(n<<2);for(auto &nd:segt)nd=node(0);}
void update(int x,int l,int r,int p,ll v)
{
if(l==r)
{
segt[x]=node(v);
return ;
}
int mid=(l+r)/2;
if(p<=mid)
update(ls,l,mid,p,v);
else
update(rs,mid+1,r,p,v);
segt[x]=segt[ls]+segt[rs];
}
node query(int x,int l,int r,int ql,int qr)
{
if(l==ql&&r==qr) return segt[x];
int mid=(l+r)/2;
if(qr<=mid)
return query(ls,l,mid,ql,qr);
if(ql>mid)
return query(rs,mid+1,r,ql,qr);
return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs
};
class segt2
{
#define ls (x<<1)
#define rs (ls|1)
ll segt[200200<<2];
public:
void update(int x,int l,int r,int p,ll v)
{
if(l==r)
{
segt[x]=v;
return ;
}
int mid=(l+r)/2;
if(p<=mid)
update(ls,l,mid,p,v);
else
update(rs,mid+1,r,p,v);
segt[x]=max(segt[ls],segt[rs]);
}
ll query(int x,int l,int r,int ql,int qr)
{
if(l==ql&&r==qr) return segt[x];
int mid=(l+r)/2;
if(qr<=mid) return query(ls,l,mid,ql,qr);
if(ql>mid) return query(rs,mid+1,r,ql,qr);
return max(query(ls,l,mid,ql,mid),query(rs,mid+1,r,mid+1,qr));
}
#undef ls
#undef rs
}s2,s3;
class segt3
{
#define ls (x<<1)
#define rs (ls|1)
struct node
{
ll ta,tb,a,b,s;
node(){}
node(ll _ta,ll _tb,ll _a,ll _b,ll _s):ta(_ta),tb(_tb),a(_a),b(_b),s(_s){}
const node operator +(const node &x){return node(0,0,max(a,x.a),max(b,x.b),max({s,x.s,b+x.a}));}
};
vector<node> segt;
public:
segt3(int s){init(s);}
segt3(){}
void init(int n){segt.resize(n<<2);}
void pushdown(int x,int l,int r)
{
if(l!=r)
{
segt[ls].ta+=segt[x].ta;
segt[rs].ta+=segt[x].ta;
segt[ls].tb+=segt[x].tb;
segt[rs].tb+=segt[x].tb;
}
segt[x].a+=segt[x].ta;
segt[x].b+=segt[x].tb;
segt[x].s+=segt[x].ta+segt[x].tb;
segt[x].ta=segt[x].tb=0;
}
void pushup(int x,int l,int r)
{
int mid=(l+r)/2;
pushdown(ls,l,mid);
pushdown(rs,mid+1,r);
segt[x]=segt[ls]+segt[rs];
}
void updateA(int x,int l,int r,int p,ll v)
{
pushdown(x,l,r);
if(l==r)
{
segt[x].a=v;
segt[x].s=segt[x].a+segt[x].b;
return ;
}
int mid=(l+r)/2;
if(p<=mid)
updateA(ls,l,mid,p,v);
else
updateA(rs,mid+1,r,p,v);
pushup(x,l,r);
}
void updateB(int x,int l,int r,int p,ll v)
{
pushdown(x,l,r);
if(l==r)
{
segt[x].b=v;
segt[x].s=segt[x].a+segt[x].b;
return ;
}
int mid=(l+r)/2;
if(p<=mid)
updateB(ls,l,mid,p,v);
else
updateB(rs,mid+1,r,p,v);
pushup(x,l,r);
}
void addA(int x,int l,int r,int ql,int qr,ll v)
{
pushdown(x,l,r);
if(ql<=l&&r<=qr)
{
segt[x].ta+=v;
return ;
}
int mid=(l+r)/2;
if(ql<=mid)
addA(ls,l,mid,ql,qr,v);
if(qr>mid)
addA(rs,mid+1,r,ql,qr,v);
pushup(x,l,r);
}
void addB(int x,int l,int r,int ql,int qr,ll v)
{
pushdown(x,l,r);
if(ql<=l&&r<=qr)
{
segt[x].tb+=v;
return ;
}
int mid=(l+r)/2;
if(ql<=mid)
addB(ls,l,mid,ql,qr,v);
if(qr>mid)
addB(rs,mid+1,r,ql,qr,v);
pushup(x,l,r);
}
node query(int x,int l,int r,int ql,int qr)
{
pushdown(x,l,r);
if(ql==l&&qr==r) return segt[x];
int mid=(l+r)/2;
if(qr<=mid) return query(ls,l,mid,ql,qr);
if(ql>mid) return query(rs,mid+1,r,ql,qr);
return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,q,c;
cin>>n>>q>>c;
for(int i=1;i<=n;i++)
cin>>a[i];
int m=(n+c-1)/c;
vector<segt1> s1(m,c+2);
vector<segt3> s4(m-1,c+2);
for(int i=0;i<m;i++)
for(int j=1;j<=c;j++)
s1[i].update(1,1,c,j,a[i*c+j]);
for(int i=0;i<m;i++)
s2.update(1,0,m-1,i,s1[i].query(1,1,c,1,c).a);
for(int i=0;i<m-1;i++)
{
s4[i].updateA(1,0,c,c,0);
s4[i].updateB(1,0,c,0,0);
ll sum=0;
for(int j=c;j;j--)
{
sum+=a[i*c+j];
s4[i].updateA(1,0,c,j-1,sum);
}
sum=0;
for(int j=1;j<=c;j++)
{
sum+=a[i*c+c+j];
s4[i].updateB(1,0,c,j,sum);
}
s3.update(1,0,m-2,i,s4[i].query(1,0,c,0,c).s);
}
while(q--)
{
int op;
cin>>op;
if(op==1)
{
int x;
ll y;
cin>>x>>y;
int b=(x-1)/c;
s1[b].update(1,1,c,x-b*c,y);
if(b<m-1)
s4[b].addA(1,0,c,0,x-b*c-1,y-a[x]);
if(b)
s4[b-1].addB(1,0,c,x-b*c,c,y-a[x]);
a[x]=y;
}
if(op==2)
{
int l,r;
cin>>l>>r;
int b1=(l-1)/c,b2=(r-1)/c;
ll ans=0;
if(b1+1<=b2-1)
ans=max(ans,s2.query(1,0,m-1,b1+1,b2-1));
if(b1+1<b2-1)
ans=max(ans,s3.query(1,0,m-2,b1+1,b2-2));
if(b1!=b2)
{
ans=max(ans,s1[b1].query(1,1,c,l-b1*c,c).a);
ans=max(ans,s1[b2].query(1,1,c,1,r-b2*c).a);
}
else
ans=max(ans,s1[b1].query(1,1,c,l-b1*c,r-b1*c).a);
if(b1+1==b2)
{
if(r-l+1<=c)
ans=max(ans,s4[b1].query(1,0,c,l-b1*c-1,c).a+s4[b1].query(1,0,c,0,r-b2*c).b);
else
{
ans=max(ans,s4[b1].query(1,0,c,r-b2*c,c).a+s4[b1].query(1,0,c,0,r-b2*c).b);
ans=max(ans,s4[b1].query(1,0,c,l-b1*c-1,c).a+s4[b1].query(1,0,c,0,l-b1*c-1).b);
ans=max(ans,s4[b1].query(1,0,c,l-b1*c-1,r-b2*c).s);
}
}
if(b1+1<b2)
{
ans=max(ans,s4[b1].query(1,0,c,l-b1*c-1,c).s);
ans=max(ans,s4[b1].query(1,0,c,l-b1*c-1,c).a+s4[b1].query(1,0,c,0,l-b1*c-1).b);
ans=max(ans,s4[b2-1].query(1,0,c,0,r-b2*c).s);
ans=max(ans,s4[b2-1].query(1,0,c,r-b2*c,c).a+s4[b2-1].query(1,0,c,0,r-b2*c).b);
}
cout<<ans<<'\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7668kb
input:
5 6 3 0 -5 -3 8 -3 2 3 5 1 2 5 2 1 5 1 4 -3 2 3 5 2 1 5
output:
8 10 0 5
result:
ok 4 number(s): "8 10 0 5"
Test #2:
score: -100
Wrong Answer
time: 561ms
memory: 199932kb
input:
200000 500000 1 387060158 961744470 37167782 737122872 -532977662 1604246 -30977399 871848791 444997246 454204578 -813187501 -660394286 448014171 -835115276 -631880452 887715308 258530352 805589560 -414653327 -156732249 -335096199 -80266237 367896009 738406627 -903652056 446120866 415658444 -1347916...
output:
999902477 999981999 999343404 999847372 999957587 998160312 999981999 999981999 999981999 999980061 999981999 999981999 999981999 999876122 999981999 999996602 999981999 999981999 999981999 999723649 999981999 999957587 999896087 999981999 999981999 999981999 999981999 999981999 999957587 999981999 ...
result:
wrong answer 622nd numbers differ - expected: '999932568', found: '999921057'