QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#223835#7438. 樋口円香NahidameowTL 975ms16564kbC++236.0kb2023-10-22 17:44:532023-10-22 17:44:53

Judging History

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

  • [2023-10-22 17:44:53]
  • 评测
  • 测评结果:TL
  • 用时:975ms
  • 内存:16564kb
  • [2023-10-22 17:44:53]
  • 提交

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=1;
	for(int i=1;i<=n;i++)pos[i]=(i-1)/n+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(PSr[i]*B,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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 16284kb

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:

9812
18329
25519
40685
50358
58477
67055
71202
84917
83471
95554
98972
114054
112482
126642
125010
144914
147671
141407
162102
164317
170828
171245
193368
183842
180062
189229
195363
201525
208055
211890
218246
222774
237496
232051
230084
240108
247492
257506
259433
262038
254605
259817
258900
25715...

result:

ok 1000 lines

Test #2:

score: 0
Accepted
time: 975ms
memory: 16564kb

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...

output:

11337
20492
27617
38150
59067
68173
78360
91299
95892
109338
125673
129644
134532
153938
162487
181716
190109
202080
211662
217170
233126
223881
247707
269064
262512
271414
292008
286305
310010
326696
327857
340549
356849
355034
385112
396461
394276
401687
431908
429402
436902
456239
480823
466472
4...

result:

ok 100000 lines

Test #3:

score: -100
Time Limit Exceeded

input:

100000
770 158 194 936 605 941 814 119 685 202 611 549 697 350 322 412 751 477 433 316 489 211 428 467 47 155 318 646 342 664 801 700 466 584 494 455 350 801 315 65 323 248 952 506 429 320 798 591 272 702 475 708 457 911 421 957 642 737 75 483 938 415 371 945 792 88 400 928 125 850 140 313 121 4 784...

output:


result: