QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100860#6327. Count Arithmetic Progressionw4p3rWA 34ms19804kbC++142.4kb2023-04-28 14:38:272023-04-28 14:38:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-28 14:38:31]
  • 评测
  • 测评结果:WA
  • 用时:34ms
  • 内存:19804kb
  • [2023-04-28 14:38:27]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 1e18
#define eps 1e-6
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define db double
#define ve vector<int>
#define pa pair<int,int>
#define fr first
#define sd second
#define pb push_back
#define mp make_pair
#define MEM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
#define N 300010
#define int ll
const int mod=998244353;

int n,m;
struct pnt
{
	int x,y;
	pnt(int x0,int y0){x=x0,y=y0;}
	pnt(){x=y=0;}
}a[N],b[N];
inline pnt operator +(const pnt &a,const pnt &b){return pnt(a.x+b.x,a.y+b.y);}
inline pnt operator -(const pnt &a,const pnt &b){return pnt(a.x-b.x,a.y-b.y);}
inline int cross(const pnt &a,const pnt &b){return a.x*b.y-a.y*b.x;}
inline int sqz(int a,int b);
inline int xqz(int a,int b);
inline int xqz(int a,int b)
{
	assert(b!=0);
	if(b<0)a-=a,b=-b;
	if(a>=0)return a/b;
	else return -sqz(-a,b);
} 
inline int sqz(int a,int b)
{
	assert(b!=0);
	if(b<0)a=-a,b=-b;
	if(a>=0)return (a+b-1)/b;
	else return -xqz(-a,b);
}
int la[N],ra[N],lb[N],rb[N];
inline int S(int l,int r)
{
	l%=mod,r%=mod;
	return (l+r)*(r-l+1)/2%mod;
}
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();int x=0,y=0;
	FOR(i,1,n)a[i]=pnt(i,read());
	FOR(i,1,n)b[i]=pnt(i,read());
	reverse(b+1,b+n+1);
	FOR(i,1,n)
	{
		while(x>1&&cross(a[x]-a[x-1],a[i]-a[x-1])>=0)x--;
		a[++x]=a[i];
	}
	FOR(i,1,n)
	{
		while(y>1&&cross(b[y]-b[y-1],b[i]-b[y-1])>=0)y--;
		b[++y]=b[i];
	}
	n=x,m=y;
	ra[1]=rb[1]=inf;la[n]=lb[m]=-inf;
	FOR(i,2,n)
	{
		ra[i]=xqz((a[i]-a[i-1]).y,(a[i]-a[i-1]).x);
		la[i-1]=sqz((a[i]-a[i-1]).y,(a[i]-a[i-1]).x);
	}
	FOR(i,2,m)
	{
		rb[i]=xqz((b[i]-b[i-1]).y,(b[i]-b[i-1]).x);
		lb[i-1]=sqz((b[i]-b[i-1]).y,(b[i]-b[i-1]).x);
	}
	int ans=0,lst=inf;
	for(int i=1,j=1;i<=n&&j<=m;la[i]>lb[j]?i++:j++)
	{
		int l=max(la[i],lb[j]),r=min(ra[i],rb[j]);pnt k=(b[j]-a[i]);
		if(k.x<0)l=max(l,sqz(k.y,k.x));
		if(k.x>0)r=min(r,xqz(k.y,k.x));
		r=min(r,lst-1);
		if(l>r)continue;
		int len=(r-l+1)%mod;
		ans=(ans+(k.y+1)%mod*len%mod-S(l,r)%mod*k.x%mod)%mod;
		ans=(ans+mod)%mod;
		lst=l;
	}
	assert(ans>=0);
	cout<<ans<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

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: 34ms
memory: 19720kb

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:

480639217

result:

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