#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=5e5+10;
const ll mod=1e9+7 ;
const ll base=3e18;
ll t[maxn];
ll x[maxn];
ll a[maxn];
struct tk
{
ll dp[3][2][2];
ll la;
ll la1;
tk()
{
la=0;
la1=0;
memset(dp,-0x3f,sizeof(dp));
dp[1][0][1]=0;
dp[1][1][1]=0;
dp[0][0][0]=0;
dp[0][0][1]=0;
dp[0][1][0]=0;
}
};
tk st[4*maxn];
void modify(ll id,ll val,ll val1)
{
for (int t=0;t<=2;t++)
{
st[id].dp[t][0][0]-=val;
st[id].dp[t][1][1]+=val;
for (int i=0;i<=1;i++)
{
for (int j=0;j<=1;j++)
{
if (t==0&&(i||j)) continue;
st[id].dp[t][i][j]+=(val1*t);
}
}
}
st[id].la+=val;
st[id].la1+=val1;
}
void dosth(ll id)
{
modify(id*2,st[id].la,st[id].la1);
modify(id*2+1,st[id].la,st[id].la1);
st[id].la=0;
st[id].la1=0;
}
tk mer(tk a,tk b)
{
tk c;
for (int t=0; t<=2; t++)
{
for (int l=0; l<=1; l++)
{
for (int r=0; r<=1; r++)
{
if (a.dp[t][l][r]==-base)
continue;
ll l1=1-r;
for (int t1=0; t1<=2; t1++)
{
for (int r1=0; r1<=1; r1++)
{
c.dp[min(2,t+t1)][l][r1]=max(c.dp[min(2,t+t1)][l][r1],a.dp[t][l][r]+b.dp[t1][l1][r1]);
}
}
}
}
}
return c;
}
void update(ll id,ll left,ll right,ll x,ll diff)
{
if (x>right||x<left) return ;
if (left==right)
{
st[id].dp[1][0][1]+=diff;
st[id].dp[1][1][1]+=diff;
return ;
}
dosth(id);
ll mid=(left+right)/2;
update(id*2,left,mid,x,diff);
update(id*2+1,mid+1,right,x,diff);
st[id]=mer(st[id*2],st[id*2+1]);
}
void update1(ll id,ll left,ll right,ll x,ll y,ll val,ll val1)
{
if (x>right||y<left) return ;
if (x<=left&&y>=right)
{
modify(id,val,val1);
return ;
}
dosth(id);
ll mid=(left+right)/2;
update1(id*2,left,mid,x,y,val,val1);
update1(id*2+1,mid+1,right,x,y,val,val1);
st[id]=mer(st[id*2],st[id*2+1]);
}
void build(ll id,ll left,ll right)
{
if (left==right)
{
return ;
}
ll mid=(left+right)/2;
build(id*2,left,mid);
build(id*2+1,mid+1,right);
st[id]=mer(st[id*2],st[id*2+1]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
ll q, l;
cin>> q>> l;
vector<ll> vt;
for (int i=1; i<=q; i++)
{
cin>> t[i]>> x[i]>> a[i];
vt.pb(x[i]);
}
sort(vt.begin(),vt.end());
vt.resize(unique(vt.begin(),vt.end())-vt.begin());
ll len=vt.size();
build(1,1,len);
ll cnt=0;
for (int i=1;i<=q;i++)
{
if (t[i]==1)
{
cnt+=a[i];
ll pos=lower_bound(vt.begin(),vt.end(),x[i]+1)-vt.begin()+1;
update1(1,1,len,pos,len,a[i],0);
pos=lower_bound(vt.begin(),vt.end(),x[i])-vt.begin()+1;
update(1,1,len,pos,a[i]);
}
else
{
ll pos=lower_bound(vt.begin(),vt.end(),x[i]+l+1)-vt.begin()+1;
update1(1,1,len,pos,len,-a[i],0);
ll r=upper_bound(vt.begin(),vt.end(),x[i]+l)-vt.begin();
ll l=lower_bound(vt.begin(),vt.end(),x[i]-l)-vt.begin()+1;
update1(1,1,len,l,r,0,-a[i]);
}
ll res=0;
for (int t=0;t<=2;t++)
{
res=max(res,st[1].dp[t][0][1]);
}
// cout <<cnt<<" "<<res<<endl;
cout <<cnt-res<<endl;
}
}
Compilation message
sugar.cpp: In function 'int main()':
sugar.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | freopen("test.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sugar.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | freopen("test.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sugar.cpp:164:54: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
164 | ll l=lower_bound(vt.begin(),vt.end(),x[i]-l)-vt.begin()+1;
| ~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
219408 KB |
Output is correct |
| 2 |
Incorrect |
101 ms |
219480 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
219412 KB |
Output is correct |
| 2 |
Incorrect |
101 ms |
219508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
219472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
219408 KB |
Output is correct |
| 2 |
Incorrect |
101 ms |
219480 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
