oj.uz

Submission #946664

# Submission time Handle Problem Language Result Execution time Memory
946664 2024-03-14T21:25:41 Z MilosMilutinovic Ants and Sugar (JOI22_sugar) C++14
100 / 100
 2612 ms 503396 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][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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 5 ms 8796 KB Output is correct
7 Correct 5 ms 8944 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 8 ms 13144 KB Output is correct
11 Correct 8 ms 13148 KB Output is correct
12 Correct 9 ms 13156 KB Output is correct
13 Correct 9 ms 13144 KB Output is correct
14 Correct 9 ms 12892 KB Output is correct
15 Correct 9 ms 12892 KB Output is correct
16 Correct 6 ms 12968 KB Output is correct
17 Correct 6 ms 12892 KB Output is correct
18 Correct 6 ms 12892 KB Output is correct
19 Correct 8 ms 13068 KB Output is correct
20 Correct 6 ms 11868 KB Output is correct
21 Correct 9 ms 13144 KB Output is correct
22 Correct 6 ms 12888 KB Output is correct
23 Correct 9 ms 13148 KB Output is correct
24 Correct 6 ms 12892 KB Output is correct
25 Correct 9 ms 13144 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1206 ms 187616 KB Output is correct
5 Correct 501 ms 100020 KB Output is correct
6 Correct 1431 ms 191200 KB Output is correct
7 Correct 501 ms 100104 KB Output is correct
8 Correct 1698 ms 195468 KB Output is correct
9 Correct 1106 ms 193968 KB Output is correct
10 Correct 1696 ms 195392 KB Output is correct
11 Correct 1140 ms 196312 KB Output is correct
12 Correct 464 ms 99456 KB Output is correct
13 Correct 653 ms 183292 KB Output is correct
14 Correct 1081 ms 192588 KB Output is correct
15 Correct 1088 ms 190560 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 490 ms 99192 KB Output is correct
3 Correct 655 ms 183564 KB Output is correct
4 Correct 1101 ms 192088 KB Output is correct
5 Correct 1078 ms 191976 KB Output is correct
6 Correct 1274 ms 187620 KB Output is correct
7 Correct 92 ms 49352 KB Output is correct
8 Correct 651 ms 180340 KB Output is correct
9 Correct 970 ms 183272 KB Output is correct
10 Correct 2116 ms 495732 KB Output is correct
11 Correct 2045 ms 494656 KB Output is correct
12 Correct 2021 ms 494300 KB Output is correct
13 Correct 2001 ms 493200 KB Output is correct
14 Correct 2054 ms 495620 KB Output is correct
15 Correct 1903 ms 492036 KB Output is correct
16 Correct 2008 ms 488416 KB Output is correct
17 Correct 2201 ms 470004 KB Output is correct
18 Correct 2399 ms 488824 KB Output is correct
19 Correct 2341 ms 475052 KB Output is correct
20 Correct 2322 ms 495280 KB Output is correct
21 Correct 2301 ms 468524 KB Output is correct
22 Correct 2612 ms 494396 KB Output is correct
23 Correct 2378 ms 450080 KB Output is correct
24 Correct 2285 ms 500284 KB Output is correct
25 Correct 2286 ms 460204 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 5 ms 8796 KB Output is correct
7 Correct 5 ms 8944 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 8 ms 13144 KB Output is correct
11 Correct 8 ms 13148 KB Output is correct
12 Correct 9 ms 13156 KB Output is correct
13 Correct 9 ms 13144 KB Output is correct
14 Correct 9 ms 12892 KB Output is correct
15 Correct 9 ms 12892 KB Output is correct
16 Correct 6 ms 12968 KB Output is correct
17 Correct 6 ms 12892 KB Output is correct
18 Correct 6 ms 12892 KB Output is correct
19 Correct 8 ms 13068 KB Output is correct
20 Correct 6 ms 11868 KB Output is correct
21 Correct 9 ms 13144 KB Output is correct
22 Correct 6 ms 12888 KB Output is correct
23 Correct 9 ms 13148 KB Output is correct
24 Correct 6 ms 12892 KB Output is correct
25 Correct 9 ms 13144 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6492 KB Output is correct
29 Correct 1206 ms 187616 KB Output is correct
30 Correct 501 ms 100020 KB Output is correct
31 Correct 1431 ms 191200 KB Output is correct
32 Correct 501 ms 100104 KB Output is correct
33 Correct 1698 ms 195468 KB Output is correct
34 Correct 1106 ms 193968 KB Output is correct
35 Correct 1696 ms 195392 KB Output is correct
36 Correct 1140 ms 196312 KB Output is correct
37 Correct 464 ms 99456 KB Output is correct
38 Correct 653 ms 183292 KB Output is correct
39 Correct 1081 ms 192588 KB Output is correct
40 Correct 1088 ms 190560 KB Output is correct
41 Correct 1 ms 6492 KB Output is correct
42 Correct 490 ms 99192 KB Output is correct
43 Correct 655 ms 183564 KB Output is correct
44 Correct 1101 ms 192088 KB Output is correct
45 Correct 1078 ms 191976 KB Output is correct
46 Correct 1274 ms 187620 KB Output is correct
47 Correct 92 ms 49352 KB Output is correct
48 Correct 651 ms 180340 KB Output is correct
49 Correct 970 ms 183272 KB Output is correct
50 Correct 2116 ms 495732 KB Output is correct
51 Correct 2045 ms 494656 KB Output is correct
52 Correct 2021 ms 494300 KB Output is correct
53 Correct 2001 ms 493200 KB Output is correct
54 Correct 2054 ms 495620 KB Output is correct
55 Correct 1903 ms 492036 KB Output is correct
56 Correct 2008 ms 488416 KB Output is correct
57 Correct 2201 ms 470004 KB Output is correct
58 Correct 2399 ms 488824 KB Output is correct
59 Correct 2341 ms 475052 KB Output is correct
60 Correct 2322 ms 495280 KB Output is correct
61 Correct 2301 ms 468524 KB Output is correct
62 Correct 2612 ms 494396 KB Output is correct
63 Correct 2378 ms 450080 KB Output is correct
64 Correct 2285 ms 500284 KB Output is correct
65 Correct 2286 ms 460204 KB Output is correct
66 Correct 988 ms 185304 KB Output is correct
67 Correct 1314 ms 187708 KB Output is correct
68 Correct 1472 ms 191440 KB Output is correct
69 Correct 1304 ms 189208 KB Output is correct
70 Correct 2079 ms 501968 KB Output is correct
71 Correct 2209 ms 501864 KB Output is correct
72 Correct 2228 ms 503396 KB Output is correct
73 Correct 2230 ms 502652 KB Output is correct
74 Correct 2545 ms 496192 KB Output is correct
75 Correct 2538 ms 503052 KB Output is correct
76 Correct 1523 ms 501156 KB Output is correct
77 Correct 1432 ms 493136 KB Output is correct
78 Correct 1426 ms 494220 KB Output is correct
79 Correct 2307 ms 502276 KB Output is correct
80 Correct 1370 ms 493688 KB Output is correct
81 Correct 2220 ms 502432 KB Output is correct
82 Correct 1448 ms 493800 KB Output is correct
83 Correct 2469 ms 481120 KB Output is correct
84 Correct 1397 ms 493188 KB Output is correct
85 Correct 2591 ms 469716 KB Output is correct
86 Correct 1431 ms 486248 KB Output is correct
87 Correct 2557 ms 465380 KB Output is correct
88 Correct 1295 ms 428096 KB Output is correct
89 Correct 1867 ms 457564 KB Output is correct