This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
struct T{
int mx[2][2];
T(){memset(mx,0,sizeof(mx));}
}st[4000001];
int lazy[4000001],cnt[4000001];
T f(T a, T b, int cnt){
T c;
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
c.mx[i][j]=max(a.mx[i][0]+b.mx[0][j],a.mx[i][1]+b.mx[1][j]-cnt);
for (int i=0;i<2;i++){
c.mx[i][0]=max(c.mx[i][0],a.mx[i][0]);
c.mx[0][i]=max(c.mx[0][i],b.mx[0][i]);
}
return c;
}
void down(int node, int l, int r){
if (!lazy[node]||l==r)
return;
for (int i=0;i<2;i++)
for (int j=0;j<2;j++){
st[node<<1].mx[i][j]+=lazy[node];
st[node<<1|1].mx[i][j]+=lazy[node];
}
lazy[node<<1]+=lazy[node];
lazy[node<<1|1]+=lazy[node];
lazy[node]=0;
}
void update(int node, int l, int r, int u, int v, int val){
if (l>v||r<u||l>r)
return;
if (l>=u&&r<=v){
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
st[node].mx[i][j]+=val;
lazy[node]+=val;
return;
}
down(node,l,r);
int mid=(l+r)>>1;
if (mid>=u&&mid<v)
cnt[node]+=val;
update(node<<1,l,mid,u,v,val);
update(node<<1|1,mid+1,r,u,v,val);
st[node]=f(st[node<<1],st[node<<1|1],cnt[node]);
}
int q,l,t[500001],x[500001],a[500001],s;
vector <int> ve;
int32_t main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> q >> l;
for (int i=0;i<q;i++){
cin >> t[i] >> x[i] >> a[i];
if (t[i]==1)
ve.push_back(x[i]);
else{
ve.push_back(x[i]-l);
ve.push_back(x[i]+l);
}
}
sort(ve.begin(),ve.end());
ve.resize(unique(ve.begin(),ve.end())-ve.begin());
for (int i=0;i<q;i++){
if (t[i]==1){
s+=a[i];
int pos=lower_bound(ve.begin(),ve.end(),x[i])-ve.begin();
update(1,0,ve.size()-1,pos,pos,a[i]);
}
else{
int u=lower_bound(ve.begin(),ve.end(),x[i]-l)-ve.begin();
int v=lower_bound(ve.begin(),ve.end(),x[i]+l)-ve.begin();
update(1,0,ve.size()-1,u,v,-a[i]);
}
cout << s-max(st[1].mx[0][0],0LL) << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |