Submission #626097

#	Time	Username	Problem	Language	Result	Execution time	Memory
626097		errorgorn	Catfish Farm (IOI22_fish)	C++17	100 / 100	757 ms	212692 KiB

fish

#include "fish.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
struct node{
	int s,e,m;
	int val=0,lazy=0;
	node *l,*r;
 
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
 
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
 
	void propo(){
		if (lazy==0) return;
		val+=lazy;
		if (s!=e){
			l->lazy+=lazy;
			r->lazy+=lazy;
		}
		lazy=0;
	}
 
	void update(int i,int j,int k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
 
			l->propo(),r->propo();
			val=max(l->val,r->val);
		}
	}
} *root;
 
int n,m;
vector<ii> arr[100005];
vector<int> pos[100005];
vector<int> w[100005];
 
vector<int> memo[2][2];
 
int max_weights(signed N, signed M, vector<signed> X, vector<signed> Y,
                      vector<signed> W) {
 
 
	n=N,m=M;
	rep(x,0,m) arr[X[x]+1].pub({Y[x],W[x]});
 
	rep(x,0,n+2){
		if (x==0 || x==n+1) arr[x].pub({0,0});
		else arr[x].pub({n+1,0});
		sort(all(arr[x]));
 
		for (auto [a,b]:arr[x]){
			pos[x].pub(a);
			w[x].pub(b);
		}
	}
 
	int a=0,b=1;
	memo[a][0]=memo[a][1]={0};
 
	rep(idx,1,n+2){
		int ss1=sz(pos[idx-1]),ss2=sz(pos[idx]);
		memo[b][0]=vector<int>(ss2,0); //contribution counted
		memo[b][1]=vector<int>(ss2,0); //contribution not counted
 
		rep(i,0,2) rep(j,0,2){
			root=new node(0,ss1-1);
			rep(x,0,ss1) root->update(x,x,memo[a][i][x]);
 
			rep(y,0,sz(pos[idx])) if (j==0){
				int z=ub(all(pos[idx-1]),pos[idx][y])-pos[idx-1].begin();
				if (z<ss1) root->update(z,ss1-1,w[idx][y]);
			}
 
			int z=0;
			rep(y,0,sz(pos[idx])){
				if (i==1){
					while (z<sz(pos[idx-1]) && pos[idx-1][z]<pos[idx][y]){
						root->update(0,z,w[idx-1][z]);
						z++;
					}
				}
 
				root->propo();
				memo[b][j][y]=max(memo[b][j][y],root->val);
 
				if (j==0){
					int z=ub(all(pos[idx-1]),pos[idx][y])-pos[idx-1].begin();
					if (z<ss1) root->update(z,ss1-1,-w[idx][y]);
				}
			}
		}
 
		swap(a,b);
 
		//cout<<"idx: "<<idx<<endl;
		//for (auto it:memo[a][0]) cout<<it<<" "; cout<<endl;
		//for (auto it:memo[a][1]) cout<<it<<" "; cout<<endl;
	}
 
	return memo[a][0][0];
}

Compilation message (stderr)

fish.cpp: In constructor 'node::node(long long int, long long int)':
fish.cpp:30:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

• Subtask 1: 3 / 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: 16 / 16