Submission #1256127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256127		anonymousbunny	Catfish Farm (IOI22_fish)	C++20	81 / 100	1097 ms	91544 KiB

fish

#include <bits/stdc++.h>
using namespace std;
#define maxn 300010

int X[maxn], Y[maxn], weight[maxn];
int n, maxcord;

vector <int> checkpoints[maxn];
vector < pair <int, int > > store[maxn];
vector <long long int> dp_1[maxn], dp_2[maxn], dp_3[maxn], dp_4[maxn];


/*

dp[i][1] --> i is in increasing range, right contribution not counted
dp[i][2] --> i is in decreasing range, right contribution not counted
dp[i][3] --> segment of i had ended, right contribution counted

*/


long long int st[8*maxn+10], lz[8*maxn+10];
int marked[8*maxn+10];

void push (int N, int L, int R){
	if (marked[N]){
		st[N]+=lz[N];
		int mid= (L+R)/2;
		if (L <= mid) {
			marked[2*N+1]=1;
			lz[2*N+1]+=lz[N];
		}
		if (mid+1<=R){
			marked[2*N+2]=1;
			lz[2*N+2]+=lz[N];
		}
		lz[N]=0;
		marked[N]=0;
	}
}

void upd (int N, int L, int R, int S, int E, long long int val){
	if (L>R) return;
	push (N, L, R);
	if (L>=S and R<=E){
		lz[N]=val;
		marked[N]=1;
		push(N, L, R);
		return;
	}
	if (L>E or S>R) return;
	int mid= (L+R)/2;
	upd (2*N+1, L, mid, S, E, val);
	upd (2*N+2, mid+1, R, S, E, val);
	st[N]= max(st[2*N+1], st[2*N+2]);
}

long long int query (int N, int L, int R, int S, int E){
	if (L>R) return -1;
	push(N, L, R);
	if (L>E or S>R) return -1;
	if (L>=S and R<=E) return st[N];
	int mid= (L+R)/2;
	return max (query (2*N+1, L, mid, S, E), query(2*N+2, mid+1, R, S, E));
}

vector < pair <int, int> > tmp;


void update_dp_1 (int pos){
	for (int i=0; i<checkpoints[pos-2].size(); i++){
		int y= checkpoints[pos-2][i];
		upd (0, 0, maxcord, y, y, dp_3[pos-2][i]);
	}

	tmp.clear();
	for (pair <int, int> p:store[pos-1]){
		tmp.push_back(p);
	}

	for (int i:checkpoints[pos]) tmp.push_back(make_pair(i,1));
	sort(tmp.begin(), tmp.end());
	int counter=0;
	for (pair <int, int> p:tmp){
		int y=p.first, w=-p.second;
		if (w>=0) upd (0, 0, maxcord, 0, y-1, w);
		else{
			dp_1[pos][counter]= max(dp_1[pos][counter], query(0, 0, maxcord, 0, maxcord));
			counter++;
		}
	}

	for (int i=0; i<checkpoints[pos-2].size(); i++){
		int y= checkpoints[pos-2][i];
		upd (0, 0, maxcord, y, y, -dp_3[pos-2][i]);
	}

	for (pair <int, int> p:tmp){
		int y=p.first, w=-p.second;
		if (w>=0) upd (0, 0, maxcord, 0, y-1, -w);
	
	}


}

void update_dp_2(int pos){
	for (int i=0; i<checkpoints[pos-1].size(); i++){
		int y= checkpoints[pos-1][i];
		upd (0, 0, maxcord, y, y, dp_1[pos-1][i]);
	}
	tmp.clear();
	for (pair <int, int> p:store[pos-1]) tmp.push_back(p);
	for (int i:checkpoints[pos]) tmp.push_back(make_pair(i,1));
	sort(tmp.begin(), tmp.end());
	int counter=0;
	for (pair <int, int> p:tmp){
		int y= p.first, w= -p.second;
		if (w>=0){
			upd (0, 0, maxcord, 0, y-1, w);
		}
		else{
			dp_1[pos][counter]= max(dp_1[pos][counter], query(0, 0, maxcord, 0, maxcord));
			counter++;
		}
	}	

	for (int i=0; i<checkpoints[pos-1].size(); i++){
		int y= checkpoints[pos-1][i];
		upd (0, 0, maxcord, y, y, -dp_1[pos-1][i]);
	}


	for (pair <int, int> p:tmp){
		int y= p.first, w= -p.second;
		if (w>=0){
			upd (0, 0, maxcord, 0, y-1, -w);
		}
	}	


}

void update_dp_3 (int pos){
	for (int i=0; i<checkpoints[pos].size(); i++) dp_2[pos][i]= dp_1[pos][i];

	int highest_checkpoint=0;	
	for (int i=0; i<checkpoints[pos-1].size(); i++){
		int y= checkpoints[pos-1][i];
		highest_checkpoint= max(highest_checkpoint, y);
		upd(0, 0, maxcord, y, y, dp_2[pos-1][i]);
	}	

	tmp.clear();

	for (pair <int, int> p:store[pos]) tmp.push_back(p);
	for (int i:checkpoints[pos]) tmp.push_back(make_pair(i,1));
	sort(tmp.begin(), tmp.end());
	reverse(tmp.begin(), tmp.end());
	int counter= checkpoints[pos].size()-1;
	for (pair <int, int> p:tmp){
		int y= p.first, w=-p.second;
		if (w>=0) {
			upd(0, 0, maxcord, y, maxcord, w);
		}
		else{
			
			if (pos>2) dp_2[pos][counter]= max(dp_2[pos][counter], query(0, 0, maxcord, 0, maxcord));
			counter--;
		}
	}	

	for (int i=0; i<checkpoints[pos-1].size(); i++){
		int y= checkpoints[pos-1][i];
		upd(0, 0, maxcord, y, y, -dp_2[pos-1][i]);
	}	

	for (pair <int, int> p:tmp){
		int y= p.first, w=-p.second;
		if (w>=0) upd(0, 0, maxcord, y, maxcord, -w);
		
	}	


}

void update_dp_4 (int pos){
	tmp.clear();
	for (pair<int,int> p:store[pos+1]) tmp.push_back(p);
	for (int i:checkpoints[pos]) {
		tmp.push_back(make_pair(i,1));
	}
	sort(tmp.begin(), tmp.end());
	long long int cur_sum=0;
	int counter=0;
	for (pair <int, int> p:tmp){
		int y=p.first, w=-p.second;
		if (w>=0) cur_sum+=w;
		else {
			dp_3[pos][counter]= dp_2[pos][counter]+cur_sum;
			counter++;
		}
	}


}


long long max_weights(int max_cord, int COUNT, std::vector<int> A, std::vector<int> B, std::vector<int> W){
	n=COUNT;
	maxcord=max_cord+2;
	for (int i=1; i<=n; i++){
		X[i]= A[i-1]+2;
		Y[i]= B[i-1]+2;
		weight[i]= W[i-1];
	}



	
	for (int i=1; i<=n; i++) store[X[i]].push_back(make_pair(Y[i], -weight[i]));
	for (int i=0; i<=maxcord; i++) sort(store[i].begin(), store[i].end());	

	for (int i=1; i<=n; i++){
		if (Y[i]>1) checkpoints[X[i]].push_back(Y[i]-1);
	}

	for (int i=0; i<=maxcord; i++) {
		checkpoints[i].push_back(0);
		if (i>=2) checkpoints[i].push_back(maxcord);
	}
	for (int i=0; i<=maxcord; i++) sort(checkpoints[i].begin(), checkpoints[i].end());	

	for (int i=0; i<=3; i++){
		for (int j=0; j<2*checkpoints[i].size(); j++){
			dp_1[i].push_back(0);
			dp_2[i].push_back(0);
			dp_3[i].push_back(0);
			dp_4[i].push_back(0);			
		}
	}




	for (int i=2; i<=maxcord; i++){

		/*for (int j=0; j<(int) checkpoints[i].size()+1; j++){
				if (i==5) cout<<"filling "<<j<<endl;
				dp_1[i].push_back(0);
				dp_2[i].push_back(0);
				dp_3[i].push_back(0);
				dp_4[i].push_back(0);				

		}*/
		int sz= (int) checkpoints[i].size()+1;
		dp_1[i].resize( sz );
		dp_2[i].resize(sz);
		dp_3[i].resize(sz);
		dp_4[i].resize(sz);
		for (int t=0; t<sz; t++){
			dp_1[i][t]=0;
			dp_2[i][t]=0;
			dp_3[i][t]=0;
			dp_4[i][t]=0;
		}
	/*	if (i>2){
			dp_1[i-3].clear();
			dp_2[i-3].clear();
			dp_3[i-3].clear();
			dp_4[i-3].clear();
		}*/
		update_dp_1(i);
		update_dp_2(i);
		update_dp_3(i);
		update_dp_4(i);
	}




	return dp_3[maxcord][0];

}

/*

int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> X(M), Y(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
  }
  long long int result = max_weights(N, M, X, Y, W);
  cout<<result<<endl;
  return 0;
}

*/

• Subtask 1: 0 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 0 / 16