WA #4~#9 MnZn 求调
查看原帖
WA #4~#9 MnZn 求调
542905
WannaYellow楼主2022/11/22 17:36
#include<bits/stdc++.h>

using i8=char;		using u8=unsigned char;
using i16=short;	using u16=unsigned short;
using i32=int;		using u32=unsigned int;
using i64=long long;using u64=unsigned long long;
using i128=__int128;using u128=unsigned __int128;
using f32=float; 	using f64=double;				using f128=long double;

template<typename T> inline void read(T &x){
	char ch=getchar(),f=0;
	x=0;
	while(ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9')(x=x*10+(ch-'0')),ch=getchar();
	x=(f?-x:x);
}
template<typename T,typename ...Ts> void read(T &x,Ts &...xs){read(x); read(xs...); }
char fostk[50]; u8 cntfostk;
template<typename T> inline void write(T x){
	if(x<0)putchar('-'),x=-x;
	while(x>9)fostk[++cntfostk]='0'+x%10,x/=10;
	fostk[++cntfostk]=x+'0';
	while(cntfostk)putchar(fostk[cntfostk--]);
}
template<typename T> void writesp(T x){write(x); putchar(' '); }
template<typename T> void writeln(T x){write(x); putchar('\n'); }
template<typename T> void writelns(T x){writeln(x); }
template<typename T,typename ...Ts> void write(T x,Ts ...xs){writesp(x); write(xs...); }
template<typename T,typename ...Ts> void writeln(T x,Ts ...xs){write(x,xs...); putchar('\n'); }
template<typename T,typename ...Ts> void writelns(T x,Ts ...xs){writeln(x); writelns(xs...); }
#define i32 i64
i32 n,w,h;
struct Segment{
	i32 l,r,h,f;
	friend bool operator<(const Segment &x,const Segment &y){
		return x.h<y.h;
	}
}s[20005];
i32 cntline,lsh[20005],lshlen;
void addline(i32 x,i32 y,i32 v){
	s[++cntline]={
		x,x+w,y,v
	};
	lsh[cntline]=x;
	s[++cntline]={
		x,x+w,y+h,-v
	};
	lsh[cntline]=x+w;
}
void init(){
	cntline=0;
	read(n,w,h);
	w--,h--;
	for(i32 i=1;i<=n;i++){
		i32 x,y,v;
		read(x,y,v);
		addline(x,y,v);
	}
	std::sort(lsh+1,lsh+1+cntline);
	lshlen=std::unique(lsh+1,lsh+1+cntline)-lsh-1;
	for(i32 i=1;i<=cntline;i++){
		s[i].l=std::lower_bound(lsh+1,lsh+1+lshlen,s[i].l)-lsh;
		s[i].r=std::lower_bound(lsh+1,lsh+1+lshlen,s[i].r)-lsh;
	}
	std::sort(s+1,s+1+cntline);
	// for(i32 i=1;i<=cntline;i++){
	// 		fprintf(stderr,"s[i:%d]={l:%d,r:%d,h:%d,f:%d}\n",
	// 			i,s[i].l,s[i].r,s[i].h,s[i].f);
	// 		fflush(stderr);
	// }putc('\n',stderr);
}
struct SegmentTree{
	struct Node{
		i32 lz,max;
	}nod[20004<<2];
	inline i32 ls(i32 x){return x<<1; }
	inline i32 rs(i32 x){return x<<1|1; }
	#define mid ((l+r)>>1)
	void build(i32 x,i32 l,i32 r){
		if(l==r){nod[x]={0,0}; return; }
		build(ls(x),l,mid);
		build(rs(x),mid+1,r);
	}
	void add(i32 x,i32 l,i32 r,i32 k){
		nod[x].max+=k;
		nod[x].lz+=k;
	}
	void push_down(i32 x,i32 l,i32 r){
		if(nod[x].lz){
			add(ls(x),l,mid,nod[x].lz);
			add(rs(x),mid+1,r,nod[x].lz);
			nod[x].lz=0;
		}
	}
	void update(i32 x){
		nod[x].max=std::max(nod[ls(x)].max,nod[rs(x)].max);
	}
	void modify(i32 x,i32 l,i32 r,i32 ml,i32 mr,i32 k){
		if(ml<=l&&r<=mr)add(x,l,r,k);
		else{
			push_down(x,l,r);
			if(ml<=mid)modify(ls(x),l,mid,ml,mr,k);
			if(mr>mid)modify(rs(x),mid+1,r,ml,mr,k);
			update(x);
		}
	}
	i32 query(){
		return nod[1].max;
	}
}T;
i32 calc(){
	i32 re=0;
	T.build(1,1,lshlen);
	for(i32 i=1;i<=cntline;i++){
		T.modify(1,1,lshlen,s[i].l,s[i].r,s[i].f);
		re=std::max(re,T.query());
	}
	return re;
}
void solve(){
	init();
	writeln(calc());
}
int main(){
#ifdef LOCAL
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	freopen("test.err","w",stderr);
#endif
	i32 t;
	read(t);
	while(t--){
		solve();
	}
	return 0;
}
2022/11/22 17:36
加载中...