oj.uz

Submission #946650

# Submission time Handle Problem Language Result Execution time Memory
946650 2024-03-14T21:00:43 Z MilosMilutinovic Ants and Sugar (JOI22_sugar) C++14
0 / 100
 4000 ms 246096 KB 
#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++){
					for(int c1=0;c1<3;c1++){
						for(int c2=0;c2<3;c2++){
							if(x2!=y1) 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 c=0;c<3;c++){
		dp[id][0][0][c]-=v;
		dp[id][1][1][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 c=0;c<3;c++){
			chkmax(mx,dp[1][0][1][c]);
		}
		printf("%lld\n",sum-mx);
	}
	return 0;
}

Subtask #1
0 / 6.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 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 23 ms 12892 KB Output is correct
7 Correct 28 ms 12888 KB Output is correct
8 Correct 17 ms 10840 KB Output is correct
9 Correct 19 ms 10840 KB Output is correct
10 Correct 42 ms 16988 KB Output is correct
11 Correct 74 ms 17196 KB Output is correct
12 Correct 178 ms 17492 KB Output is correct
13 Correct 168 ms 17224 KB Output is correct
14 Correct 101 ms 17240 KB Output is correct
15 Correct 95 ms 17200 KB Output is correct
16 Correct 24 ms 16984 KB Output is correct
17 Correct 20 ms 16988 KB Output is correct
18 Correct 21 ms 16984 KB Output is correct
19 Correct 56 ms 16988 KB Output is correct
20 Correct 20 ms 16984 KB Output is correct
21 Correct 953 ms 17248 KB Output is correct
22 Correct 20 ms 16988 KB Output is correct
23 Execution timed out 4078 ms 17444 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Execution timed out 4072 ms 240580 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 3251 ms 129432 KB Output is correct
3 Execution timed out 4037 ms 246096 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 52.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 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 23 ms 12892 KB Output is correct
7 Correct 28 ms 12888 KB Output is correct
8 Correct 17 ms 10840 KB Output is correct
9 Correct 19 ms 10840 KB Output is correct
10 Correct 42 ms 16988 KB Output is correct
11 Correct 74 ms 17196 KB Output is correct
12 Correct 178 ms 17492 KB Output is correct
13 Correct 168 ms 17224 KB Output is correct
14 Correct 101 ms 17240 KB Output is correct
15 Correct 95 ms 17200 KB Output is correct
16 Correct 24 ms 16984 KB Output is correct
17 Correct 20 ms 16988 KB Output is correct
18 Correct 21 ms 16984 KB Output is correct
19 Correct 56 ms 16988 KB Output is correct
20 Correct 20 ms 16984 KB Output is correct
21 Correct 953 ms 17248 KB Output is correct
22 Correct 20 ms 16988 KB Output is correct
23 Execution timed out 4078 ms 17444 KB Time limit exceeded
24 Halted 0 ms 0 KB -