QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#744204#5069. VacationTheZoneAC ✓636ms104560kbC++2010.5kb2024-11-13 21:09:252024-11-13 21:09:31

Judging History

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

  • [2024-11-13 21:09:31]
  • 评测
  • 测评结果:AC
  • 用时:636ms
  • 内存:104560kb
  • [2024-11-13 21:09:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
typedef long long ll;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin)),p1==p2)?EOF:*p1++
template<class rd>
void read(rd &x){
	char c=getchar();int f=1;
	for(;c!='-'&&(c<48||c>57);c=getchar());
	if(c=='-')f=-f,c=getchar();
	for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
int n,m,B,pn,a[N],pos[N],pl[N],pr[N],ls;
ll sl[N],sr[N],S,Mx;
#define L k<<1
#define R k<<1|1
struct node{
	ll lmx,rmx,mx,sum;
}tr[N<<2];
inline node operator +(node a,node b){
	node c;
	c.sum=a.sum+b.sum;
	c.lmx=max(a.lmx,a.sum+b.lmx);
	c.rmx=max(b.rmx,b.sum+a.rmx);
	c.mx=max(max(a.mx,b.mx),a.rmx+b.lmx);
	return c;
}
struct seg1{
	node tr[N<<2];
	void build(int k,int l,int r){
		if(l==r){
			tr[k].mx=tr[k].lmx=tr[k].rmx=tr[k].sum=a[l];
			return;
		}
		int mid=l+r>>1;
		build(L,l,mid),build(R,mid+1,r);
		if(r-l+1<=B)tr[k]=tr[L]+tr[R];
	}
	void modify(int k,int l,int r,int x,int v){
		if(l==r){
			tr[k].mx=tr[k].lmx=tr[k].rmx=tr[k].sum=v;
			return;
		}
		int mid=l+r>>1;
		if(x<=mid)modify(L,l,mid,x,v);
		else modify(R,mid+1,r,x,v);
		if(r-l+1<=B)tr[k]=tr[L]+tr[R];
	}
	node query(int k,int l,int r,int x,int y){
		if(x<=l&&r<=y)return tr[k];
		int mid=l+r>>1;
		if(x<=mid&&y>mid)return query(L,l,mid,x,y)+query(R,mid+1,r,x,y);
		if(x<=mid)return query(L,l,mid,x,y);
		else return query(R,mid+1,r,x,y);
	}
}T1;
struct seg3{
	ll *s1,*s2,*tg,*m1,*m2;
	inline void pushup(int k){
		s2[k]=s2[L]+s2[R];
		s1[k]=max(s1[L],s1[R]);
		m2[k]=max(m2[L],s2[L]+m2[R]);
		m1[k]=max(m1[L],max(m1[R]+s2[L],s1[R]+m2[L]));
	}
	inline void pushtg(int k,ll v){
		tg[k]+=v,s1[k]+=v,m1[k]+=v;
	}
	inline void pushdown(int k){
		if(tg[k]){
			pushtg(L,tg[k]);
			pushtg(R,tg[k]);
			tg[k]=0;
		}
	}
	void build(int k,int l,int r){
		tg[k]=0;
		if(l==r){
			s2[k]=m2[k]=sr[l],s1[k]=m1[k]=sl[l];
			return;
		}
		int mid=l+r>>1;
		build(L,l,mid),build(R,mid+1,r);
		pushup(k);
	}
#define New new ll [B<<2]
	void init(int x){
		s1=New,s2=New,tg=New,m1=New,m2=New;
		for(int i=1;i<=B;++i){
			sr[i]=a[pl[x+1]+i-1];
			sl[i]=a[pl[x]+i-1];
		}
		for(int i=B;i;--i)sl[i]+=sl[i+1];
		build(1,1,B);
	}
	void modify(int k,int l,int r,int x,ll v){
		if(x>=r)return pushtg(k,v);
		int mid=l+r>>1;
		pushdown(k);
		if(x>mid)modify(R,mid+1,r,x,v);
		modify(L,l,mid,x,v);
		pushup(k);
	}
	void modify2(int k,int l,int r,int x,ll v){
		if(l==r)return s2[k]=m2[k]=v,void();
		int mid=l+r>>1;
		pushdown(k);
		if(x<=mid)modify2(L,l,mid,x,v);
		else modify2(R,mid+1,r,x,v);
		pushup(k);
	}
	void query2(int k,int l,int r,int y){
		if(r<=y){
			Mx=max(Mx,S+m2[k]);
			S+=s2[k];
			return;
		}
		pushdown(k);
		int mid=l+r>>1;
		if(y>mid)query2(L,l,mid,y);
		query2(R,mid+1,r,y);
	}
	ll query(int k,int l,int r,int x,int y){
		if(x<=l){
			if(y<l)return Mx+s1[k];
			if(y>=r)return max(Mx+s1[k],S+m1[k]);
		}
		int mid=l+r>>1;
		pushdown(k);
		ll res=0;
		if(x<=mid)res=max(res,query(L,l,mid,x,y));
		if(ls<min(l,y))query2(L,l,mid,y),ls=mid;
		res=max(res,query(R,mid+1,r,x,y));
		if(ls<min(mid+1,y))query2(R,mid+1,r,y),ls=r;
		return res;
	}
}T3[N];
struct seg2{
	ll mx[N<<2];
	void build(int k,int l,int r,bool fg=0){
		if(l==r){
			if(fg)return mx[k]=T3[l-1].m1[1],void();
			ll s=0;
			for(int i=pl[l];i<=pr[l];++i){
				s=max(0ll,s+a[i]);
				mx[k]=max(mx[k],s);
			}
			return;
		}
		int mid=l+r>>1;
		build(L,l,mid,fg),build(R,mid+1,r,fg);
		mx[k]=max(mx[L],mx[R]);
	}
	void modify(int k,int l,int r,int x,ll v){
		if(l==r)return mx[k]=v,void();
		int mid=l+r>>1;
		if(x<=mid)modify(L,l,mid,x,v);
		else modify(R,mid+1,r,x,v);
		mx[k]=max(mx[L],mx[R]);
	}
	ll query(int k,int l,int r,int x,int y){
		if(x<=l&&r<=y)return mx[k];
		int mid=l+r>>1;ll res=0;
		if(x<=mid)res=max(res,query(L,l,mid,x,y));
		if(y>mid)res=max(res,query(R,mid+1,r,x,y));
		return res;
	}
}T2,T4;
void Modify(int x,int y){
	int lx=pos[x];
	T1.modify(1,1,n,x,y);
	T2.modify(1,1,pn,lx,T1.query(1,1,n,pl[lx],pr[lx]).mx);
	if(lx<pn){
		T3[lx].modify(1,1,B,x-pl[lx]+1,y-a[x]);
		T4.modify(1,2,pn,lx+1,T3[lx].m1[1]);
	}
	if(lx>1){
		T3[lx-1].modify2(1,1,B,x-pl[lx]+1,y);
		T4.modify(1,2,pn,lx,T3[lx-1].m1[1]);
	}
	a[x]=y;
}
ll Query(int l,int r){
	if(r-l+1<=B)return max(0ll,T1.query(1,1,n,l,r).mx);
	int lx=pos[l],rx=pos[r];
	if(l==pl[lx])--lx;
	if(r==pr[rx])++rx;
	ll res=0;
	if(lx+1<rx)res=max(res,T2.query(1,1,pn,lx+1,rx-1));
	if(lx+2<rx)res=max(res,T4.query(1,2,pn,lx+2,rx-1));
	if(lx==pos[l]){
		S=Mx=ls=0;
		res=max(res,max(T3[lx].query(1,1,B,l-pl[lx]+1,min(r,pr[lx+1])-pl[lx+1]+1),T1.query(1,1,n,l,pr[lx]).mx));
	}
	if(rx==pos[r]){
		S=Mx=ls=0;
		res=max(res,max(T3[rx-1].query(1,1,B,max(l,pl[rx-1])-pl[rx-1]+1,r-pl[rx]+1),T1.query(1,1,n,pl[rx],r).mx));
	}
	return res;
}
int main(){
	read(n),read(m),read(B);
	for(int i=1;i<=n;++i)read(a[i]),pos[i]=(i-1)/B+1;
	pn=pos[n];
	while(n%B!=0)++n,pos[n]=pn;
	for(int i=1;i<=pn;++i)pl[i]=(i-1)*B+1,pr[i]=i*B;
	T1.build(1,1,n),T2.build(1,1,pn);
	for(int i=1;i<pos[n];++i)T3[i].init(i);
	if(pn>1)T4.build(1,2,pn,1);
	for(int i=1,op,x,y;i<=m;++i){
		read(op),read(x),read(y);
		if(op==1)Modify(x,y);
		else printf("%lld\n",Query(x,y));
	}
	return 0;
}
/*#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
typedef long long ll;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin)),p1==p2)?EOF:*p1++
template<class rd>
void read(rd &x){
	char c=getchar();int f=1;
	for(;c!='-'&&(c<48||c>57);c=getchar());
	if(c=='-')f=-f,c=getchar();
	for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
int n,m,B,pn,a[N],pos[N],pl[N],pr[N],ls;
ll sl[N],sr[N],S,Mx;
#define L k<<1
#define R k<<1|1
struct node{
	ll lmx,rmx,mx,sum;
}tr[N<<2];
inline node operator +(node a,node b){
	node c;
	c.sum=a.sum+b.sum;
	c.lmx=max(a.lmx,a.sum+b.lmx);
	c.rmx=max(b.rmx,b.sum+a.rmx);
	c.mx=max(max(a.mx,b.mx),a.rmx+b.lmx);
	return c;
}
struct seg1{
	node tr[N<<2];
	void build(int k,int l,int r){
		if(l==r){
			tr[k].mx=tr[k].lmx=tr[k].rmx=tr[k].sum=a[l];
			return;
		}
		int mid=l+r>>1;
		build(L,l,mid),build(R,mid+1,r);
		if(r-l+1<=B)tr[k]=tr[L]+tr[R];
	}
	void modify(int k,int l,int r,int x,int v){
		if(l==r){
			tr[k].mx=tr[k].lmx=tr[k].rmx=tr[k].sum=v;
			return;
		}
		int mid=l+r>>1;
		if(x<=mid)modify(L,l,mid,x,v);
		else modify(R,mid+1,r,x,v);
		if(r-l+1<=B)tr[k]=tr[L]+tr[R];
	}
	node query(int k,int l,int r,int x,int y){
		if(x<=l&&r<=y)return tr[k];
		int mid=l+r>>1;
		if(x<=mid&&y>mid)return query(L,l,mid,x,y)+query(R,mid+1,r,x,y);
		if(x<=mid)return query(L,l,mid,x,y);
		else return query(R,mid+1,r,x,y);
	}
}T1;
struct seg3{
	ll *s1,*s2,*tg,*m1,*m2;
	inline void pushup(int k){
		s2[k]=s2[L]+s2[R];
		s1[k]=max(s1[L],s1[R]);
		m2[k]=max(m2[L],s2[L]+m2[R]);
		m1[k]=max(m1[L],max(m1[R]+s2[L],s1[R]+m2[L]));
	}
	inline void pushtg(int k,ll v){
		tg[k]+=v,s1[k]+=v,m1[k]+=v;
	}
	inline void pushdown(int k){
		if(tg[k]){
			pushtg(L,tg[k]);
			pushtg(R,tg[k]);
			tg[k]=0;
		}
	}
	void build(int k,int l,int r){
		tg[k]=0;
		if(l==r){
			s2[k]=m2[k]=sr[l],s1[k]=m1[k]=sl[l];
			return;
		}
		int mid=l+r>>1;
		build(L,l,mid),build(R,mid+1,r);
		pushup(k);
	}
#define New new ll [B<<2]
	void init(int x){
		s1=New,s2=New,tg=New,m1=New,m2=New;
		for(int i=1;i<=B;++i){
			sr[i]=a[pl[x+1]+i-1];
			sl[i]=a[pl[x]+i-1];
		}
		for(int i=B;i;--i)sl[i]+=sl[i+1];
		build(1,1,B);
	}
	void modify(int k,int l,int r,int x,ll v){
		if(x>=r)return pushtg(k,v);
		int mid=l+r>>1;
		pushdown(k);
		if(x>mid)modify(R,mid+1,r,x,v);
		modify(L,l,mid,x,v);
		pushup(k);
	}
	void modify2(int k,int l,int r,int x,ll v){
		if(l==r)return s2[k]=m2[k]=v,void();
		int mid=l+r>>1;
		pushdown(k);
		if(x<=mid)modify2(L,l,mid,x,v);
		else modify2(R,mid+1,r,x,v);
		pushup(k);
	}
	void query2(int k,int l,int r,int y){
		if(r<=y){
			Mx=max(Mx,S+m2[k]);
			S+=s2[k];
			return;
		}
		pushdown(k);
		int mid=l+r>>1;
		if(y>mid)query2(L,l,mid,y);
		query2(R,mid+1,r,y);
	}
	ll query(int k,int l,int r,int x,int y){
		if(x<=l){
			if(y<l)return Mx+s1[k];
			if(y>=r)return max(Mx+s1[k],S+m1[k]);
		}
		int mid=l+r>>1;
		pushdown(k);
		ll res=0;
		if(x<=mid)res=max(res,query(L,l,mid,x,y));
		if(ls<min(l,y))query2(L,l,mid,y),ls=mid;
		res=max(res,query(R,mid+1,r,x,y));
		if(ls<min(mid+1,y))query2(R,mid+1,r,y),ls=r;
		return res;
	}
}T3[N];
struct seg2{
	ll mx[N<<2];
	void build(int k,int l,int r,bool fg=0){
		if(l==r){
			if(fg)return mx[k]=T3[l-1].m1[1],void();
			ll s=0;
			for(int i=pl[l];i<=pr[l];++i){
				s=max(0ll,s+a[i]);
				mx[k]=max(mx[k],s);
			}
			return;
		}
		int mid=l+r>>1;
		build(L,l,mid,fg),build(R,mid+1,r,fg);
		mx[k]=max(mx[L],mx[R]);
	}
	void modify(int k,int l,int r,int x,ll v){
		if(l==r)return mx[k]=v,void();
		int mid=l+r>>1;
		if(x<=mid)modify(L,l,mid,x,v);
		else modify(R,mid+1,r,x,v);
		mx[k]=max(mx[L],mx[R]);
	}
	ll query(int k,int l,int r,int x,int y){
		if(x<=l&&r<=y)return mx[k];
		int mid=l+r>>1;ll res=0;
		if(x<=mid)res=max(res,query(L,l,mid,x,y));
		if(y>mid)res=max(res,query(R,mid+1,r,x,y));
		return res;
	}
}T2,T4;
void Modify(int x,int y){
	int lx=pos[x];
	T1.modify(1,1,n,x,y);
	T2.modify(1,1,pn,lx,T1.query(1,1,n,pl[lx],pr[lx]).mx);
	if(lx<pn){
		T3[lx].modify(1,1,B,x-pl[lx]+1,y-a[x]);
		T4.modify(1,2,pn,lx+1,T3[lx].m1[1]);
	}
	if(lx>1){
		T3[lx-1].modify2(1,1,B,x-pl[lx]+1,y);
		T4.modify(1,2,pn,lx,T3[lx-1].m1[1]);
	}
	a[x]=y;
}
ll Query(int l,int r){
	if(r-l+1<=B)return max(0ll,T1.query(1,1,n,l,r).mx);
	int lx=pos[l],rx=pos[r];
	if(l==pl[lx])--lx;
	if(r==pr[rx])++rx;
	ll res=0;
	if(lx+1<rx)res=max(res,T2.query(1,1,pn,lx+1,rx-1));
	if(lx+2<rx)res=max(res,T4.query(1,2,pn,lx+2,rx-1));
	if(lx==pos[l]){
		S=Mx=ls=0;
		res=max(res,max(T3[lx].query(1,1,B,l-pl[lx]+1,min(r,pr[lx+1])-pl[lx+1]+1),T1.query(1,1,n,l,pr[lx]).mx));
	}
	if(rx==pos[r]){
		S=Mx=ls=0;
		res=max(res,max(T3[rx-1].query(1,1,B,max(l,pl[rx-1])-pl[rx-1]+1,r-pl[rx]+1),T1.query(1,1,n,pl[rx],r).mx));
	}
	return res;
}
int main(){
	read(n),read(m),read(B);
	for(int i=1;i<=n;++i)read(a[i]),pos[i]=(i-1)/B+1;
	pn=pos[n];
	while(n%B!=0)++n,pos[n]=pn;
	for(int i=1;i<=pn;++i)pl[i]=(i-1)*B+1,pr[i]=i*B;
	T1.build(1,1,n),T2.build(1,1,pn);
	for(int i=1;i<pos[n];++i)T3[i].init(i);
	if(pn>1)T4.build(1,2,pn,1);
	for(int i=1,op,x,y;i<=m;++i){
		read(op),read(x),read(y);
		if(op==1)Modify(x,y);
		else printf("%lld\n",Query(x,y));
	}
	return 0;
}*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 20260kb

input:

5 6 3
0 -5 -3 8 -3
2 3 5
1 2 5
2 1 5
1 4 -3
2 3 5
2 1 5

output:

8
10
0
5

result:

ok 4 number(s): "8 10 0 5"

Test #2:

score: 0
Accepted
time: 384ms
memory: 104560kb

input:

200000 500000 1
387060158 961744470 37167782 737122872 -532977662 1604246 -30977399 871848791 444997246 454204578 -813187501 -660394286 448014171 -835115276 -631880452 887715308 258530352 805589560 -414653327 -156732249 -335096199 -80266237 367896009 738406627 -903652056 446120866 415658444 -1347916...

output:

999902477
999981999
999343404
999847372
999957587
998160312
999981999
999981999
999981999
999980061
999981999
999981999
999981999
999876122
999981999
999996602
999981999
999981999
999981999
999723649
999981999
999957587
999896087
999981999
999981999
999981999
999981999
999981999
999957587
999981999
...

result:

ok 250051 numbers

Test #3:

score: 0
Accepted
time: 469ms
memory: 79856kb

input:

200000 500000 5
802774074 383481934 -295470374 285359286 751657057 197444479 626916547 -828168464 288373833 -493446966 -208422769 956745384 919286225 959643271 -176531848 -380256966 357111771 -50890039 -637284768 -337010918 259019684 752475630 -259898780 98620995 -704832505 -532710796 -971600790 -84...

output:

4544135313
4544135313
4443416295
3390067591
4544135313
4544135313
4322308420
4386413596
4386413596
4165697630
4322308420
4287938127
4443416295
4544135313
4386413596
4165697630
4386413596
4386413596
4386413596
4323325838
4443416295
4386413596
4385851999
4544135313
4443416295
4443416295
4323325838
432...

result:

ok 249998 numbers

Test #4:

score: 0
Accepted
time: 493ms
memory: 79480kb

input:

200000 500000 10
294669347 -694582751 -596596961 -126098203 564639690 -654836388 -393227122 -835904658 699214733 147549986 -60745155 364274902 6365735 182107449 544381751 8255910 -581710335 -254751705 -547803021 113792037 -526424167 -948294769 -456727013 -172857504 627985189 -660230969 -233539222 -3...

output:

6382761194
6975829216
5771846079
7795537121
6975829216
7251135307
7795537121
7795537121
7795537121
7251135307
6382761194
7251135307
7795537121
7795537121
7251135307
6166320975
7251135307
5845186875
6304374419
7795537121
6533205084
6975829216
7795537121
6051983693
7795537121
6533205084
6671392380
553...

result:

ok 249912 numbers

Test #5:

score: 0
Accepted
time: 547ms
memory: 74584kb

input:

200000 500000 50
682924062 -410171362 727046928 -248951706 447030590 -828489266 -766563199 -502548010 -959695696 -583569857 -305162329 -550851997 -462615752 -822803313 -640012170 267251148 340565257 -111341766 689672874 -515868601 -242875719 -162422332 49211711 277849676 -108078900 -304560362 -50058...

output:

15856525974
15423765469
15423765469
15728637453
15856525974
15728637453
15728637453
15060577990
15856525974
15856525974
15060577990
15856525974
15856525974
15856525974
15060577990
15728637453
15856525974
15856525974
15856525974
15856525974
15592293852
15856525974
15592293852
15856525974
15423765469
...

result:

ok 249945 numbers

Test #6:

score: 0
Accepted
time: 597ms
memory: 74772kb

input:

200000 500000 100
-861625642 488714758 151701153 337144530 -318293290 -765334091 -210261967 -253541961 993816332 -736017816 52189861 -428475798 -281280689 875335671 889366119 -863352867 4083578 382040499 152212580 696548442 348806166 -403452187 -91390158 -86542614 -915521115 -615218473 374313280 -60...

output:

22356669163
16483275109
20675548507
20675548507
18341749229
16758974141
19886103941
22356669163
12776363397
19919404941
22356669163
22356669163
22356669163
20675548507
22356669163
22356669163
20675548507
22356669163
19886103941
20352085144
22356669163
22356669163
19064838381
19782436621
20675548507
...

result:

ok 250001 numbers

Test #7:

score: 0
Accepted
time: 601ms
memory: 67996kb

input:

200000 500000 500
560111824 156076602 -300062433 -135130960 172514238 -107440145 332810571 -462042876 -248802506 163714210 -330670470 42796256 -486522143 -669315725 -916663241 992138762 904514188 -430525531 509990997 -414368382 886580739 968753025 -783053293 60399434 -189320070 -2477706 -334706343 4...

output:

51487237399
38429372430
32781696692
35966554114
51487237399
51487237399
49119655459
40039498632
49119655459
42076835781
51487237399
42076835781
40039498632
51487237399
40039498632
51487237399
43222631363
40936887546
38671383728
35611226388
42076835781
51487237399
51487237399
51487237399
35611226388
...

result:

ok 249987 numbers

Test #8:

score: 0
Accepted
time: 611ms
memory: 64392kb

input:

200000 500000 1000
-274863070 -196927487 -173462836 -322148327 -974733923 872416187 81984586 243765318 392194447 16424530 -680051160 -870124234 197884950 51597873 -580027867 53316656 943742315 -289166281 665826659 505220474 -814189661 771924792 945468209 -606782872 -316840243 735583862 163401810 -98...

output:

68585884487
68585884487
68585884487
48732425297
68585884487
68585884487
34196859335
68585884487
44187544054
68585884487
59171503971
45112394103
48732425297
68585884487
68585884487
62264064415
68585884487
68585884487
68585884487
68585884487
68585884487
68585884487
62264064415
68585884487
44187544054
...

result:

ok 249847 numbers

Test #9:

score: 0
Accepted
time: 636ms
memory: 68700kb

input:

200000 500000 5000
-233541473 -821406097 -834373426 -682847219 -558452214 794047404 658431025 584854890 -43958103 -471082436 456699444 660894280 -563936020 867203954 -26065334 680624954 844062461 -808600596 -206923771 788768922 266650071 -722136485 -308857317 414063248 333797658 468533943 -346326422...

output:

111528324186
111528324186
122473166396
88429113651
121592699866
90259744634
22840599473
111528324186
111528324186
121592699866
111528324186
111528324186
121592699866
88429113651
39504491251
121848200792
52521769508
97463661530
111528324186
35002189953
121848200792
98152563998
60222302625
29889397997...

result:

ok 249934 numbers

Test #10:

score: 0
Accepted
time: 600ms
memory: 67732kb

input:

200000 500000 10000
665344648 603248129 584747190 794918694 -495297038 -649651364 907437075 243399623 -196406062 424326840 284108349 842229343 891113172 396582242 895208153 639110569 -419465483 653939112 -456449644 -619549194 320587509 -619648562 -968216902 -393378967 -271827747 -656563637 194138895...

output:

56259543721
45446857386
127693546205
139657304562
139734032583
145066327195
151709822656
151709822656
151709822656
59196591326
151709822656
151709822656
151709822656
93441101388
145765337767
151709822656
151709822656
139657304562
139657304562
76339935235
82918361465
145765337767
152180432737
1521804...

result:

ok 249995 numbers

Test #11:

score: 0
Accepted
time: 457ms
memory: 61204kb

input:

200000 500000 50000
575796283 151484543 -720552679 -957363572 -132370386 -401546120 455846368 -409284627 408358670 41466509 998470195 393898097 -115481139 -871390033 993789573 -165491528 819845991 -936404970 189543742 213192673 -602174573 740565806 -821274853 332822078 340913021 634416742 950042524 ...

output:

34822696696
304044933300
68367040267
189494218463
334878403626
267659551435
24069522488
207246743747
266472736311
256136296058
318863343332
266472736311
318863343332
333342852149
333342852149
333342852149
333342852149
333342852149
244890005888
333894397388
14926116799
327180309259
169083865298
30229...

result:

ok 249979 numbers

Test #12:

score: 0
Accepted
time: 355ms
memory: 57424kb

input:

200000 500000 100000
569636990 278084140 -907570046 -104611731 552518652 -409282313 -595255647 231712326 556036284 -307914181 -157540087 -678605019 67375374 -777844451 54967467 -421230696 909327738 924463398 814165304 217454981 -504035512 469087307 268453049 448391697 -626058118 -867475106 -71503492...

output:

183803743045
84753846309
183803743045
184110002817
105439165831
67546271314
169297374450
99805942710
169297374450
182981361171
104276266099
264432291020
151095250825
264578163447
113845850587
185483046361
197245535689
185483046361
171141245411
163740444589
46081034455
99805942710
151095250825
171141...

result:

ok 249890 numbers

Test #13:

score: 0
Accepted
time: 161ms
memory: 36796kb

input:

200000 500000 200000
-797962146 -508688404 710511327 -513510680 728213176 552511953 -936241431 488159917 -444295562 -536695906 -505756916 130939739 614047261 -713095641 846308813 714302364 -50331832 62015532 -201658784 708890384 -759229325 -444174649 718951299 -388948828 877697837 -860392893 5422631...

output:

13912697561
53056934566
408059533397
26752612529
231772401996
408919427178
79448528167
268531947957
134457596821
132829174449
109465830672
94113395976
408210605035
408210605035
408210605035
79283848538
409284836395
75674809566
231092415035
90163884680
99205202539
269241228577
106739591025
1438823581...

result:

ok 249963 numbers