Submission #573145

#TimeUsernameProblemLanguageResultExecution timeMemory
573145dennisstarAnts and Sugar (JOI22_sugar)C++17
0 / 100
315 ms36504 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct node { ll sum, lmin, rmin, mn, a[2]; }; node operator +(node l, node r) { node rt; ll md=l.a[1]; rt.sum=l.sum+r.sum-md; rt.lmin=min(l.lmin+r.mn, l.sum+r.lmin-md); rt.rmin=min(r.rmin+l.mn, r.sum+l.rmin-md); rt.mn=min(l.mn+r.mn, l.rmin+r.lmin-md); rt.a[0]=l.a[0], rt.a[1]=r.a[1]; return rt; } node st[1<<20]; void upd1(int i, int s, int e, int t, int ty, int v) { if (t<s||t>e) return ; if (s==e) { st[i].sum+=v; st[i].a[ty]+=v; st[i].lmin=st[i].rmin=st[i].sum; st[i].mn=min(0ll, st[i].sum); return ; } int m=(s+e)/2; if (t<=m) upd1(i*2, s, m, t, ty, v); else upd1(i*2+1, m+1, e, t, ty, v); st[i]=st[i*2]+st[i*2+1]; } void upd2(int i, int s, int e, int t, int v) { if (s==e) { st[i].sum-=v; st[i].lmin=st[i].rmin=st[i].sum; st[i].mn=min(0ll, st[i].sum); return ; } int m=(s+e)/2; if (t<=m) upd2(i*2, s, m, t, v); else upd2(i*2+1, m+1, e, t, v); st[i]=st[i*2]+st[i*2+1]; } int main() { cin.tie(0)->sync_with_stdio(0); int q, l; cin>>q>>l; ll sum=0; for (int l=0; l<q; l++) { int t, x, a; cin>>t>>x>>a; x++; if (t==1) upd1(1, 1, (q+1)/2, x/2, 1, a), upd1(1, 1, (q+1)/2, x/2+1, 0, a); else sum+=a, upd2(1, 1, (q+1)/2, (x+1)/2, a); cout<<sum+st[1].mn<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...