Submission #946632

#	Time	Username	Problem	Language	Result	Execution time	Memory
946632		MilosMilutinovic	Ants and Sugar (JOI22_sugar)	C++14	0 / 100	4062 ms	255340 KiB

sugar

#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;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52