QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#189777#6327. Count Arithmetic ProgressionqzezWA 167ms36708kbC++142.9kb2023-09-27 21:31:172023-09-27 21:31:18

Judging History

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

  • [2023-09-27 21:31:18]
  • 评测
  • 测评结果:WA
  • 用时:167ms
  • 内存:36708kb
  • [2023-09-27 21:31:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const ll INF=1e13;
const int N=3e5+10,mod=998244353;
int n;
ll l[N],r[N];
int top,stk[N];
bool chkL(int x,int y,int z){
	return (z-x)*(l[y]-l[x])-(l[z]-l[x])*(y-x)>0;
}
bool chkR(int x,int y,int z){
	return (y-x)*(r[z]-r[x])-(r[y]-r[x])*(z-x)>0;
}
int ta,tb,m;
struct zj{
	ll L,R;//[L,R)
	int id;
}a[N],b[N];
ll c[N*4];
ll upper(ll x,int y){
	if(y<0)y=-y,x=-x;
	if(x>=0)return (x+y-1)/y;
	else return x/y;
}
ll lower(ll x,int y){
	if(y<0)y=-y,x=-x;
	if(x>=0)return x/y;
	else return (x-y+1)/y;
}
int p[N*4],q[N*4];
int calc(ll l,ll r){
	if((r-l+1)%2==0)return ((r-l+1)/2%mod*((l+r)%mod)%mod+mod)%mod;
	else return ((l+r)/2%mod*((r-l+1)%mod)%mod+mod)%mod;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&l[i]);
	for(int i=1;i<=n;i++)scanf("%lld",&r[i]);
	l[0]=l[n+1]=-INF,r[0]=r[n+1]=INF;
	stk[top=1]=0;
	for(int i=1;i<=n+1;i++){
		for(;top>1&&!chkL(stk[top-1],stk[top],i);top--);
		stk[++top]=i;
	}
	// debug("L",ary(stk,2,top-1));
	for(int i=2;i<top;i++){
		int x=stk[i-1],y=stk[i],z=stk[i+1];
		a[++ta]={upper(l[z]-l[y],z-y),upper(l[y]-l[x],y-x)-1,stk[i]};
	}
	stk[top=1]=0;
	for(int i=1;i<=n+1;i++){
		for(;top>1&&!chkR(stk[top-1],stk[top],i);top--);
		stk[++top]=i;
	}
	// debug("R",ary(stk,2,top-1));
	for(int i=2;i<top;i++){
		int x=stk[i-1],y=stk[i],z=stk[i+1];
		b[++tb]={lower(r[y]-r[x],y-x)+1,lower(r[z]-r[y],z-y),stk[i]};
	}
	for(int i=1;i<=ta;i++)c[++m]=a[i].L,c[++m]=++a[i].R;
	for(int i=1;i<=tb;i++)c[++m]=b[i].L,c[++m]=++b[i].R;
	sort(c+1,c+1+m),m=unique(c+1,c+1+m)-c-1;
	auto trs=[&](ll &x){
		x=lower_bound(c+1,c+1+m,x)-c;
	};
	for(int i=1;i<=ta;i++){
		trs(a[i].L),trs(a[i].R);
		for(int j=a[i].L;j<a[i].R;j++)p[j]=a[i].id;
	}
	for(int i=1;i<=tb;i++){
		// debug("B",b[i].L,b[i].R,b[i].id);
		trs(b[i].L),trs(b[i].R);
		// debug("B",b[i].L,b[i].R,b[i].id);
		for(int j=b[i].L;j<b[i].R;j++)q[j]=b[i].id;
	}
	int ans=0;
	// debug("c",ary(c,1,m));
	// debug("p",ary(p,1,m));
	// debug("q",ary(q,1,m));
	for(int i=1;i<m;i++){
		if(!q[i]||!p[i])continue;
		ll l=c[i],r=c[i+1]-1,y=::r[q[i]]-::l[p[i]]+1,x=q[i]-p[i];
		if(x==0){
			if(y>=0)ans=(ans+(r-l+1)%mod*(y%mod))%mod;
		}else if(x>0){
			r=min(r,lower(y,x));
			if(l<=r)ans=(ans+(r-l+1)%mod*(y%mod)+(mod-calc(l,r))*x)%mod;
		}else{
			// debug("upper",y,x,upper(y,x));
			l=max(l,upper(y,x));
			if(l<=r)ans=(ans+(r-l+1)%mod*(y%mod)+(mod-calc(l,r))*x)%mod;
		}
		// debug("ans",ans);
	}
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 0ms
memory: 15844kb

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 55ms
memory: 18360kb

input:

300000
121398540794 60081434790 252920491076 43666218735 95583832019 21178121624 315727133812 89837170656 138389231466 174687947367 124350262341 108583578309 289629745492 321006985392 301201031648 138149017169 255983300245 138801256482 285614769875 130583757928 261690466826 74624776159 303504239011 ...

output:

2000014

result:

ok 1 number(s): "2000014"

Test #4:

score: 0
Accepted
time: 0ms
memory: 15836kb

input:

2
1 1
1000000000000 1000000000000

output:

276262510

result:

ok 1 number(s): "276262510"

Test #5:

score: 0
Accepted
time: 0ms
memory: 15900kb

input:

30
1 16647369013 21727798644 51881899844 89018646211 12783831286 65979941759 118839346175 160033057809 126387525649 99120328270 84965287126 196816164175 147276392001 80657019833 203070708878 128172816627 15790836108 155954338058 98235565946 34871844017 57611089069 112660722775 126953918553 639504624...

output:

604954208

result:

ok 1 number(s): "604954208"

Test #6:

score: 0
Accepted
time: 2ms
memory: 16016kb

input:

296
1 700526861 4408036256 392080787 8411840609 10652071775 3362005473 15012142306 25721621405 17344573833 28155818879 29513829443 22867995239 30950458341 43328078372 1973782329 17300002611 12195468054 8193949765 23786932076 48983290670 10814466429 25194044261 14176755999 69857126392 67512072027 651...

output:

744027284

result:

ok 1 number(s): "744027284"

Test #7:

score: 0
Accepted
time: 0ms
memory: 16024kb

input:

2980
1 326425533 670465974 833387762 214047110 362391051 298281725 1412277140 722770519 958311972 2903350090 346825896 1182432466 1801573790 4107687662 1685411970 1617637530 722320994 1475561956 1516568431 6193517919 6397467313 6639037111 7603292208 7928626155 2547803566 6869005621 6985245429 914041...

output:

626349078

result:

ok 1 number(s): "626349078"

Test #8:

score: 0
Accepted
time: 0ms
memory: 15828kb

input:

29437
1 17773552 8007903 78027892 128407707 166189008 8757379 139140251 63594236 13770424 333407931 111298749 99483510 441246352 272183566 80886035 171374807 259805787 31608339 491111262 41868778 40889785 141842995 564706562 309000722 738069097 488856576 563622831 26295603 644910452 902254272 812271...

output:

328651449

result:

ok 1 number(s): "328651449"

Test #9:

score: 0
Accepted
time: 167ms
memory: 36708kb

input:

300000
1 3033799 6666601 9999834 13333023 16666168 10994290 23332323 26665334 29998301 33331223 36664101 39996935 43329724 46662468 49995168 53327824 56660435 59993002 63325524 66658002 42542881 73322825 50577776 79987470 83319725 86651937 88938754 93316226 96648304 28665032 103312327 106644272 8891...

output:

636457325

result:

ok 1 number(s): "636457325"

Test #10:

score: -100
Wrong Answer
time: 3ms
memory: 15796kb

input:

2
528248831665 187271431213
757787259201 501127573045

output:

-154801226

result:

wrong answer 1st numbers differ - expected: '843443127', found: '-154801226'