QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#770336	#4407. 回	I_be_wanna	100 ✓	5446ms	59060kb	C++20	11.5kb	2024-11-21 21:29:20	2024-11-21 21:29:21

Judging History

你现在查看的是最新测评结果

[2024-11-21 21:29:21]
评测

测评结果：100
用时：5446ms
内存：59060kb

查看

[2024-11-21 21:29:20]
提交

answer

#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<r;++i)
#define Fe(i,l,r) for(int i=l;i<=r;++i)
#define N 1000010
#define maxm 1000000
#define maxv 100000000
int read(int L,int R){
	int x;
	assert(scanf("%d",&x)==1);
	assert(L<=x&&x<=R);
	return x;
}
char pool[67108864],*pool_p=pool;
template<class T>
void alloc(T *&p,int sz){
	p=reinterpret_cast<T*>(pool_p);
	pool_p+=sz*sizeof(T);
	assert(pool_p<pool+67108864);
	F(i,0,sz)new(p+i)T();
}

template<class T>
struct Undo{
	T &x;
	T x0;
	Undo(T &x):x(x),x0(x){}
	~Undo(){x=x0;}
};

#define alloc_scope Undo<char*> _##__LINE__(pool_p)



template<class T>
struct BIT{
	T *a;
	int n;
	void alloc(int n0){
		n=n0;
		::alloc(a,n+1);
	}
	void add(int x,T y){
		int _n=n;
		for(;x<=_n;x+=x&-x)a[x]+=y;
	}
	T sum(int x){
		T s;
		s=0;
		for(;x;x-=x&-x)s+=a[x];
		return s;
	}
};

template<class T,int n>
struct Vec{
	T v[n];
	void operator=(T x){
		F(i,0,n)v[i]=x;
	}
	Vec operator+(const Vec &w)const{
		Vec c;
		F(i,0,n)c.v[i]=v[i]+w.v[i];
		return c;
	}
	void operator+=(const Vec &w){
		F(i,0,n)v[i]+=w.v[i];
	}
	T operator*(const Vec &w)const{
		T s=0;
		F(i,0,n)s+=v[i]*w.v[i];
		return s;
	}
	friend Vec operator*(T x,const Vec &w){
		Vec c;
		F(i,0,n)c.v[i]=x*w.v[i];
		return c;
	}
};

template<class T,int n1,int n2>
Vec<T,n1+n2> operator&(const Vec<T,n1> &a,const Vec<T,n2> &b){
	Vec<T,n1+n2> c;
	F(i,0,n1)c.v[i]=a.v[i];
	F(i,0,n2)c.v[i+n1]=b.v[i];
	return c;
}

template<class T>
struct Pos{
	int x,y,id;
	T v;
};

std::vector<Pos<Vec<unsigned,6>>> t1;
std::vector<Pos<Vec<unsigned,4>>> t2;
std::vector<Pos<Vec<unsigned,6>>> t3;
int qp=0;
unsigned ans[N];

template<class T>
void solve(Pos<T> *a,int n){
	if(n<=40){
		F(i,0,n)if(a[i].id){
			F(j,0,i)if(!a[j].id){
				if(a[j].x<a[i].x&&a[j].y<a[i].y){
					ans[a[i].id]+=a[i].v*a[j].v;
				}
			}
		}
		std::sort(a,a+n,[](const Pos<T> &a,const Pos<T> &b){return a.x<b.x;});
		return;
	}
	alloc_scope;
	
	int n2=n/2;
	solve(a,n2);
	solve(a+n2,n-n2);
	
	int *ys,yp=0;
	alloc(ys,n2);
	F(i,0,n2)if(!a[i].id)ys[yp++]=a[i].y;
	std::sort(ys,ys+yp);
	
	BIT<T> bit;
	
	bit.alloc(yp);
	
	Pos<T> *b;
	alloc(b,n);
	int p1=0,p2=n2,p3=0;
	auto f1=[&]{
		if(!a[p1].id){
			int y=std::lower_bound(ys,ys+yp,a[p1].y)-ys+1;
			bit.add(y,a[p1].v);
		}
		b[p3++]=a[p1++];
	};
	auto f2=[&]{
		if(a[p2].id){
			int y=std::upper_bound(ys,ys+yp,a[p2].y)-ys;
			ans[a[p2].id]+=bit.sum(y)*a[p2].v;
		}
		b[p3++]=a[p2++];
	};
	while(p1<n2&&p2<n){
		if(a[p1].x<=a[p2].x)f1();
		else f2();
	}
	while(p1<n2)f1();
	while(p2<n)f2();
	std::copy(b,b+n,a);
}


int tp;
int mat[8][4]={
	{+1,0, 0,-1},
	{+1,0, 0,+1},
	{-1,0, 0,-1},
	{-1,0, 0,+1},
	{0,+1, -1,0},
	{0,+1, +1,0},
	{0,-1, -1,0},
	{0,-1, +1,0}};
using std::swap;
struct M{
	int x,y;
	unsigned v,sgn;
};
std::vector<M> ms;
void f1b(int x0,int y0,unsigned mv,unsigned sgn){
	ms.push_back(M{x0,y0,mv,sgn});
	{
		unsigned my=y0;
		auto vec=sgn*Vec<unsigned,4>{
			my*my*my+(3+mv*3)*my*my+(2+mv*3)*my,
			-3*my*my+(3+mv*3)*-2*my-(2+mv*3),
			3*my+(3+mv*3),
			-1u,
		};
		t2.push_back({-x0*2,-y0*2,0,vec});
	}
	{
		unsigned mx=x0+y0,my=x0;
		auto vec=sgn*Vec<unsigned,6>{
			mx*mx*mx+(3+3*mv-3*my)*mx*mx+(2+3*mv-3*my)*mx,
			-3*mx*mx-2*(3+3*mv-3*my)*mx+-(2+3*mv-3*my)*1,
			3*mx+(3+3*mv-3*my)*1,
			1,
			mx,
			mx*mx,
		};
		t3.push_back({-(x0+y0)*2,x0*2,0,vec});
	}
}
void f1c(int x0,int y0,unsigned mv,unsigned sgn){
	unsigned my=y0,mx=x0;
	auto vec=(sgn*3)*Vec<unsigned,6>{
	(mv*2+1)*my*mx-my*mx*mx,
	-(mv*2+1)*my+2*my*mx,
	-(mv*2+1)*mx+mx*mx,
	(mv*2+1)-2*mx,
	1,
	-my};
	t1.push_back({-x0*2,-y0*2,0,vec});
}
bool flag=1;
void f1a(int x0,int y0,int d,unsigned v){
	int x1=mat[tp][0];
	int y1=mat[tp][1];
	int x2=mat[tp][2];
	int y2=mat[tp][3];
	if(y1)swap(x1,y1),swap(x2,y2),swap(x0,y0);
	x0*=x1;
	y0*=y2;
	f1b(x0,y0+d-1,0,v);
	f1b(x0+d,y0-1,d,-v);
	f1c(x0+d-1,y0-1,d,-v);
	f1c(x0-1,y0-1,0,v);
}
void f1(int x,int y,int d,unsigned v){
	switch(tp){
	case 0:f1a(x-d,y-1, d,v);break;
	case 1:f1a(x-d,y  , d+1,v);break;
	case 2:f1a(x+d,y-1, d-1,v);break;
	case 3:f1a(x+d,y  , d,v);break;
	case 4:f1a(x  ,y-d, d,v);break;
	case 5:f1a(x+1,y-d, d,v);break;
	case 6:f1a(x  ,y+d, d,v);break;
	case 7:f1a(x+1,y+d, d,v);break;
	}
}
void f2b(int X1,int Y1,unsigned sgn){
	int x=X1,y=Y1;
	{
		unsigned y1=y-1;
		auto vec=sgn*Vec<unsigned,4>{1,y1,y1*y1,y1*y1*y1};
		t2.push_back({-x*2+1,-y*2+1,qp,vec});
	}
	{
		unsigned x1=x+y-1,y1=x;
		auto vec=sgn*Vec<unsigned,6>{1,x1,x1*x1,-x1*x1*x1+y1*3*x1*(x1-1),y1*3*(1-2*x1),y1*3,};
		t3.push_back({-(x+y)*2+1,(x-1)*2+1,qp,vec});
	}
	{
		unsigned y1=y-1,x1=x-1;
		auto vec=sgn*Vec<unsigned,6>{1,x1,y1,x1*y1,y1*x1*x1,x1*x1};
		t1.push_back({-x*2+1,-y*2+1,qp,vec});
	}
}
void f2a(int X1,int X2,int Y1,int Y2){
	int x1=mat[tp][0];
	int y1=mat[tp][1];
	int x2=mat[tp][2];
	int y2=mat[tp][3];
	if(y1)swap(x1,y1),swap(x2,y2),swap(X1,Y1),swap(X2,Y2);
	X1*=x1,X2*=x1;
	if(X1>X2)swap(X1,X2);
	Y1*=y2,Y2*=y2;
	if(Y1>Y2)swap(Y1,Y2);
	
	f2b(X1,Y1,1);
	f2b(X1,Y2+1,-1);
	f2b(X2+1,Y1,-1);
	f2b(X2+1,Y2+1,1);
}
struct Q{
	int o,a,b,c,d;
}qs[N];
unsigned mod(unsigned x){
	x>>=1;
	unsigned P=1u<<30;
	x&=P-1u;
	while(x%3u)x+=P;
	return x/3u;
}
int main(){
	int m=read(1,maxm);
	F(_,0,m){
		int o=read(1,2);
		if(o==1){
			int x=read(1,maxv),y=read(1,maxv),d=read(1,maxv);
			int v=read(1,maxv);
			qs[_]=Q{1,x,y,d-1,v};
		}else{
			int x1=read(1,maxv),x2=read(x1,maxv);
			int y1=read(1,maxv),y2=read(y1,maxv);
			qs[_]=Q{2,x1,x2,y1,y2};
		}
	}
	F(i,0,8){
		t1.clear();
		t2.clear();
		t3.clear();
		
		ms.clear();
		
		tp=i;
		qp=0;
		F(_,0,m){
			Q &q=qs[_];
			if(q.o==1)f1(q.a,q.b,q.c,q.d);
			else{
				++qp;
				f2a(q.a,q.b,q.c,q.d);
			}
		}
		solve(t1.data(),t1.size());
		solve(t2.data(),t2.size());
		solve(t3.data(),t3.size());
	}
	Fe(_,1,qp)printf("%u\n",mod(ans[_]));
	return 0;
}
/*#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<r;++i)
#define Fe(i,l,r) for(int i=l;i<=r;++i)
#define N 1000010
#define maxm 1000000
#define maxv 100000000
int read(int L,int R){
	int x;
	assert(scanf("%d",&x)==1);
	assert(L<=x&&x<=R);
	return x;
}
char pool[67108864],*pool_p=pool;
template<class T>
void alloc(T *&p,int sz){
	p=reinterpret_cast<T*>(pool_p);
	pool_p+=sz*sizeof(T);
	assert(pool_p<pool+67108864);
	F(i,0,sz)new(p+i)T();
}

template<class T>
struct Undo{
	T &x;
	T x0;
	Undo(T &x):x(x),x0(x){}
	~Undo(){x=x0;}
};

#define alloc_scope Undo<char*> _##__LINE__(pool_p)



template<class T>
struct BIT{
	T *a;
	int n;
	void alloc(int n0){
		n=n0;
		::alloc(a,n+1);
	}
	void add(int x,T y){
		int _n=n;
		for(;x<=_n;x+=x&-x)a[x]+=y;
	}
	T sum(int x){
		T s;
		s=0;
		for(;x;x-=x&-x)s+=a[x];
		return s;
	}
};

template<class T,int n>
struct Vec{
	T v[n];
	void operator=(T x){
		F(i,0,n)v[i]=x;
	}
	Vec operator+(const Vec &w)const{
		Vec c;
		F(i,0,n)c.v[i]=v[i]+w.v[i];
		return c;
	}
	void operator+=(const Vec &w){
		F(i,0,n)v[i]+=w.v[i];
	}
	T operator*(const Vec &w)const{
		T s=0;
		F(i,0,n)s+=v[i]*w.v[i];
		return s;
	}
	friend Vec operator*(T x,const Vec &w){
		Vec c;
		F(i,0,n)c.v[i]=x*w.v[i];
		return c;
	}
};

template<class T,int n1,int n2>
Vec<T,n1+n2> operator&(const Vec<T,n1> &a,const Vec<T,n2> &b){
	Vec<T,n1+n2> c;
	F(i,0,n1)c.v[i]=a.v[i];
	F(i,0,n2)c.v[i+n1]=b.v[i];
	return c;
}

template<class T>
struct Pos{
	int x,y,id;
	T v;
};

std::vector<Pos<Vec<unsigned,6>>> t1;
std::vector<Pos<Vec<unsigned,4>>> t2;
std::vector<Pos<Vec<unsigned,6>>> t3;
int qp=0;
unsigned ans[N];

template<class T>
void solve(Pos<T> *a,int n){
	if(n<=40){
		F(i,0,n)if(a[i].id){
			F(j,0,i)if(!a[j].id){
				if(a[j].x<a[i].x&&a[j].y<a[i].y){
					ans[a[i].id]+=a[i].v*a[j].v;
				}
			}
		}
		std::sort(a,a+n,[](const Pos<T> &a,const Pos<T> &b){return a.x<b.x;});
		return;
	}
	alloc_scope;
	
	int n2=n/2;
	solve(a,n2);
	solve(a+n2,n-n2);
	
	int *ys,yp=0;
	alloc(ys,n2);
	F(i,0,n2)if(!a[i].id)ys[yp++]=a[i].y;
	std::sort(ys,ys+yp);
	
	BIT<T> bit;
	
	bit.alloc(yp);
	
	Pos<T> *b;
	alloc(b,n);
	int p1=0,p2=n2,p3=0;
	auto f1=[&]{
		if(!a[p1].id){
			int y=std::lower_bound(ys,ys+yp,a[p1].y)-ys+1;
			bit.add(y,a[p1].v);
		}
		b[p3++]=a[p1++];
	};
	auto f2=[&]{
		if(a[p2].id){
			int y=std::upper_bound(ys,ys+yp,a[p2].y)-ys;
			ans[a[p2].id]+=bit.sum(y)*a[p2].v;
		}
		b[p3++]=a[p2++];
	};
	while(p1<n2&&p2<n){
		if(a[p1].x<=a[p2].x)f1();
		else f2();
	}
	while(p1<n2)f1();
	while(p2<n)f2();
	std::copy(b,b+n,a);
}


int tp;
int mat[8][4]={
	{+1,0, 0,-1},
	{+1,0, 0,+1},
	{-1,0, 0,-1},
	{-1,0, 0,+1},
	{0,+1, -1,0},
	{0,+1, +1,0},
	{0,-1, -1,0},
	{0,-1, +1,0}};
using std::swap;
struct M{
	int x,y;
	unsigned v,sgn;
};
std::vector<M> ms;
void f1b(int x0,int y0,unsigned mv,unsigned sgn){
	ms.push_back(M{x0,y0,mv,sgn});
	{
		unsigned my=y0;
		auto vec=sgn*Vec<unsigned,4>{
			my*my*my+(3+mv*3)*my*my+(2+mv*3)*my,
			-3*my*my+(3+mv*3)*-2*my-(2+mv*3),
			3*my+(3+mv*3),
			-1u,
		};
		t2.push_back({-x0*2,-y0*2,0,vec});
	}
	{
		unsigned mx=x0+y0,my=x0;
		auto vec=sgn*Vec<unsigned,6>{
			mx*mx*mx+(3+3*mv-3*my)*mx*mx+(2+3*mv-3*my)*mx,
			-3*mx*mx-2*(3+3*mv-3*my)*mx+-(2+3*mv-3*my)*1,
			3*mx+(3+3*mv-3*my)*1,
			1,
			mx,
			mx*mx,
		};
		t3.push_back({-(x0+y0)*2,x0*2,0,vec});
	}
}
void f1c(int x0,int y0,unsigned mv,unsigned sgn){
	unsigned my=y0,mx=x0;
	auto vec=(sgn*3)*Vec<unsigned,6>{
	(mv*2+1)*my*mx-my*mx*mx,
	-(mv*2+1)*my+2*my*mx,
	-(mv*2+1)*mx+mx*mx,
	(mv*2+1)-2*mx,
	1,
	-my};
	t1.push_back({-x0*2,-y0*2,0,vec});
}
bool flag=1;
void f1a(int x0,int y0,int d,unsigned v){
	int x1=mat[tp][0];
	int y1=mat[tp][1];
	int x2=mat[tp][2];
	int y2=mat[tp][3];
	if(y1)swap(x1,y1),swap(x2,y2),swap(x0,y0);
	x0*=x1;
	y0*=y2;
	f1b(x0,y0+d-1,0,v);
	f1b(x0+d,y0-1,d,-v);
	f1c(x0+d-1,y0-1,d,-v);
	f1c(x0-1,y0-1,0,v);
}
void f1(int x,int y,int d,unsigned v){
	switch(tp){
	case 0:f1a(x-d,y-1, d,v);break;
	case 1:f1a(x-d,y  , d+1,v);break;
	case 2:f1a(x+d,y-1, d-1,v);break;
	case 3:f1a(x+d,y  , d,v);break;
	case 4:f1a(x  ,y-d, d,v);break;
	case 5:f1a(x+1,y-d, d,v);break;
	case 6:f1a(x  ,y+d, d,v);break;
	case 7:f1a(x+1,y+d, d,v);break;
	}
}
void f2b(int X1,int Y1,unsigned sgn){
	int x=X1,y=Y1;
	{
		unsigned y1=y-1;
		auto vec=sgn*Vec<unsigned,4>{1,y1,y1*y1,y1*y1*y1};
		t2.push_back({-x*2+1,-y*2+1,qp,vec});
	}
	{
		unsigned x1=x+y-1,y1=x;
		auto vec=sgn*Vec<unsigned,6>{1,x1,x1*x1,-x1*x1*x1+y1*3*x1*(x1-1),y1*3*(1-2*x1),y1*3,};
		t3.push_back({-(x+y)*2+1,(x-1)*2+1,qp,vec});
	}
	{
		unsigned y1=y-1,x1=x-1;
		auto vec=sgn*Vec<unsigned,6>{1,x1,y1,x1*y1,y1*x1*x1,x1*x1};
		t1.push_back({-x*2+1,-y*2+1,qp,vec});
	}
}
void f2a(int X1,int X2,int Y1,int Y2){
	int x1=mat[tp][0];
	int y1=mat[tp][1];
	int x2=mat[tp][2];
	int y2=mat[tp][3];
	if(y1)swap(x1,y1),swap(x2,y2),swap(X1,Y1),swap(X2,Y2);
	X1*=x1,X2*=x1;
	if(X1>X2)swap(X1,X2);
	Y1*=y2,Y2*=y2;
	if(Y1>Y2)swap(Y1,Y2);
	
	f2b(X1,Y1,1);
	f2b(X1,Y2+1,-1);
	f2b(X2+1,Y1,-1);
	f2b(X2+1,Y2+1,1);
}
struct Q{
	int o,a,b,c,d;
}qs[N];
unsigned mod(unsigned x){
	x>>=1;
	unsigned P=1u<<30;
	x&=P-1u;
	while(x%3u)x+=P;
	return x/3u;
}
int main(){
	int m=read(1,maxm);
	F(_,0,m){
		int o=read(1,2);
		if(o==1){
			int x=read(1,maxv),y=read(1,maxv),d=read(1,maxv);
			int v=read(1,maxv);
			qs[_]=Q{1,x,y,d-1,v};
		}else{
			int x1=read(1,maxv),x2=read(x1,maxv);
			int y1=read(1,maxv),y2=read(y1,maxv);
			qs[_]=Q{2,x1,x2,y1,y2};
		}
	}
	return 0;
}*/

Source code, Language: C++20

Details

Subtask #1:

score: 23

Accepted

Test #1:

score: 23

Accepted

time: 19ms

memory: 4332kb

Test #2:

score: 23

Accepted

time: 21ms

memory: 4584kb

Subtask #2:

score: 8

Accepted

Test #3:

score: 8

Accepted

time: 791ms

memory: 15608kb

Test #4:

score: 8

Accepted

time: 839ms

memory: 14168kb

Subtask #3:

score: 8

Accepted

Test #5:

score: 8

Accepted

time: 1771ms

memory: 23556kb

Test #6:

score: 8

Accepted

time: 1893ms

memory: 23768kb

Subtask #4:

score: 8

Accepted

Test #7:

score: 8

Accepted

time: 2853ms

memory: 35768kb

Test #8:

score: 8

Accepted

time: 3000ms

memory: 37980kb

Subtask #5:

score: 8

Accepted

Test #9:

score: 8

Accepted

time: 3976ms

memory: 42636kb

Test #10:

score: 8

Accepted

time: 4210ms

memory: 43452kb

Subtask #6:

score: 15

Accepted

Test #11:

score: 15

Accepted

time: 4043ms

memory: 54612kb

Test #12:

score: 15

Accepted

time: 4739ms

memory: 45028kb

Subtask #7:

score: 10

Accepted

Test #13:

score: 10

Accepted

time: 4483ms

memory: 54112kb

Test #14:

score: 10

Accepted

time: 4392ms

memory: 54776kb

Subtask #8:

score: 10

Accepted

Test #15:

score: 10

Accepted

time: 4941ms

memory: 57356kb

Test #16:

score: 10

Accepted

time: 5190ms

memory: 59060kb

Subtask #9:

score: 10

Accepted

Test #17:

score: 10

Accepted

time: 5131ms

memory: 54880kb

Test #18:

score: 10

Accepted

time: 5446ms

memory: 53428kb