四分树求卡常
查看原帖
四分树求卡常
602803
_qingshu_楼主2024/6/25 14:13

前面的是快读,然后感觉能加的都加了....

#include<bits/stdc++.h>
namespace Fread{
const long long SIZE=1<<21;
	char buf[SIZE],*S,*T;
	inline char getchar(){
		if (S==T){
			T=(S=buf)+fread(buf,1,SIZE,stdin);
			if(S==T){
				return '\n';
			}
		}
		return *S++;
	}
}	
namespace Fwrite{
	const long long SIZE=1<<21;
	char buf[SIZE],*S=buf,*T=buf+SIZE;
	inline void flush(){
		fwrite(buf,1,S-buf,stdout);
		S=buf;
	}
	inline void putchar(char c){
		*S++=c;
		if(S==T){
			flush();
		}
	}
	struct NTR{
		~NTR(){
			flush();
		}
	}ztr;
} 
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
	struct Reader{
		template<typename T>
		Reader& operator>>(T& x){
			char c=getchar();
			T f=1;
			while (c<'0'||c>'9'){
				if (c=='-') f=-1;
				c=getchar();
			}
			x=0;
			while (c>='0'&&c<='9'){
				x=x*10+(c-'0');
				c=getchar();
			}
			x*=f;
			return *this;
		}
		Reader& operator>>(char& c){
			c=getchar();
			while (c==' '||c=='\n'){
				c=getchar();
			}
			return *this;
		}
		Reader& operator>>(char* str){
			long long len=0;
			char c=getchar();
			while (c==' '||c=='\n'){
				c=getchar();
			}
			while (c!=' '&&c!='\n'&&c!='\r'){ 
				str[len++]=c;
				c=getchar();
			}
			str[len]='\0';
			return *this;
		}
		Reader(){}
	}cin;
	const char endl='\n';
	struct Writer{
		template<typename T>
		Writer&operator<<(T x){
			if(x==0){
				putchar('0');
				return *this;
			}
			if(x<0){
				putchar('-');
				x=-x;
			}
			static long long sta[45];
			long long top=0;
			while(x){
				sta[++top]=x%10;
				x/=10;
			}
			while(top){
				putchar(sta[top]+'0');
				--top;
			}
			return *this;
		}
		Writer& operator<<(char c){
			putchar(c);
			return *this;
		}
		Writer& operator<<(char* str){
			long long cur=0;
			while(str[cur]){
				putchar(str[cur++]);
			}
			return *this;
		}
		Writer& operator<<(const char* str){
			long long cur=0;
			while(str[cur]){
				putchar(str[cur++]);
			}
			return *this;
		}
		Writer(){}
	}cout;
}
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
#define son1 ((id<<2)-2)
#define son2 ((id<<2)-1)
#define son3 (id<<2)
#define son4 ((id<<2)+1)
using namespace std;
int D,S,N,d,s,w,x,y,Max[20000010],lz[20000010],V;
inline void modify(int id,int Lef,int Rig,int Up,int Down,int lef,int rig,int up,int down,int fixnum){
	if(Lef>rig||Rig<lef||Up<down||Down>up)return;
	if(Lef>=lef&&Rig<=rig&&Up<=up&&Down>=down){
		Max[id]=lz[id]=fixnum;return;}
	modify(son1,Lef,Lef+Rig>>1,Up+Down>>1,Down,lef,rig,up,down,fixnum);
	modify(son2,(Lef+Rig>>1)+1,Rig,Up+Down>>1,Down,lef,rig,up,down,fixnum);
	modify(son3,Lef,Lef+Rig>>1,Up,(Up+Down>>1)+1,lef,rig,up,down,fixnum);
	modify(son4,(Lef+Rig>>1)+1,Rig,Up,(Up+Down>>1)+1,lef,rig,up,down,fixnum);
	Max[id]=max(Max[id],fixnum);
}
inline void query(int id,int Lef,int Rig,int Up,int Down,int lef,int rig,int up,int down){
	if(Lef>rig||Rig<lef||Up<down||Down>up)return;
	if(Lef>=lef&&Rig<=rig&&Up<=up&&Down>=down){V=max(Max[id],V);return;}
	V=max(lz[id],V);
	query(son1,Lef,Lef+Rig>>1,Up+Down>>1,Down,lef,rig,up,down);
	query(son2,(Lef+Rig>>1)+1,Rig,Up+Down>>1,Down,lef,rig,up,down);
	query(son3,Lef,Lef+Rig>>1,Up,(Up+Down>>1)+1,lef,rig,up,down);
	query(son4,(Lef+Rig>>1)+1,Rig,Up,(Up+Down>>1)+1,lef,rig,up,down);
}
main(){
	cin>>D>>S>>N;
	for(int i=1;i<=N;i++,V=0){
		cin>>d>>s>>w>>x>>y;
		query(1,0,D-1,S-1,0,x,x+d-1,y+s-1,y);
		modify(1,0,D-1,S-1,0,x,x+d-1,y+s-1,y,V+w);
	}cout<<Max[1];
}
2024/6/25 14:13
加载中...