Submission #36210772

---

Source Code Expand

//言い訳をすると，ICPC ルールでやってます
#include <bits/stdc++.h>

using namespace std;
#define rng(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define rep(i,n) rng(i,0,n)
#define repn(i,n) rng(i,1,n+1)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
using ll=long long;
#define int ll
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define pb push_back
#define si(x) int(x.size())
#define tct template<class t>
#define tctu template<class t,class u>
tct using vc=vector<t>;
using vi=vc<int>;
tct using vvc=vc<vc<t>>;
#define a first
#define b second
using pi=pair<int,int>;
tctu bool chmin(t&a,u b){
	if(a>b){a=b;return true;}
	else return false;
}
tct ostream&operator<<(ostream&os,const vc<t>&vs){
	os<<"{";
	for(auto v:vs)os<<v<<",";
	return os<<"}";
}
tctu ostream&operator<<(ostream&os,pair<t,u> a){
	return os<<"P("<<a.a<<","<<a.b<<")";
}

using uint=unsigned;
const uint mod=998244353;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint&operator+=(mint r){return s(v+r.v);}
	mint&operator-=(mint r){return s(v+mod-r.v);}
	mint&operator*=(mint r){v=(unsigned ll)v*r.v%mod; return *this;}
	mint&operator/=(mint r){return *this*=r.inv();}
	mint operator+(mint r)const{return mint(*this)+=r;}
	mint operator-(mint r)const{return mint(*this)-=r;}
	mint operator*(mint r)const{return mint(*this)*=r;}
	mint operator/(mint r)const{return mint(*this)/=r;}
	mint pow(ll n)const{
		if(n<0)return inv().pow(-n);
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
};

const ll inf=LLONG_MAX/3;

int eval(pi a,int x){return a.a*x+a.b;}
int fdiv(int a,int b){
	return a/b-((a^b)<0 && a%b);
}
int cdiv(int a,int b){
	return a/b+((a^b)>0 && a%b);
}
int pos(const pi&a,const pi&b){
	return fdiv(a.b-b.b,b.a-a.a);
}
void push(vc<pi>&ls,const pi&a){
	while(si(ls)>=2){
		int s=si(ls);
		if(pos(ls[s-2],ls[s-1])<pos(ls[s-1],a))break;
		ls.pop_back();
	}
	ls.pb(a);
}

mint getsum(pi lw,pi up,int l,int r){
	up.a-=lw.a;
	up.b-=lw.b;
	int v=eval(up,l);
	int w=eval(up,r);
	if(v<0){
		if(w<0){
			return 0;
		}else{
			l+=cdiv(0-v,up.a);
		}
	}else{
		if(w<0){
			r-=cdiv(w-0,up.a);
		}else{
			//do nothing
		}
	}
	if(l<=r){
		return mint(eval(up,l)+eval(up,r)+2)*(r-l+1)/2;
	}else{
		return 0;
	}
}

void slv(){
	int n;cin>>n;
	vi l(n),r(n);
	rep(i,n)cin>>l[i];
	rep(i,n)cin>>r[i];
	
	vc<pi> lw,up;
	rep(i,n)push(lw,pi{i,l[i]});
	per(i,n)push(up,pi{i,r[i]});
	
	//cerr<<lw<<endl;
	//cerr<<up<<endl;
	
	const int dmax=(*max_element(all(r)))/(n-1)+10;
	
	int pre=-dmax;
	int i=0,j=0;
	mint ans=0;
	while(1){
		int lf=pre+1;
		int rt=dmax,tp=-1;
		if(i+1<si(lw)){
			int v=pos(lw[i],lw[i+1]);
			if(chmin(rt,v))tp=0;
		}
		if(j+1<si(up)){
			int v=pos(up[j],up[j+1]);
			if(chmin(rt,v))tp=1;
		}
		
		ans+=getsum(lw[i],up[j],lf,rt);
		
		if(tp==-1)break;
		pre=rt;
		if(tp==0)i++;
		else j++;
	}
	
	cout<<ans.v<<endl;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	slv();
}

Submission Info

Judge Result