Submission #946664

#	Time	Username	Problem	Language	Result	Execution time	Memory
946664		MilosMilutinovic	Ants and Sugar (JOI22_sugar)	C++14	100 / 100	2612 ms	503396 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[12000005][2][2][2],lzy[12000005][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<2;c++) dp[id][c][x][y]=max(dp[id<<1][c][x][y],dp[id<<1|1][c][x][y]);
	for(int x1=0;x1<2;x1++){
		for(int y2=0;y2<2;y2++){
			for(int c1=0;c1<2;c1++){
				for(int c2=0;c2<2;c2++){
					dp[id][min(1,c1+c2)][x1][y2]=max(dp[id][min(1,c1+c2)][x1][y2],dp[id<<1][c1][x1][0]+dp[id<<1|1][c2][1][y2]);
					dp[id][min(1,c1+c2)][x1][y2]=max(dp[id][min(1,c1+c2)][x1][y2],dp[id<<1][c1][x1][1]+dp[id<<1|1][c2][0][y2]);
				}
			}
		}
	}
}

void upd1(int id,ll v){
	for(int c=0;c<2;c++){
		dp[id][c][0][0]-=v;
		dp[id][c][1][1]+=v;
	}
}

void upd2(int id,ll v){
	for(int x=0;x<2;x++){
		for(int y=0;y<2;y++){
			dp[id][1][x][y]-=v;
		}
	}
}

void push(int id){
	if((id<<1|1)>6000000) return;
	if(lzy[id][0]!=0){
		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;
	}
	if(lzy[id][1]!=0){
		upd2(id<<1,lzy[id][1]);
		upd2(id<<1|1,lzy[id][1]);
		lzy[id<<1][1]+=lzy[id][1];
		lzy[id<<1|1][1]+=lzy[id][1];
		lzy[id][1]=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<2;c++){
					dp[id][c][x][y]=(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 ql,int qr,int v){
	if(ql<=l&&r<=qr){
		upd2(id,v);
		lzy[id][1]+=v;
		push(id);
		return;
	}
	push(id);
	int mid=(l+r)/2;
	if(qr<=mid) modify(id<<1,l,mid,ql,qr,v);
	else if(ql>mid) modify(id<<1|1,mid+1,r,ql,qr,v);
	else modify(id<<1,l,mid,ql,qr,v),modify(id<<1|1,mid+1,r,ql,qr,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());
			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());
			change(1,0,k-1,idx1,k-1,-a[i]);
			int idx2=(int)(lower_bound(xs.begin(),xs.end(),x[i]-l)-xs.begin());
			modify(1,0,k-1,idx2,idx1-1,a[i]);
		}
		ll mx=0;
		for(int c=0;c<2;c++){
			chkmax(mx,dp[1][c][0][1]);
		}
		printf("%lld\n",sum-mx);
	}
	return 0;
}

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