oj.uz

Submission #866555

# Submission time Handle Problem Language Result Execution time Memory
866555 2023-10-26T11:30:22 Z willychan Ants and Sugar (JOI22_sugar) C++14
100 / 100
 1192 ms 118620 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 2 ms 604 KB Output is correct
7 Correct 2 ms 780 KB Output is correct
8 Correct 1 ms 644 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 4 ms 1184 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 3 ms 1116 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 1116 KB Output is correct
19 Correct 3 ms 1112 KB Output is correct
20 Correct 4 ms 1112 KB Output is correct
21 Correct 4 ms 1116 KB Output is correct
22 Correct 4 ms 1116 KB Output is correct
23 Correct 4 ms 1116 KB Output is correct
24 Correct 4 ms 1060 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 344 KB Output is correct
4 Correct 579 ms 58088 KB Output is correct
5 Correct 315 ms 56672 KB Output is correct
6 Correct 676 ms 69720 KB Output is correct
7 Correct 310 ms 57296 KB Output is correct
8 Correct 829 ms 82448 KB Output is correct
9 Correct 675 ms 117128 KB Output is correct
10 Correct 816 ms 82104 KB Output is correct
11 Correct 667 ms 117136 KB Output is correct
12 Correct 284 ms 51152 KB Output is correct
13 Correct 405 ms 70192 KB Output is correct
14 Correct 664 ms 113708 KB Output is correct
15 Correct 657 ms 113964 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 295 ms 50996 KB Output is correct
3 Correct 408 ms 70164 KB Output is correct
4 Correct 651 ms 113864 KB Output is correct
5 Correct 655 ms 111416 KB Output is correct
6 Correct 637 ms 66108 KB Output is correct
7 Correct 36 ms 7508 KB Output is correct
8 Correct 317 ms 38860 KB Output is correct
9 Correct 501 ms 53272 KB Output is correct
10 Correct 905 ms 111972 KB Output is correct
11 Correct 953 ms 112140 KB Output is correct
12 Correct 934 ms 112216 KB Output is correct
13 Correct 882 ms 112356 KB Output is correct
14 Correct 924 ms 112192 KB Output is correct
15 Correct 762 ms 111928 KB Output is correct
16 Correct 904 ms 112212 KB Output is correct
17 Correct 1020 ms 112344 KB Output is correct
18 Correct 1085 ms 112412 KB Output is correct
19 Correct 1073 ms 112284 KB Output is correct
20 Correct 1082 ms 112240 KB Output is correct
21 Correct 1130 ms 112324 KB Output is correct
22 Correct 1155 ms 112448 KB Output is correct
23 Correct 1140 ms 112452 KB Output is correct
24 Correct 923 ms 112240 KB Output is correct
25 Correct 1090 ms 112272 KB Output is correct

Subtask #4
52.0 / 52.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 1 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 2 ms 604 KB Output is correct
7 Correct 2 ms 780 KB Output is correct
8 Correct 1 ms 644 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 4 ms 1184 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 3 ms 1116 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 1116 KB Output is correct
19 Correct 3 ms 1112 KB Output is correct
20 Correct 4 ms 1112 KB Output is correct
21 Correct 4 ms 1116 KB Output is correct
22 Correct 4 ms 1116 KB Output is correct
23 Correct 4 ms 1116 KB Output is correct
24 Correct 4 ms 1060 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 344 KB Output is correct
29 Correct 579 ms 58088 KB Output is correct
30 Correct 315 ms 56672 KB Output is correct
31 Correct 676 ms 69720 KB Output is correct
32 Correct 310 ms 57296 KB Output is correct
33 Correct 829 ms 82448 KB Output is correct
34 Correct 675 ms 117128 KB Output is correct
35 Correct 816 ms 82104 KB Output is correct
36 Correct 667 ms 117136 KB Output is correct
37 Correct 284 ms 51152 KB Output is correct
38 Correct 405 ms 70192 KB Output is correct
39 Correct 664 ms 113708 KB Output is correct
40 Correct 657 ms 113964 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 295 ms 50996 KB Output is correct
43 Correct 408 ms 70164 KB Output is correct
44 Correct 651 ms 113864 KB Output is correct
45 Correct 655 ms 111416 KB Output is correct
46 Correct 637 ms 66108 KB Output is correct
47 Correct 36 ms 7508 KB Output is correct
48 Correct 317 ms 38860 KB Output is correct
49 Correct 501 ms 53272 KB Output is correct
50 Correct 905 ms 111972 KB Output is correct
51 Correct 953 ms 112140 KB Output is correct
52 Correct 934 ms 112216 KB Output is correct
53 Correct 882 ms 112356 KB Output is correct
54 Correct 924 ms 112192 KB Output is correct
55 Correct 762 ms 111928 KB Output is correct
56 Correct 904 ms 112212 KB Output is correct
57 Correct 1020 ms 112344 KB Output is correct
58 Correct 1085 ms 112412 KB Output is correct
59 Correct 1073 ms 112284 KB Output is correct
60 Correct 1082 ms 112240 KB Output is correct
61 Correct 1130 ms 112324 KB Output is correct
62 Correct 1155 ms 112448 KB Output is correct
63 Correct 1140 ms 112452 KB Output is correct
64 Correct 923 ms 112240 KB Output is correct
65 Correct 1090 ms 112272 KB Output is correct
66 Correct 428 ms 53188 KB Output is correct
67 Correct 562 ms 60888 KB Output is correct
68 Correct 707 ms 69588 KB Output is correct
69 Correct 649 ms 64688 KB Output is correct
70 Correct 816 ms 114888 KB Output is correct
71 Correct 883 ms 115164 KB Output is correct
72 Correct 912 ms 115140 KB Output is correct
73 Correct 950 ms 115464 KB Output is correct
74 Correct 937 ms 109020 KB Output is correct
75 Correct 876 ms 117568 KB Output is correct
76 Correct 916 ms 117432 KB Output is correct
77 Correct 847 ms 111784 KB Output is correct
78 Correct 930 ms 111672 KB Output is correct
79 Correct 961 ms 118136 KB Output is correct
80 Correct 1036 ms 111892 KB Output is correct
81 Correct 955 ms 118080 KB Output is correct
82 Correct 1085 ms 111996 KB Output is correct
83 Correct 1116 ms 118620 KB Output is correct
84 Correct 1102 ms 111820 KB Output is correct
85 Correct 1139 ms 115620 KB Output is correct
86 Correct 1192 ms 108756 KB Output is correct
87 Correct 1152 ms 115520 KB Output is correct
88 Correct 1024 ms 109064 KB Output is correct
89 Correct 977 ms 115404 KB Output is correct