文件详细信息

下载本文件

本文件的大小为 2241 字节。

#include<cstdio>
#include<cstring>
#include<vector>
namespace IO{
	const int ARR_SIZE=300000;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt;
		if(a==0)pc('0');
		cnt=0;
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
void chkmax(int&a,const int b){
	a<b&&(a=b);
}
const int maxq=15005,maxlogq=20,maxv=15005;
int q,_maxv,T;
struct Answer{
	int e,maxw;
};
int f[maxlogq][maxv];
struct Item{
	int cost,val;
};
std::vector<Item>g[maxq<<2];
bool vis[maxq<<2];
void modify(int u,int l,int r,int ql,int qr,int cost,int val,int dep){
	if(ql<=l&&r<=qr){
		g[u].push_back(Item{cost,val});
		return;
	}
	int m=(l+r)>>1;
	if(m>=ql)modify(u<<1,l,m,ql,qr,cost,val,dep+1);
	if(m<qr)modify(u<<1|1,m+1,r,ql,qr,cost,val,dep+1);
	return;
}
Answer query(int u,int l,int r,int x,int val,int dep){
	while(true){
		if(!vis[u]){
			memcpy(f[dep],f[dep-1],sizeof(int)*(_maxv+1));
			for(Item p:g[u])
				for(int i=maxv;i>=p.cost;i--)
					chkmax(f[dep][i],f[dep][i-p.cost]+p.val);
			vis[u]=true;
		}
		if(l==r)return Answer{f[dep][val]>=0?1:0,f[dep][val]>=0?f[dep][val]:0};
		int m=(l+r)>>1;
		if(x<=m){
			u=u<<1;
			r=m;
		}else{
			u=u<<1|1;
			l=m+1;
		}
		dep++;
	}
}
int main(){
	read(q),read(_maxv),read(T);
	memset(f[0],192,sizeof(int)*(_maxv+1));
	f[0][0]=0;
	int op,v,w,e,d=0;
	for(int i=1;i<=q;i++){
		read(op),read(v);
		v-=d;
		if(op==1){
			read(w),read(e);
			w-=d,e-=d;
			modify(1,1,q,i,e,v,w,1);
		}else{
			Answer ans=query(1,1,q,i,v,1);
			write(ans.e),pc(' '),write(ans.maxw),pc('\n');
			if(T)d=ans.e^ans.maxw;
		}
	}
	return 0;
}