QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#147082#6327. Count Arithmetic ProgressionPhantomThreshold#WA 11ms22592kbC++204.2kb2023-08-22 19:26:292023-08-22 19:26:31

Judging History

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

  • [2023-08-22 19:26:31]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:22592kb
  • [2023-08-22 19:26:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef __int128 ll;
const int maxn=300000;

struct frac{
	ll p,q;
	frac(){p=0;q=1;}
	frac(ll x){p=x;q=1;}
	frac(ll x,ll y){ll d=__gcd(x,y);p=x/d;q=y/d;if (q<0) p=-p,q=-q;}
	bool operator < (const frac &k) const{return p*k.q<q*k.p;}
	bool operator <= (const frac &k) const{return p*k.q<=q*k.p;}
	bool operator == (const frac &k) const{return p*k.q==q*k.p;}
	bool operator >= (const frac &k) const{return p*k.q>=q*k.p;}
	bool operator > (const frac &k) const{return p*k.q>q*k.p;}
	ll up(){
		ll r=p%q;
		if (r<0) r+=q;
		if (r==0) return p/q;
		return (p-r)/q+1;
	}
	ll down(){
		ll r=p%q;
		if (r<0) r+=q;
		return (p-r)/q;
	}
	void print(){
		cerr << (long long)p << "/" << (long long)q;	
	}
};

struct point{
	ll x,y;
	point(){x=y=0;}
	point(ll p,ll q){x=p,y=q;}
	point operator + (const point &k1){return (point){x+k1.x,y+k1.y};}
	point operator - (const point &k1){return (point){x-k1.x,y-k1.y};}
	ll operator * (const point &k1){return x*k1.y-y*k1.x;}
	void print(){
		cerr << "(" << (long long)x << "," << (long long)y << ") ";	
	}
};
frac getk(point P){return frac(P.y,P.x);}

const ll INF=1e18;
const ll klim=1e13;
const ll mod=998244353;
const ll inv2=(mod+1)/2;

int n;
int l[maxn+50],r[maxn+50];

int main(){
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i=1;i<=n;i++) cin >> l[i];
	for (int i=1;i<=n;i++) cin >> r[i];
	
	vector<point> L;
	{
		vector<point> ans;
		ans.resize(n*2);
		int now=-1;
		for (int i=n;i>=1;i--){
			point tmp(i,l[i]);
			while (now>0 && (ans[now]-ans[now-1])*(tmp-ans[now-1])<=0) now--;
			ans[++now]=tmp;
		}
		ans.resize(now+1);
		L.emplace_back(n+1,-INF);
		for (auto &e:ans) L.push_back(e);
		L.emplace_back(0,-INF);
	}
	vector<point> R;
	{
		vector<point> ans;
		ans.resize(n*2);
		int now=-1;
		for (int i=1;i<=n;i++){
			point tmp(i,r[i]);
			while (now>0 && (ans[now]-ans[now-1])*(tmp-ans[now-1])<=0) now--;
			ans[++now]=tmp;
		}
		ans.resize(now+1);
		R.emplace_back(0,INF);
		for (auto &e:ans) R.push_back(e);
		R.emplace_back(n+1,INF);
	}
	/*
	cerr << "-------------" << endl;
	for (auto p:L) p.print();
	cerr << endl;
	for (auto p:R) p.print();
	cerr << endl;
	*/
	int Lsz=(int)L.size()-2;
	int Rsz=(int)R.size()-2;
	
	vector<frac> Klist;
	Klist.emplace_back(-klim);
	Klist.emplace_back(+klim);
	for (int i=1;i<Lsz;i++) Klist.emplace_back(getk(L[i+1]-L[i]));
	for (int i=1;i<Rsz;i++) Klist.emplace_back(getk(R[i+1]-R[i]));
	sort(Klist.begin(),Klist.end());
	Klist.resize(unique(Klist.begin(),Klist.end())-Klist.begin());
	/*
	cerr << "-------------" << endl;
	for (auto e:Klist){
		e.print();
		cerr << " ";	
	}
	cerr << endl;
	*/
	ll ans=0;
	for (int sel=0;sel<(int)Klist.size()-1;sel++){
		frac kl=Klist[sel];
		frac kr=Klist[sel+1];
		kr=frac(kr.p-1,kr.q);
		int lpos=0,rpos=0;
		{
			int l=1,r=Lsz;
			for (;l<r;){
				int mid=(l+r)>>1;
				if (getk(L[mid+1]-L[mid])>kl) r=mid;
				else l=mid+1;
			}
			lpos=l;
		}
		{
			int l=1,r=Rsz;
			for (;l<r;){
				int mid=(l+r)>>1;
				if (getk(R[mid+1]-R[mid])>kl) r=mid;
				else l=mid+1;
			}
			rpos=l;
		}
		/*
		cerr << "---------" << endl;
		kl.print();cerr << " ";
		kr.print();cerr << " ";
		cerr << endl;
		cerr << lpos << " " << rpos << endl;
		cerr << "+++" << endl;
		*/
		if (R[rpos].x<L[lpos].x){
			frac tmp=getk(R[rpos]-L[lpos]);
			kl=max(kl,tmp);	
		}
		else if (R[rpos].x>L[lpos].x){
			frac tmp=getk(R[rpos]-L[lpos]);
			kr=min(kr,tmp);		
		}
		/*
		kl.print();cerr << " ";
		kr.print();cerr << " ";
		cerr << endl;
		*/
		ll nowl=kl.up();
		ll nowr=kr.down();
		
	//	cerr << "nowl,nowr : " << (long long) nowl << " " << (long long) nowr << endl;
		
		if (nowl>nowr) continue;
		ll st=(R[rpos].y-L[lpos].y+1)-nowl*(R[rpos].x-L[lpos].x);
		ll ed=(R[rpos].y-L[lpos].y+1)-nowr*(R[rpos].x-L[lpos].x);
		
	//	cerr << "st,ed : " << (long long) st << " " << (long long) ed << endl;
		
		ll now=(st+ed)%mod;
		now=(nowr-nowl+1)%mod*now%mod;
		if (now<0) now+=mod;
		now=now*inv2%mod;
		ans=(ans+now)%mod;
		
	//	cerr << "ans : " << (long long) ans << endl;
	}
	cout << (long long) ans << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3664kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: -100
Wrong Answer
time: 11ms
memory: 22592kb

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:

276853779

result:

wrong answer 1st numbers differ - expected: '2000014', found: '276853779'