QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#223859	#7438. 樋口円香	Nahidameow	TL	5ms	13788kb	C++23	6.0kb	2023-10-22 18:26:48	2023-10-22 18:26:49

Judging History

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

[2023-10-22 18:26:49]
评测

测评结果：TL
用时：5ms
内存：13788kb

查看

[2023-10-22 18:26:48]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pd push_back
#define all(x) x.begin(),x.end()
//==============================================================
ll QP(ll x,ll y,ll mod){
	ll ans=1;
	for(;y;y>>=1,x=x*x%mod)
		if(y&1)
			ans=ans*x%mod;
	return ans;
}
ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
//==============================================================1
const int BUFSIZE=1<<20;
char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
char tmp[BUFSIZE];int ct=0;
inline char getch(){
    if(is==it)
        it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
    return is==it?EOF:*is++;
}
namespace IO{
	int readInt(){
		int x=0,y=0;char c=0;
		while(!isdigit(c))
			y|=c=='-',c=getch();
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();
		return !y?x:-x;
	}
	void flush(){
		fwrite(tmp,1,ct,stdout);
		ct=0;
	}
	void putch(char c){
		tmp[ct++]=c;
		if(ct==BUFSIZE)flush();
	}
	void putint(int x){
		char q[10];
		if(x==0)putch('0');
		int top=0;
		while(x)q[top++]=(x%10+'0'),x/=10;
		while(top--)putch(q[top]);
	}
}
const int N=3e5+10;
const int M=6e5+1;
const int mod=1004535809,g=3,G=inv(3,mod);
//int w[40]={0,998244352,911660635,372528824,929031873,452798380,922799308,781712469,476477967,
//		  166035806,258648936,584193783,63912897,350007156,666702199,968855178,629671588,24514907,
//		  996173970,363395222,565042129,733596141},
//	w0[40]={0,998244352,86583718,509520358,337190230,87557064,609441965,135236158,304459705,685443576,
//			381598368,335559352,129292727,358024708,814576206,708402881,283043518,3707709,121392023,
//			704923114,950391366,428961804};
//ll g1=QP(opt==1?g:gi,(mod-1)/(i<<1),mod);
//void init1(){
//	for(int i=1,p=1;i<=2e6;i<<=1,p++)w[p]=QP(g,(mod-1)/(i<<1),mod);
//	for(int i=1,p=1;i<=2e6;i<<=1,p++)w0[p]=QP(gi,(mod-1)/(i<<1),mod);
//}
//vector<int> rev;
int gi[N];
//void Resize(int n){rev.resize(n<<1);}
void init1(int n){
	for(int i=2;i<=n;i<<=1){
		int gn=QP(G,(mod-1)/i,mod);
		gi[i>>1]=1;
		for(int j=(i>>1)+1;j<i;j++)
			gi[j]=1ll*gi[j-1]*gn%mod;
	}
}
namespace Math{
	//int fac[N],nfac[N];
	int Iv[N];
//	void initfac(){
//		fac[0]=1;for(int i=1;i<=N-10;i++)fac[i]=1ll*fac[i-1]*i%mod;
//		nfac[N-10]=inv(fac[N-10],mod);for(int i=N-11;~i;i--)nfac[i]=1ll*nfac[i+1]*(i+1)%mod;
//	}int C(int x,int y){return x<0||y<0||x<y?0:1ll*fac[x]*nfac[y]%mod*nfac[x-y]%mod;}
	void initinv(){
		Iv[1]=1;
		for(int i=2;i<=N-10;i++)
			Iv[i]=1ll*(-1ll*Iv[mod%i]*(mod/i)%mod+mod)%mod;
	}
}
#define add(x) (x+(x<0?mod:0)-(x>=mod?mod:0))
struct Poly{
	vector<int> v;
	inline void read(int n){v.resize(n+1);for(int i=0;i<=n;i++){v[i]=IO::readInt();if(v[i]>=mod)v[i]-=mod;};}
	inline void write(int n){for(int i=0;i<=n;i++)printf("%d ",v[i]);puts("");return;}
	inline void debug(){for(auto y:v)printf("%d ",y);puts("");return;} 
	//=========================================================================
	inline void clear(int n){while(v.size()>n+1)v.pop_back();} 
	//=========================================================================
	inline int operator [](const int &i)const{
		if(v.size()<=i)return 0;
		else return v[i];
	}inline int& operator [](const int &i){
		if(v.size()<=i)v.resize(i+1);
		return v[i];
	}
	//==========================================================================
	inline int init2(int n,int m){
		int lim=0; 
		while((1<<lim)<=n+m)lim++;
	//	for(int i=0;i<(1<<lim);i++)rev[i]=(rev[i>>1]>>1)|((i&1)?(1<<lim-1):0);
		return lim;
	}
	//==========================================================================
	inline void NTT(Poly &f,const int &n){
		for(int i=n>>1;i;i>>=1)
			for(int j=0;j<n;j+=(i<<1))
				for(int k=0,x,y;k<i;k++)
					x=f[j|k],y=f[i|j|k],
					f[j|k]=x+y-(x+y>=mod?mod:0),
					f[i|j|k]=1ll*gi[i|k]*(x-y+(x-y<0?mod:0))%mod;
	}
	inline void INTT(Poly &f,const int &n){
		for(int i=1;i<n;i<<=1)
			for(int j=0;j<n;j+=(i<<1))
				for(int k=0,x,y;k<i;k++)
					x=f[j|k],y=1ll*gi[i|k]*f[i|j|k]%mod,
					f[j|k]=x+y-(x+y>=mod?mod:0),f[i|j|k]=(x-y+(x-y<0?mod:0));		
		int Inv=inv(n,mod);
		reverse(f.v.begin()+1,f.v.begin()+n);
		for(int i=0;i<n;i++)f[i]=1ll*f[i]*Inv%mod;
	}inline Poly convolution(Poly A,Poly B){
		int lim=init2(A.v.size()-1,B.v.size()-1);
	//	A.debug();B.debug();
		NTT(A,1<<lim);NTT(B,1<<lim);
	//	A.debug();B.debug();
		for(int i=0;i<(1<<lim);i++)A[i]=1ll*A[i]*B[i]%mod;
		INTT(A,(1<<lim));
	//	for(auto y:A.v)printf("%d ",y);puts("");
		return A;
	}
	inline Poly operator * (const Poly &y){
		Poly ans=convolution((*this),y);
		ans.clear(((*this).v.size()-1)+(y.v.size()-1));
		return ans;
	}
};
const int K=1e6+10;
int n,m;
int pos[N],Pl[N],Pr[N];
int PSl[N],PSr[N];
int B;
int A[N];
int C[N];
struct Query{int l,posl,posr,L;}Q[K];
int cnt=0;
void change(int l,int r,int F){
	if(pos[l]==pos[r]){
		for(int i=l;i<=r;i++)
			C[F-l+i]+=A[i];
		return;
	}
	for(int i=l;i<=Pr[l];i++)C[F-l+i]+=A[i];
	for(int i=Pl[r];i<=r;i++)C[F-l+i]+=A[i];
	Q[++cnt]={l,pos[l]+1,pos[r]-1,F};
}
void solve(int l,int r){
	int p=pos[l],len=r-l+1;
	Poly A1,A2;
	for(int i=1;i<=cnt;i++){
		if(Q[i].posl<=p&&p<=Q[i].posr)
			A1[Q[i].L+l-Q[i].l]++;
		//else if(p>Q[i].posr)continue;
	}
	for(int i=0;i<len;i++)
		A2[i]=A[l+i];
	A1=A1*A2;
	for(int i=1;i<=n;i++)
		C[i]+=A1[i];
}
int main(){
	//freopen("1.in","r",stdin);
	//freopen(".out","w",stdout);
	Math::initinv();
	init1(N-1);
	n=IO::readInt(); 
	for(int i=1;i<=n;i++)A[i]=IO::readInt();
	//B=max(int(sqrt((1ll*n*n*log(n)+1ll*n*m)/m)),1);
	B=500;
	for(int i=1;i<=n;i++)pos[i]=(i-1)/B+1;
	for(int i=1;i<=n;i++)Pl[i]=(pos[i]-1)*B+1,Pr[i]=min(pos[i]*B,n);
	for(int i=1;i<=pos[n];i++)PSl[i]=(i-1)*B+1,PSr[i]=min(PSl[i]+B-1,n);
	m=IO::readInt();
	while(m--){
		int l=IO::readInt(),r=IO::readInt(),L=IO::readInt();//scanf("%d%d%d",&l,&r,&L);
		change(l,r,L);
	}
	sort(Q+1,Q+cnt+1,[](auto x,auto y){return x.posr<y.posr;});
	for(int i=1;i<=pos[n];i++)solve(PSl[i],PSr[i]);
	for(int i=1;i<=n;i++)
		IO::putint(C[i]),IO::putch('\n');
	IO::flush();
	return 0;
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 5ms

memory: 13788kb

input:

1000
629 353 463 242 579 37 341 579 751 331 971 209 993 230 150 893 723 872 154 456 443 858 815 904 643 97 471 510 695 436 306 499 371 971 494 147 702 903 795 968 731 890 594 590 356 63 313 564 718 680 525 284 848 154 36 858 367 454 723 351 580 80 102 308 680 598 185 681 706 494 725 951 248 570 793 ...

output:

result:

ok 1000 lines

Test #2:

score: -100

Time Limit Exceeded

input:

100000
984 353 333 932 661 754 360 57 828 818 156 676 408 992 550 847 743 689 198 782 144 163 27 320 781 316 966 842 84 797 588 39 867 498 675 598 345 159 491 1000 46 874 992 829 838 575 542 836 541 30 393 998 762 434 978 382 34 862 446 828 283 820 537 293 597 240 198 258 404 929 977 588 138 214 504...