oj.uz

Submission #866554

# Submission time Handle Problem Language Result Execution time Memory
866554 2023-10-26T11:26:33 Z willychan Ants and Sugar (JOI22_sugar) C++14
100 / 100
 1247 ms 120584 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
// 0-base
// my dp is just wrong, l,r can be the same, why? because 
ll suma,sumb;
vector<int> d;
inline int ind(int X){
	return lower_bound(d.begin(),d.end(),X)-d.begin();
}

struct Data{
	//ll dp[2][2] = {{(ll)-1e17,(ll)-1e17},{(ll)-1e17,(ll)-1e17}};
	ll dp[2][2] = {{0,0},{0,0}};
};
Data operator+(Data &a,Data &b){
	Data ret;
	ret.dp[0][0]= max({a.dp[0][0]+b.dp[0][0],a.dp[0][1]+b.dp[1][0]});
	ret.dp[0][1]= max({a.dp[0][0]+b.dp[0][1],a.dp[0][1]+b.dp[1][1]});
	ret.dp[1][0]= max({a.dp[1][0]+b.dp[0][0],a.dp[1][1]+b.dp[1][0]});
	ret.dp[1][1]= max({a.dp[1][0]+b.dp[0][1],a.dp[1][1]+b.dp[1][1]});
	return ret;
}

struct SegTree{
	int s;
	struct node{
		Data dt;
		ll tag[2]={0,0};
		void add_tag(ll v,int o){
			dt.dp[o][o^1]+=v;
			tag[o]+=v;
		}
	};
	vector<node> arr;
	void init(int _s){
		s = _s;
		arr.resize(4*s+5);
	}
	void pull(int ind){
		arr[ind].dt = arr[2*ind].dt+arr[2*ind+1].dt;
	}
	void push(int ind){
		for(int o=0;o<2;o++){
			if(arr[ind].tag[o]){
				arr[2*ind].add_tag(arr[ind].tag[o],o);
				arr[2*ind+1].add_tag(arr[ind].tag[o],o);
				arr[ind].tag[o]=0;
			}
		}
	}
	void update(int ind,int v,int l,int r,int L,int R,int o){	
		if(l>=r) return;
		if(l==L && r==R){
			arr[ind].add_tag(v,o);
			return;
		}
		push(ind);
		int mid = (L+R)/2;
		if(r<=mid) update(2*ind,v,l,r,L,mid,o);
		else if(l>=mid) update(2*ind+1,v,l,r,mid,R,o);
		else{
			update(2*ind,v,l,mid,L,mid,o);
			update(2*ind+1,v,mid,r,mid,R,o);
		}
		pull(ind);
	}
	ll get(){
		return max(max(arr[1].dt.dp[1][1],arr[1].dt.dp[0][1])+sumb,max(arr[1].dt.dp[0][0],arr[1].dt.dp[1][0])+suma);
	}
} seg;


signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,L;			
	cin>>n>>L;
	vector<int> T(n),X(n),A(n);
	for(int i=0;i<n;i++) {
		cin>>T[i]>>X[i]>>A[i];
		d.push_back(X[i]);
	}
	sort(d.begin(),d.end());
	d.resize(unique(d.begin(),d.end())-d.begin());
	int N = d.size();
	seg.init(N);
	for(int i=0;i<n;i++){
		if(T[i]==1)	{
			suma+=A[i];
			int r = ind(X[i]);
			int l = ind(X[i]-L);
			seg.update(1,A[i],r,N,0,N,0);
			seg.update(1,-A[i],r,N,0,N,1);
			seg.update(1,-A[i],l,r,0,N,1);
		}else{
			sumb+=A[i]	;
			int r = ind(X[i]);
			int l = ind(X[i]-L);
			seg.update(1,A[i],r,N,0,N,1);
			seg.update(1,-A[i],r,N,0,N,0);
			seg.update(1,-A[i],l,r,0,N,0);
		}
		cout<<suma+sumb-seg.get()<<"\n";
	}
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 4 ms 1116 KB Output is correct
11 Correct 4 ms 1368 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 4 ms 1116 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 3 ms 984 KB Output is correct
16 Correct 4 ms 1116 KB Output is correct
17 Correct 4 ms 1116 KB Output is correct
18 Correct 4 ms 1080 KB Output is correct
19 Correct 3 ms 1116 KB Output is correct
20 Correct 4 ms 976 KB Output is correct
21 Correct 4 ms 1112 KB Output is correct
22 Correct 4 ms 1116 KB Output is correct
23 Correct 5 ms 1116 KB Output is correct
24 Correct 5 ms 1116 KB Output is correct
25 Correct 4 ms 1116 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 589 ms 54604 KB Output is correct
5 Correct 323 ms 57240 KB Output is correct
6 Correct 722 ms 71120 KB Output is correct
7 Correct 316 ms 57756 KB Output is correct
8 Correct 854 ms 83996 KB Output is correct
9 Correct 673 ms 119176 KB Output is correct
10 Correct 863 ms 84072 KB Output is correct
11 Correct 678 ms 119348 KB Output is correct
12 Correct 288 ms 51712 KB Output is correct
13 Correct 428 ms 71136 KB Output is correct
14 Correct 687 ms 115820 KB Output is correct
15 Correct 681 ms 115816 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 292 ms 51732 KB Output is correct
3 Correct 414 ms 71304 KB Output is correct
4 Correct 692 ms 115796 KB Output is correct
5 Correct 672 ms 115716 KB Output is correct
6 Correct 662 ms 69488 KB Output is correct
7 Correct 37 ms 7564 KB Output is correct
8 Correct 323 ms 40416 KB Output is correct
9 Correct 533 ms 55988 KB Output is correct
10 Correct 1000 ms 117312 KB Output is correct
11 Correct 1050 ms 117040 KB Output is correct
12 Correct 966 ms 117212 KB Output is correct
13 Correct 959 ms 117648 KB Output is correct
14 Correct 962 ms 117304 KB Output is correct
15 Correct 794 ms 117156 KB Output is correct
16 Correct 901 ms 117184 KB Output is correct
17 Correct 1082 ms 117472 KB Output is correct
18 Correct 1155 ms 117404 KB Output is correct
19 Correct 1123 ms 117420 KB Output is correct
20 Correct 1133 ms 117352 KB Output is correct
21 Correct 1206 ms 117128 KB Output is correct
22 Correct 1247 ms 117160 KB Output is correct
23 Correct 1192 ms 117300 KB Output is correct
24 Correct 999 ms 117200 KB Output is correct
25 Correct 1105 ms 117272 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 4 ms 1116 KB Output is correct
11 Correct 4 ms 1368 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 4 ms 1116 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 3 ms 984 KB Output is correct
16 Correct 4 ms 1116 KB Output is correct
17 Correct 4 ms 1116 KB Output is correct
18 Correct 4 ms 1080 KB Output is correct
19 Correct 3 ms 1116 KB Output is correct
20 Correct 4 ms 976 KB Output is correct
21 Correct 4 ms 1112 KB Output is correct
22 Correct 4 ms 1116 KB Output is correct
23 Correct 5 ms 1116 KB Output is correct
24 Correct 5 ms 1116 KB Output is correct
25 Correct 4 ms 1116 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 589 ms 54604 KB Output is correct
30 Correct 323 ms 57240 KB Output is correct
31 Correct 722 ms 71120 KB Output is correct
32 Correct 316 ms 57756 KB Output is correct
33 Correct 854 ms 83996 KB Output is correct
34 Correct 673 ms 119176 KB Output is correct
35 Correct 863 ms 84072 KB Output is correct
36 Correct 678 ms 119348 KB Output is correct
37 Correct 288 ms 51712 KB Output is correct
38 Correct 428 ms 71136 KB Output is correct
39 Correct 687 ms 115820 KB Output is correct
40 Correct 681 ms 115816 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 292 ms 51732 KB Output is correct
43 Correct 414 ms 71304 KB Output is correct
44 Correct 692 ms 115796 KB Output is correct
45 Correct 672 ms 115716 KB Output is correct
46 Correct 662 ms 69488 KB Output is correct
47 Correct 37 ms 7564 KB Output is correct
48 Correct 323 ms 40416 KB Output is correct
49 Correct 533 ms 55988 KB Output is correct
50 Correct 1000 ms 117312 KB Output is correct
51 Correct 1050 ms 117040 KB Output is correct
52 Correct 966 ms 117212 KB Output is correct
53 Correct 959 ms 117648 KB Output is correct
54 Correct 962 ms 117304 KB Output is correct
55 Correct 794 ms 117156 KB Output is correct
56 Correct 901 ms 117184 KB Output is correct
57 Correct 1082 ms 117472 KB Output is correct
58 Correct 1155 ms 117404 KB Output is correct
59 Correct 1123 ms 117420 KB Output is correct
60 Correct 1133 ms 117352 KB Output is correct
61 Correct 1206 ms 117128 KB Output is correct
62 Correct 1247 ms 117160 KB Output is correct
63 Correct 1192 ms 117300 KB Output is correct
64 Correct 999 ms 117200 KB Output is correct
65 Correct 1105 ms 117272 KB Output is correct
66 Correct 467 ms 55624 KB Output is correct
67 Correct 607 ms 63664 KB Output is correct
68 Correct 755 ms 72484 KB Output is correct
69 Correct 686 ms 67712 KB Output is correct
70 Correct 846 ms 120044 KB Output is correct
71 Correct 918 ms 120424 KB Output is correct
72 Correct 998 ms 120228 KB Output is correct
73 Correct 1004 ms 120264 KB Output is correct
74 Correct 998 ms 114124 KB Output is correct
75 Correct 925 ms 119584 KB Output is correct
76 Correct 940 ms 119332 KB Output is correct
77 Correct 871 ms 113944 KB Output is correct
78 Correct 987 ms 114032 KB Output is correct
79 Correct 1025 ms 120196 KB Output is correct
80 Correct 1074 ms 113976 KB Output is correct
81 Correct 1012 ms 120324 KB Output is correct
82 Correct 1171 ms 113972 KB Output is correct
83 Correct 1125 ms 120552 KB Output is correct
84 Correct 1131 ms 113884 KB Output is correct
85 Correct 1227 ms 120272 KB Output is correct
86 Correct 1202 ms 114084 KB Output is correct
87 Correct 1215 ms 120492 KB Output is correct
88 Correct 1074 ms 114392 KB Output is correct
89 Correct 999 ms 120584 KB Output is correct