#include <iostream> #include <algorithm> #include <unordered_map> #include <iomanip> #include <vector> using namespace std; vector<int>vec; unordered_map<int,int>mp; long long overmid[1200005]; long long overfull[1200005]; long long cost[1200005][2][2]; long long furnici[1200005]; long long lazy[1200005]; long long inf=1e18; void merge(int node,long long sussugar) { long long common=overmid[node]+sussugar+overfull[node]; cost[node][0][0]=0; cost[node][1][0]=-inf; cost[node][0][1]=-inf; cost[node][1][1]=-inf; for(int b1=0; b1<=1; b1++) { for(int b2=0; b2<=1; b2++) { for(int b3=0; b3<=1; b3++) { for(int b4=0; b4<=1; b4++) { if(b2+b3<=1) { cost[node][b1][b4]=max(cost[node][b1][b4],cost[node*2][b1][b2]+cost[node*2+1][b3][b4]); } else if(furnici[node*2]>=1 && furnici[node*2+1]>=1) { cost[node][b1][b4]=max(cost[node][b1][b4],cost[node*2][b1][b2]+cost[node*2+1][b3][b4]+common); } } } } } } void push(int node,int st,int dr) { if(lazy[node]!=0) { cost[node][0][0]=max(0ll,cost[node][0][0]-lazy[node]); cost[node][1][0]=cost[node][1][0]-lazy[node]; cost[node][0][1]=cost[node][0][1]-lazy[node]; cost[node][1][1]=cost[node][1][1]-lazy[node]; if(st!=dr) { lazy[node*2]+=lazy[node]; lazy[node*2+1]+=lazy[node]; } lazy[node]=0; } } void updatef(int node,int st,int dr,int poz,long long val,long long sussugar) { push(node,st,dr); if(st>poz || dr<poz) { return; } furnici[node]+=val; if(st==dr) { long long reach=sussugar+overfull[node]; cost[node][0][0]=0; cost[node][1][1]=furnici[node]-reach; cost[node][1][0]=-inf; cost[node][0][1]=-inf; return; } int mij=(st+dr)/2; updatef(node*2,st,mij,poz,val,sussugar+overfull[node]); updatef(node*2+1,mij+1,dr,poz,val,sussugar+overfull[node]); merge(node,sussugar); } void updatec(int node,int st,int dr,int qst,int qdr,long long val,long long sussugar) { push(node,st,dr); if(qst>dr || qst>qdr || st>dr || st>qdr) { return; } if(qst<=st && dr<=qdr) { lazy[node]+=val; overfull[node]+=val; push(node,st,dr); return; } int mij=(st+dr)/2; if(qst<=mij && qdr>=mij+1) { overmid[node]+=val; } updatec(node*2,st,mij,qst,qdr,val,sussugar+overfull[node]); updatec(node*2+1,mij+1,dr,qst,qdr,val,sussugar+overfull[node]); merge(node,sussugar); } void build(int node,int st,int dr) { cost[node][0][0]=0; cost[node][0][1]=-inf; cost[node][1][0]=-inf; cost[node][1][1]=-inf; if(st!=dr) { int mij=(st+dr)/2; build(node*2,st,mij); build(node*2+1,mij+1,dr); } } int tip[500005]; int x[500005]; int y[500005]; signed main() { long long n,i,j,k,l,m,p,q,r,na,nc; ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>q>>k; for(int i=1; i<=q; i++) { cin>>tip[i]>>x[i]>>y[i]; if(tip[i]==1) { vec.push_back(x[i]); } else { vec.push_back(x[i]-k); vec.push_back(x[i]+k); } } sort(vec.begin(),vec.end()); int cnt=0; for(int i=0; i<vec.size(); i++) { if(i==0 || vec[i]!=vec[i-1]) { cnt++; mp[vec[i]]=cnt; } } int nmax=cnt; long long cntf=0; for(int i=1; i<=q; i++) { if(tip[i]==1) { updatef(1,1,nmax,mp[x[i]],y[i],0); cntf=cntf+y[i]; } else { updatec(1,1,nmax,mp[x[i]-k],mp[x[i]+k],y[i],0); } cout<<cntf-max(max(cost[1][0][0],cost[1][1][0]),max(cost[1][0][1],cost[1][1][1]))<<'\n'; } return 0; }