#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
ll readint(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int q,l,k;
int t[500005],x[500005],a[500005];
ll b[1500005][2],sum,dp[6000005][2][2][3],lzy[6000005][2];
vector<int> xs;
void pull(int id){
for(int x=0;x<2;x++) for(int y=0;y<2;y++) for(int c=0;c<3;c++) dp[id][x][y][c]=(ll)-1e18;
for(int x1=0;x1<2;x1++){
for(int x2=0;x2<2;x2++){
for(int y1=0;y1<2;y1++){
for(int y2=0;y2<2;y2++){
if(x2==y1) continue;
for(int c1=0;c1<3;c1++){
for(int c2=0;c2<3;c2++){
chkmax(dp[id][x1][y2][min(2,c1+c2)],dp[id<<1][x1][x2][c1]+dp[id<<1|1][y1][y2][c2]);
chkmax(dp[id][x1][x2][c1],dp[id<<1][x1][x2][c1]);
chkmax(dp[id][y1][y2][c2],dp[id<<1|1][y1][y2][c2]);
}
}
}
}
}
}
}
void upd1(int id,ll v){
for(int x=0;x<2;x++){
for(int y=0;y<2;y++){
for(int c=0;c<3;c++){
if(x!=y) continue;
if(x==0) dp[id][x][y][c]-=v;
if(x==1) dp[id][x][y][c]+=v;
}
}
}
}
void push(int id){
if((id<<1|1)>6000000) return;
upd1(id<<1,lzy[id][0]);
upd1(id<<1|1,lzy[id][0]);
lzy[id<<1][0]+=lzy[id][0];
lzy[id<<1|1][0]+=lzy[id][0];
lzy[id][0]=0;
}
void build(int id,int l,int r){
if(l==r){
for(int x=0;x<2;x++){
for(int y=0;y<2;y++){
for(int c=0;c<3;c++){
dp[id][x][y][c]=(ll)-1e18;
}
}
}
dp[id][0][0][0]=0;
dp[id][1][1][1]=0;
return;
}
int mid=(l+r)/2;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
pull(id);
}
void change(int id,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){
upd1(id,v);
lzy[id][0]+=v;
push(id);
return;
}
push(id);
int mid=(l+r)/2;
if(qr<=mid) change(id<<1,l,mid,ql,qr,v);
else if(ql>mid) change(id<<1|1,mid+1,r,ql,qr,v);
else change(id<<1,l,mid,ql,qr,v),change(id<<1|1,mid+1,r,ql,qr,v);
pull(id);
}
void modify(int id,int l,int r,int p,int v){
if(l==r){
dp[id][1][1][1]-=v;
return;
}
push(id);
int mid=(l+r)/2;
if(p<=mid) modify(id<<1,l,mid,p,v);
else modify(id<<1|1,mid+1,r,p,v);
pull(id);
}
int main(){
q=readint(); l=readint();
for(int i=1;i<=q;i++){
t[i]=readint(); x[i]=readint(); a[i]=readint();
}
for(int i=1;i<=q;i++){
xs.pb(x[i]);
xs.pb(x[i]-l);
xs.pb(x[i]+l);
}
xs.pb((int)-1.00001e9);
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
k=(int)xs.size();
build(1,0,k-1);
for(int i=1;i<=q;i++){
if(t[i]==1){
int idx=(int)(lower_bound(xs.begin(),xs.end(),x[i])-xs.begin());
//for(int j=idx;j<k;j++) b[j][0]+=a[i];
//for(int j=idx;j<k;j++) b[j][1]+=a[i];
change(1,0,k-1,idx,k-1,a[i]);
sum+=a[i];
}else{
int idx1=(int)(lower_bound(xs.begin(),xs.end(),x[i]+l)-xs.begin());
//for(int j=idx;j<k;j++) b[j][0]-=a[i];
change(1,0,k-1,idx1,k-1,-a[i]);
int idx2=(int)(lower_bound(xs.begin(),xs.end(),x[i]-l)-xs.begin());
//for(int j=idx;j<k;j++) b[j][1]-=a[i];
for(int j=idx2;j<idx1;j++) modify(1,0,k-1,j,a[i]);
}
ll mx=0;
for(int x=0;x<2;x++){
for(int y=0;y<2;y++){
for(int c=0;c<3;c++){
chkmax(mx,dp[1][x][y][c]);
}
}
}
printf("%lld\n",max(0ll,sum-mx));
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8648 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Execution timed out |
4062 ms |
255340 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
2375 ms |
133764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
