QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#669959#7451. TB5Xzjy00010 0ms0kbC++176.3kb2024-10-23 20:07:072024-10-23 20:07:07

Judging History

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

  • [2024-10-23 20:07:07]
  • 评测
  • 测评结果：0
  • 用时：0ms
  • 内存：0kb
查看
  • [2024-10-23 20:07:07]
  • 提交

answer

#include"data.h"
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=1e5+5,BL=250,M=BL*4+5;
int n;
Data C[N],D[N];
int x_1[N],x_2[N],y_1[N],y_2[N];
int A[N],B[N],idx[N],idy[N];
vector<pair<int,int>>Tx[M],Ty[M];
inline void init(vector<pair<int,int>>&X,int x,int y){
	X.clear(),X.emplace_back(0,x-1),X.emplace_back(y,n-1),X.emplace_back(x,y-1);
}
inline void pushup(vector<pair<int,int>>L,vector<pair<int,int>>R,vector<pair<int,int>>&X){
	vector<pair<int,int>>Y=R,Z;
	sort(Y.begin(),Y.end());
	int p=0,q=-1;
	for(auto [l,r]:Y){
		for(;p<L.size()&&q+L[p].second-L[p].first+1<=r;++p)
			q+=L[p].second-L[p].first+1,Z.emplace_back(L[p]);
		if(q<r)Z.emplace_back(L[p].first,L[p].first+r-q-1),L[p].first+=r-q,q=r;
	}
	vector<int>pre(Z.size()+1);
	for(int i=0;i<Z.size();++i)pre[i+1]=pre[i]+Z[i].second-Z[i].first+1;
	X.clear();
	for(auto [l,r]:R){
		l=lower_bound(pre.begin(),pre.end(),l)-pre.begin();
		r=lower_bound(pre.begin(),pre.end(),r+1)-pre.begin()-1;
		for(int i=l;i<=r;++i)X.emplace_back(Z[i]);
	}
}
inline void build(int p,int l,int r){
	if(l==r){
		init(Tx[p],x_1[l],x_2[l]);
		init(Ty[p],y_1[l],y_2[l]);
		return;
	}
	const int mid=(l+r)>>1,ls=p*2,rs=p*2+1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(Tx[ls],Tx[rs],Tx[p]);
	pushup(Ty[ls],Ty[rs],Ty[p]);
}
inline vector<vector<Data>>reduce(vector<pair<int,int>>X,vector<pair<int,int>>nX,vector<pair<int,int>>Y,vector<pair<int,int>>nY,vector<vector<Data>>A){
	vector<vector<Data>>B(nX.size(),vector<Data>(nY.size()));
	sort(nX.begin(),nX.end()),sort(nY.begin(),nY.end());
	for(auto&[l,r]:nX)
		l=lower_bound(X.begin(),X.end(),make_pair(l,-1))-X.begin(),
		r=lower_bound(X.begin(),X.end(),make_pair(r+1,-1))-X.begin()-1;
	for(auto&[l,r]:nY)
		l=lower_bound(Y.begin(),Y.end(),make_pair(l,-1))-Y.begin(),
		r=lower_bound(Y.begin(),Y.end(),make_pair(r+1,-1))-Y.begin()-1;
	for(int i=0;i<nX.size();++i)
		for(int k=nX[i].first;k<=nX[i].second;++k)
			for(int j=0;j<nY.size();++j)
				for(int l=nY[j].first;l<=nY[j].second;++l)
					B[i][j].add_eq(A[k][l]);
	return B;
}
inline void increase(vector<pair<int,int>>X,vector<pair<int,int>>nX,vector<pair<int,int>>Y,vector<pair<int,int>>nY,vector<vector<Operation>>&W,vector<vector<Data>>&A){
	vector<vector<Data>>B(X.size(),vector<Data>(Y.size()));
	vector<vector<Operation>>C(X.size(),vector<Operation>(Y.size()));
	for(auto&[l,r]:nX)
		l=lower_bound(X.begin(),X.end(),make_pair(l,-1))-X.begin(),
		r=lower_bound(X.begin(),X.end(),make_pair(r+1,-1))-X.begin()-1;
	for(auto&[l,r]:nY)
		l=lower_bound(Y.begin(),Y.end(),make_pair(l,-1))-Y.begin(),
		r=lower_bound(Y.begin(),Y.end(),make_pair(r+1,-1))-Y.begin()-1;
	for(int i=0,p=0;i<nX.size();++i)
		for(int k=nX[i].first;k<=nX[i].second;++k,++p)
			for(int j=0,q=0;j<nY.size();++j)
				for(int l=nY[j].first;l<=nY[j].second;++l,++q)
					B[p][q]=A[k][l],C[p][q]=W[i][j];
	A=B,W=C;
}
inline void increase(vector<pair<int,int>>X,vector<pair<int,int>>nX,vector<pair<int,int>>Y,vector<pair<int,int>>nY,vector<vector<Operation>>&W){
	vector<vector<Operation>>C(X.size(),vector<Operation>(Y.size()));
	for(auto&[l,r]:nX)
		l=lower_bound(X.begin(),X.end(),make_pair(l,-1))-X.begin(),
		r=lower_bound(X.begin(),X.end(),make_pair(r+1,-1))-X.begin()-1;
	for(auto&[l,r]:nY)
		l=lower_bound(Y.begin(),Y.end(),make_pair(l,-1))-Y.begin(),
		r=lower_bound(Y.begin(),Y.end(),make_pair(r+1,-1))-Y.begin()-1;
	for(int i=0,p=0;i<nX.size();++i)
		for(int k=nX[i].first;k<=nX[i].second;++k,++p)
			for(int j=0,q=0;j<nY.size();++j)
				for(int l=nY[j].first;l<=nY[j].second;++l,++q)
					C[p][q]=W[k][l];
	W=C;
}
inline vector<pair<int,int>>update(vector<pair<int,int>>X,vector<pair<int,int>>nX){
	vector<pair<int,int>>Z;
	for(auto&[l,r]:nX){
		l=lower_bound(X.begin(),X.end(),make_pair(l,-1))-X.begin(),
		r=lower_bound(X.begin(),X.end(),make_pair(r+1,-1))-X.begin()-1;
		for(int i=l;i<=r;++i)Z.emplace_back(X[i]);
	}
	int p=0;
	for(auto&[l,r]:Z){
		int nl=p,nr=p+r-l;
		p+=r-l+1;
		l=nl,r=nr;
	}
	return Z;
}
inline vector<vector<Operation>>solve(int p,int l,int r,vector<vector<Data>>A,const Operation o[][3][3],Data ans[][3][3]){
	if(l==r){
		for(int i=0;i<3;++i)for(int j=0;j<3;++j)ans[l][i][j]=A[i][j];
		vector<vector<Operation>>W(3,vector<Operation>(3));
		for(int i=0;i<3;++i)for(int j=0;j<3;++j)W[(3-i)%3][(3-j)%3]=o[l][i][j];
		return W;
	}
	const int mid=(l+r)>>1,ls=p*2,rs=p*2+1;
	vector<pair<int,int>>X=Tx[p],Y=Ty[p];
	sort(X.begin(),X.end()),sort(Y.begin(),Y.end());
	vector<vector<Operation>>LsW=solve(ls,l,mid,reduce(X,Tx[ls],Y,Ty[ls],A),o,ans);
	increase(X,Tx[ls],Y,Ty[ls],LsW,A);
	for(int i=0;i<Tx[p].size();++i)
		for(int j=0;j<Ty[p].size();++j)
			LsW[i][j].apply(A[i][j]);
	X=update(X,Tx[ls]),Y=update(Y,Ty[ls]);
	vector<vector<Operation>>RsW=solve(rs,mid+1,r,reduce(X,Tx[rs],Y,Ty[rs],A),o,ans);
	increase(X,Tx[rs],Y,Ty[rs],RsW,A);
	increase(X,Tx[rs],Y,Ty[rs],LsW);
	for(int i=0;i<Tx[p].size();++i)
		for(int j=0;j<Ty[p].size();++j)
			RsW[i][j].apply(LsW[i][j]);
	return LsW;
}
void solve(const int n, const int m, const int p[], const Data d[],
           const int x1[], const int x2[], const int y1[], const int y2[],
           const Operation o[][3][3], Data ans[][3][3]){
	::n=n;
	copy_n(p,n,A),copy_n(d,n,C);
	copy_n(x1,m,x_1),copy_n(x2,m,x_2),copy_n(y1,m,y_1),copy_n(y2,m,y_2);
	for(int l=0,r=BL-1;l<m;l+=BL,r+=BL){
		build(1,l,min(r,m-1));
		auto X=Tx[1],Y=Ty[1];sort(X.begin(),X.end()),sort(Y.begin(),Y.end());
		for(int i=0;i<X.size();++i)for(int j=X[i].first;j<=X[i].second;++j)idx[j]=i;
		for(int i=0;i<Y.size();++i)for(int j=Y[i].first;j<=Y[i].second;++j)idy[j]=i;
		vector<vector<Data>>S(X.size(),vector<Data>(Y.size()));
		for(int i=0;i<n;++i)S[idx[i]][idy[A[i]]].add_eq(C[i]);
		vector<vector<Operation>>W=solve(1,l,min(r,m-1),S,o,ans);
		int p=0;for(auto [l,r]:Tx[1])for(int i=l;i<=r;++i)idx[i]=p++;
		int q=0;for(auto [l,r]:Ty[1])for(int i=l;i<=r;++i)idy[i]=q++;
		for(int i=0;i<n;++i)B[idx[i]]=idy[A[i]],D[idx[i]]=C[i];
		for(int i=0;i<Tx[1].size();++i)for(int j=Tx[1][i].first;j<=Tx[1][i].second;++j)idx[j]=i;
		for(int i=0;i<Ty[1].size();++i)for(int j=Ty[1][i].first;j<=Ty[1][i].second;++j)idy[j]=i;
		for(int i=0;i<n;++i)W[idx[i]][idy[B[i]]].apply(D[i]);
		copy_n(B,n,A),copy_n(D,n,C);
	}
}
源文件, 语言: C++17

詳細信息


Pretests


Final Tests

Test #1:

score: 0
Runtime Error

input:

100000 21489 6 49113 7 60173 8 74888 6 57756 3 9404 3 13780 2 73818 5 6331 2 19759 5 90563 3 2784 10 69925 9 2212 7 57523 1 92604 9 95844 2 89870 2 33003 10 53846 3 79588 5 33137 6 75240 3 12376 4 92734 3 12176 3 64048 10 48444 1 28074 9 54930 9 97809 9 53147 7 51667 6 58543 1 84925 5 47057 4 29059 ...

output:

result:

Test #2:

score: 0
Runtime Error

input:

100000 69665 10 15278 6 72674 3 93522 5 74471 9 49365 7 85608 8 3729 9 69243 5 39180 3 26876 7 51094 2 83441 10 24690 2 44686 1 32112 1 61821 10 6740 4 72546 7 86502 3 89364 3 83731 9 91821 5 33767 5 53574 4 87221 4 41642 1 29525 2 56500 7 37335 8 62608 5 3254 8 73587 10 42659 7 63576 8 14107 4 1534...

output:

result:

Test #3:

score: 0
Runtime Error

input:

100000 78088 3 94024 5 14771 10 58942 3 40949 6 98101 9 33561 9 56898 1 71177 2 43263 10 50994 1 12034 4 10960 6 52881 8 85650 4 76415 9 89558 8 28725 1 72008 7 11199 7 93193 1 41847 1 87298 10 4736 2 38329 1 59361 3 23711 4 33455 3 19302 5 95242 5 72096 10 22776 10 22864 3 12030 4 10659 3 4369 4 50...

output:

result:

Test #4:

score: 0
Runtime Error

input:

100000 15457 6 14735 3 48523 9 17776 5 68591 2 8610 7 52792 2 91312 2 49712 4 89956 9 82574 3 73360 6 13459 5 53721 6 24488 7 61581 4 53165 3 70221 6 15429 4 54374 6 11515 3 29260 2 59020 1 83031 9 52325 8 66096 7 33608 3 37002 5 47053 4 18424 5 96629 9 90730 5 27347 4 86984 8 54072 9 60283 6 91967 ...

output:

result:

Test #5:

score: 0
Runtime Error

input:

100000 10785 6 67618 7 71918 3 60330 3 77568 6 89055 6 97051 4 67553 6 47702 4 41964 7 94295 5 9078 10 83630 2 36139 7 1095 1 78642 10 19366 7 34967 7 63518 7 46007 6 71140 2 54894 6 19374 8 55751 2 31700 2 89914 7 30669 5 51687 9 92079 2 19715 3 62368 10 89803 4 94288 6 90020 4 24022 8 14984 5 7044...

output:

result:

Test #6:

score: 0
Runtime Error

input:

100000 36768 6 3257 1 38397 5 72801 6 98082 10 63603 1 38820 1 37756 1 93147 5 75201 7 74160 7 20700 8 38068 2 16497 3 27739 10 171 2 72017 3 74213 10 14872 3 18805 2 84023 7 58120 9 93591 6 35081 9 76973 6 93826 9 70815 4 69999 9 67045 3 73707 2 97041 4 53284 1 55126 8 49168 2 42869 9 56612 7 9218 ...

output:

result:

Test #7:

score: 0
Runtime Error

input:

100000 19404 6 58021 10 99136 9 33294 9 82920 9 19772 1 39629 8 81111 3 18581 8 76268 2 45876 3 74784 2 56521 1 10286 10 13164 6 62333 9 17934 2 34029 6 62141 8 33500 3 7308 2 14932 7 28141 2 44757 7 66094 6 72585 7 72091 7 77173 10 45152 6 55439 9 19447 6 64886 7 93539 6 21564 3 49343 4 86077 5 777...

output:

result:

Test #8:

score: 0
Runtime Error

input:

100000 72061 10 47496 4 19781 2 96174 10 93995 7 88807 9 46892 3 69085 9 27000 10 65702 3 94626 9 21066 2 92106 5 6473 10 80120 6 60915 7 75590 10 20507 9 59807 5 17324 3 8888 2 98609 10 54420 3 52885 10 22226 6 72252 9 1364 3 56566 10 91972 10 75258 1 73170 10 42425 9 31108 6 70811 10 79318 8 57104...

output:

result:

Test #9:

score: 0
Runtime Error

input:

100000 29532 6 63952 4 55998 9 34077 9 76926 7 56075 9 35680 5 46651 5 78718 8 29942 2 84998 4 61823 2 51347 6 92943 9 46990 6 81833 3 49223 4 18772 5 45966 6 8064 6 6480 5 95762 8 69632 2 23094 1 23768 7 79943 6 6105 3 59408 5 61416 1 47545 10 19592 2 29854 6 66637 1 14390 9 83087 7 55531 7 37485 3...

output:

result:

Test #10:

score: 0
Runtime Error

input:

100000 84676 7 57603 9 20352 4 16697 1 90115 6 48507 9 75362 10 49332 5 47705 5 85561 5 68241 5 46443 5 9688 5 45710 4 51757 3 1477 2 48114 4 74948 5 61999 3 80177 1 40560 8 22763 8 2493 9 78031 1 80799 10 77825 3 3332 1 35593 4 9067 9 26247 2 93914 10 2881 5 82785 2 86644 7 9764 6 50005 6 11432 8 8...

output:

result:
English 繁體中文 简体中文

伺服器時間: 2024-12-12 03:17:15 | 開源專案