RE 求调
查看原帖
RE 求调
1387479
LBY1145141919810楼主2025/7/22 17:21

我的代码在 init_dp() 调用线段树 Change 的时候 RE\color{purple}{RE} 了,一句指令都没有执行成功,求调。

菜鸡代码,码风垃圾,求轻喷。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll Inf=-1e16;
const int N=3e5+12;
using pi=pair<int,ll> ;
vector<pi> fish[N];
vector<pi> FISH[N];
vector<pi> dp[N];
int _n_,_m_;
vector<int> _x_;
vector<int> _y_;
vector<int> _w_;
inline void init_FISH(){
	for(int i=0;i<_n_;++i){
		FISH[i].emplace_back(Inf,0);
		ll sum=0;
		for(pi f:fish[i]){
			sum+=f.second;
			FISH[i].emplace_back(f.first,sum);
		}
	}
}
inline ll get_FISH(int rowid,int id){
	return lower_bound(FISH[rowid].begin(),FISH[rowid].end(),make_pair(id,-1ll))->second;
}
inline void init_dp_space(){
	for(int i=0;i<=_n_;i++){
		if(i!=0){
			for(pi f1:fish[i-1]){
				dp[i].emplace_back(f1.first,0);
			}
		}
		if(i!=_n_){
			for(pi f2:fish[i+1]){
				dp[i].emplace_back(f2.first,0);
			}
		}
		for(pi f3:fish[i]){
			dp[i].emplace_back(f3.first,0);
		}
	}
}
struct segment_tree{
	ll tr[N<<2];
	vector<int> trash;
	segment_tree(){
		fill(tr,tr+(N<<2)+1,Inf);
		trash.clear();
	}
	inline void upd(int k){
		tr[k]=max(tr[k<<1],tr[k<<1|1]);
	}
	inline void change(int k,int L,int R,int id,ll val){
		if(L==id&&id==R){
			tr[L]=val;
			return;
		}
		int mid=(L+R)>>1;
		if(id<=mid)change(k<<1,L,mid,id,val);
		else change(k<<1|1,mid+1,R,id,val);
		upd(k);
	}
	inline void Change(int id,ll val){
//		cout<<"CCF_NOI "<<id<<'\_n_';
		trash.emplace_back(id);
//		cout<<"1 0 "<<_n_<<" "<<id<<" "<<val<<endl;
		change(1,0,_n_,id,val);
	}
	inline ll quary(int k,int L,int R,int ql,int qr){
		if(ql<=L&&R<=qr){
			return tr[k];
		}
		int mid=(L+R)>>1;
		ll ans=Inf;
		if(ql<=mid)ans=max(ans,quary(k<<1,L,mid,ql,qr));
		if(qr>mid) ans=max(ans,quary(k<<1|1,mid+1,R,ql,qr));
		return ans;
	}
	inline ll Quary(int L,int R){
		return quary(1,0,_n_,L,R);
	}
	inline void Clear(){
		for(int f:trash)Change(f,Inf);
		trash.clear();
	}
}tr[2][2];
inline void init_dp(){
	for(pi &f:dp[0]){
		f.second=0;
//		cout<<"GF="<<get_FISH(1,f.first)<<' '<<f.first<<endl;
		tr[0][0].Change(f.first,f.second-get_FISH(1,f.first));
//		cout<<"GF="<<get_FISH(0,f.first-1)<<endl;
		tr[0][1].Change(f.first,f.second+get_FISH(0,f.first-1));
	}
}
ll max_weights(int n,int m,vector<int> x,vector<int> y,vector<int> w){
	_n_=n,_m_=m,_x_=x,_y_=y,_w_=w;
//	printf("E1\_n_");
	for(int i=0;i<_m_;++i){
		_y_[i]++;
		fish[_x_[i]].emplace_back(_y_[i],_w_[i]);
	}
//	printf("E2\_n_");
	fish[_n_].emplace_back(0,0);
	for(int i=0;i<=_n_;++i){
		sort(fish[i].begin(),fish[i].end());
	}
//	printf("E3\_n_");
	init_FISH();
//	printf("E4\_n_");
	init_dp_space();
//	printf("E5\_n_");
	
	init_dp();
//	printf("E6\_n_");
	for(int i=1;i<=_n_;i++){
		bool th=i&1,lst=th^1;
		for(pi &f:dp[i]){
			f.second=max(tr[lst][0].Quary(1,f.first)+get_FISH(i,f.second-1),tr[lst][1].Quary(f.first+1,_n_)-get_FISH(i-1,f.first));
			tr[th][0].Change(f.first,f.second-get_FISH(i,f.first));
			tr[th][1].Change(f.first,f.second+get_FISH(i-1,f.first));
		}
		tr[lst][0].Clear();
		tr[lst][1].Clear();
	}
//	printf("E7\_n_");
	return dp[_n_][0].second;
}
//int _n1,_m1;
//vector<int> _x1,_y1,_w1;
//int f;
//int main(){
//	cin>>_n1>>_m1;
//	for(int i=0;i<_m1;i++){
//		cin>>f;
//		_x1.emplace_back(f);
//	}
//	for(int i=0;i<_m1;i++){
//		cin>>f;
//		_y1.emplace_back(f);
//	}
//	for(int i=0;i<_m1;i++){
//		cin>>f;
//		_w1.emplace_back(f);
//	}
//	cout<<max_weights(_n1,_m1,_x1,_y1,_w1);
//	return 0;
//}
/*
5 4
0 1 4 3
2 1 4 3
5 2 1 3
*/
2025/7/22 17:21
加载中...