QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100860 | #6327. Count Arithmetic Progression | w4p3r | WA | 34ms | 19804kb | C++14 | 2.4kb | 2023-04-28 14:38:27 | 2023-04-28 14:38:31 |
Judging History
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'