oj.uz

Submission #946651

# Submission time Handle Problem Language Result Execution time Memory
946651 2024-03-14T21:06:04 Z MilosMilutinovic Ants and Sugar (JOI22_sugar) C++14
0 / 100
 4000 ms 264668 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 y2=0;y2<2;y2++){
			for(int c1=0;c1<3;c1++){
				for(int c2=0;c2<3;c2++){
					dp[id][x1][y2][min(2,c1+c2)]=max(dp[id][x1][y2][min(2,c1+c2)],dp[id<<1][x1][0][c1]+dp[id<<1|1][1][y2][c2]);
					dp[id][x1][y2][min(2,c1+c2)]=max(dp[id][x1][y2][min(2,c1+c2)],dp[id<<1][x1][1][c1]+dp[id<<1|1][0][y2][c2]);
				}
			}
		}
	}
	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]=max(dp[id][x][y][c],dp[id<<1][x][y][c]);
				dp[id][x][y][c]=max(dp[id][x][y][c],dp[id<<1|1][x][y][c]);
			}
		}
	}
}

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());
			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());
			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 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 11 ms 12892 KB Output is correct
7 Correct 12 ms 13016 KB Output is correct
8 Correct 7 ms 10840 KB Output is correct
9 Correct 9 ms 10844 KB Output is correct
10 Correct 18 ms 17144 KB Output is correct
11 Correct 29 ms 17148 KB Output is correct
12 Correct 68 ms 17248 KB Output is correct
13 Correct 71 ms 16988 KB Output is correct
14 Correct 37 ms 16988 KB Output is correct
15 Correct 39 ms 16984 KB Output is correct
16 Correct 13 ms 16988 KB Output is correct
17 Correct 12 ms 16984 KB Output is correct
18 Correct 9 ms 16988 KB Output is correct
19 Correct 22 ms 17148 KB Output is correct
20 Correct 12 ms 17500 KB Output is correct
21 Correct 323 ms 16988 KB Output is correct
22 Correct 10 ms 16988 KB Output is correct
23 Correct 2740 ms 17332 KB Output is correct
24 Correct 9 ms 16988 KB Output is correct
25 Execution timed out 4062 ms 17436 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2897 ms 247824 KB Output is correct
5 Correct 1334 ms 135348 KB Output is correct
6 Correct 3394 ms 259052 KB Output is correct
7 Correct 1344 ms 135488 KB Output is correct
8 Correct 3971 ms 263604 KB Output is correct
9 Correct 2739 ms 264668 KB Output is correct
10 Execution timed out 4014 ms 263984 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1144 ms 128668 KB Output is correct
3 Correct 1684 ms 245708 KB Output is correct
4 Correct 2739 ms 260252 KB Output is correct
5 Correct 2695 ms 260128 KB Output is correct
6 Correct 2763 ms 257112 KB Output is correct
7 Correct 214 ms 67584 KB Output is correct
8 Correct 2175 ms 247048 KB Output is correct
9 Execution timed out 4017 ms 251660 KB Time limit exceeded
10 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 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 11 ms 12892 KB Output is correct
7 Correct 12 ms 13016 KB Output is correct
8 Correct 7 ms 10840 KB Output is correct
9 Correct 9 ms 10844 KB Output is correct
10 Correct 18 ms 17144 KB Output is correct
11 Correct 29 ms 17148 KB Output is correct
12 Correct 68 ms 17248 KB Output is correct
13 Correct 71 ms 16988 KB Output is correct
14 Correct 37 ms 16988 KB Output is correct
15 Correct 39 ms 16984 KB Output is correct
16 Correct 13 ms 16988 KB Output is correct
17 Correct 12 ms 16984 KB Output is correct
18 Correct 9 ms 16988 KB Output is correct
19 Correct 22 ms 17148 KB Output is correct
20 Correct 12 ms 17500 KB Output is correct
21 Correct 323 ms 16988 KB Output is correct
22 Correct 10 ms 16988 KB Output is correct
23 Correct 2740 ms 17332 KB Output is correct
24 Correct 9 ms 16988 KB Output is correct
25 Execution timed out 4062 ms 17436 KB Time limit exceeded
26 Halted 0 ms 0 KB -