oj.uz

Submission #946656

# Submission time Handle Problem Language Result Execution time Memory
946656 2024-03-14T21:14:09 Z MilosMilutinovic Ants and Sugar (JOI22_sugar) C++14
22 / 100
 4000 ms 683236 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[12000005][2][2][3],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<3;c++) dp[id][x][y][c]=max(dp[id<<1][x][y][c],dp[id<<1|1][x][y][c]);
	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]);
				}
			}
		}
	}
}

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 upd2(int id,ll v){
	for(int x=0;x<2;x++){
		for(int y=0;y<2;y++){
			for(int c=1;c<3;c++){
				dp[id][x][y][c]-=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;
	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<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 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<3;c++){
			chkmax(mx,dp[1][0][1][c]);
		}
		printf("%lld\n",sum-mx);
	}
	return 0;
}

Subtask #1
6.0 / 6.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 8652 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 9 ms 12892 KB Output is correct
7 Correct 8 ms 12892 KB Output is correct
8 Correct 4 ms 8796 KB Output is correct
9 Correct 4 ms 8828 KB Output is correct
10 Correct 14 ms 17152 KB Output is correct
11 Correct 15 ms 16984 KB Output is correct
12 Correct 15 ms 16984 KB Output is correct
13 Correct 15 ms 16988 KB Output is correct
14 Correct 16 ms 17144 KB Output is correct
15 Correct 16 ms 16988 KB Output is correct
16 Correct 10 ms 16984 KB Output is correct
17 Correct 9 ms 16988 KB Output is correct
18 Correct 9 ms 16988 KB Output is correct
19 Correct 15 ms 17176 KB Output is correct
20 Correct 10 ms 17148 KB Output is correct
21 Correct 16 ms 16988 KB Output is correct
22 Correct 9 ms 16984 KB Output is correct
23 Correct 18 ms 16984 KB Output is correct
24 Correct 9 ms 16988 KB Output is correct
25 Correct 14 ms 16984 KB Output is correct

Subtask #2
16.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 Correct 2283 ms 250340 KB Output is correct
5 Correct 964 ms 130780 KB Output is correct
6 Correct 2699 ms 250220 KB Output is correct
7 Correct 954 ms 130744 KB Output is correct
8 Correct 3248 ms 252192 KB Output is correct
9 Correct 2126 ms 253004 KB Output is correct
10 Correct 3388 ms 253960 KB Output is correct
11 Correct 2120 ms 253996 KB Output is correct
12 Correct 916 ms 129448 KB Output is correct
13 Correct 1289 ms 244952 KB Output is correct
14 Correct 2062 ms 250736 KB Output is correct
15 Correct 2101 ms 249364 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 907 ms 129616 KB Output is correct
3 Correct 1285 ms 244800 KB Output is correct
4 Correct 2085 ms 249700 KB Output is correct
5 Correct 2076 ms 250460 KB Output is correct
6 Correct 2330 ms 247708 KB Output is correct
7 Correct 191 ms 67016 KB Output is correct
8 Correct 1213 ms 242884 KB Output is correct
9 Correct 1778 ms 244836 KB Output is correct
10 Correct 3937 ms 672464 KB Output is correct
11 Correct 3941 ms 682124 KB Output is correct
12 Correct 3896 ms 683180 KB Output is correct
13 Correct 3850 ms 683236 KB Output is correct
14 Correct 3820 ms 682060 KB Output is correct
15 Correct 3620 ms 679440 KB Output is correct
16 Correct 3762 ms 682200 KB Output is correct
17 Correct 3926 ms 616568 KB Output is correct
18 Execution timed out 4118 ms 680360 KB Time limit exceeded
19 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 8540 KB Output is correct
3 Correct 1 ms 8652 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 9 ms 12892 KB Output is correct
7 Correct 8 ms 12892 KB Output is correct
8 Correct 4 ms 8796 KB Output is correct
9 Correct 4 ms 8828 KB Output is correct
10 Correct 14 ms 17152 KB Output is correct
11 Correct 15 ms 16984 KB Output is correct
12 Correct 15 ms 16984 KB Output is correct
13 Correct 15 ms 16988 KB Output is correct
14 Correct 16 ms 17144 KB Output is correct
15 Correct 16 ms 16988 KB Output is correct
16 Correct 10 ms 16984 KB Output is correct
17 Correct 9 ms 16988 KB Output is correct
18 Correct 9 ms 16988 KB Output is correct
19 Correct 15 ms 17176 KB Output is correct
20 Correct 10 ms 17148 KB Output is correct
21 Correct 16 ms 16988 KB Output is correct
22 Correct 9 ms 16984 KB Output is correct
23 Correct 18 ms 16984 KB Output is correct
24 Correct 9 ms 16988 KB Output is correct
25 Correct 14 ms 16984 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 1 ms 8540 KB Output is correct
28 Correct 1 ms 8540 KB Output is correct
29 Correct 2283 ms 250340 KB Output is correct
30 Correct 964 ms 130780 KB Output is correct
31 Correct 2699 ms 250220 KB Output is correct
32 Correct 954 ms 130744 KB Output is correct
33 Correct 3248 ms 252192 KB Output is correct
34 Correct 2126 ms 253004 KB Output is correct
35 Correct 3388 ms 253960 KB Output is correct
36 Correct 2120 ms 253996 KB Output is correct
37 Correct 916 ms 129448 KB Output is correct
38 Correct 1289 ms 244952 KB Output is correct
39 Correct 2062 ms 250736 KB Output is correct
40 Correct 2101 ms 249364 KB Output is correct
41 Correct 1 ms 8540 KB Output is correct
42 Correct 907 ms 129616 KB Output is correct
43 Correct 1285 ms 244800 KB Output is correct
44 Correct 2085 ms 249700 KB Output is correct
45 Correct 2076 ms 250460 KB Output is correct
46 Correct 2330 ms 247708 KB Output is correct
47 Correct 191 ms 67016 KB Output is correct
48 Correct 1213 ms 242884 KB Output is correct
49 Correct 1778 ms 244836 KB Output is correct
50 Correct 3937 ms 672464 KB Output is correct
51 Correct 3941 ms 682124 KB Output is correct
52 Correct 3896 ms 683180 KB Output is correct
53 Correct 3850 ms 683236 KB Output is correct
54 Correct 3820 ms 682060 KB Output is correct
55 Correct 3620 ms 679440 KB Output is correct
56 Correct 3762 ms 682200 KB Output is correct
57 Correct 3926 ms 616568 KB Output is correct
58 Execution timed out 4118 ms 680360 KB Time limit exceeded
59 Halted 0 ms 0 KB -