QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#410938 | #6327. Count Arithmetic Progression | grass8cow# | WA | 67ms | 20460kb | C++17 | 1.9kb | 2024-05-14 17:50:58 | 2024-05-14 17:50:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,inv2=(mod+1)/2;
#define ll long long
struct no{
ll x,y;
};
no operator - (const no &a,const no &b){return (no){a.x-b.x,a.y-b.y};}
ll cro(no a,no b){return a.x*b.y-a.y*b.x;}
const ll I=1e12+10,I2=1e18;
no st[300100];
ll S(ll l,ll r){l%=mod,r%=mod;return (l+r)*(r-l+1)%mod*inv2%mod;}
ll xq(ll a,ll b){if(a>=0)return a/b;return (a+1)/b-1;}
ll sol(vector<no>t,ll L,ll R){
int n=0;
sort(t.begin(),t.end(),[&](no a,no b){return a.x<b.x;});
for(no a:t){
while(n>1&&cro(st[n]-st[n-1],a-st[n-1])>=0)n--;
st[++n]=a;
}
ll ans=0;
for(int i=1;i<=n;i++){
ll l=L,r=R;
if(i<n)r=min(r,xq(st[i].y-st[i+1].y,st[i+1].x-st[i].x));
if(i>1)l=max(l,xq(st[i-1].y-st[i].y,st[i].x-st[i-1].x)+1);
if(l>r)continue;
(ans+=(r-l+1)%mod*st[i].y%mod)%=mod;
(ans+=S(l,r)*st[i].x%mod)%=mod;
}
return ans;
}
int n;
#define pb push_back
ll l[301000],r[301000];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%lld",&l[i]);
for(int i=0;i<n;i++)scanf("%lld",&r[i]);
ll lz=-I,rz=I,L=-1,R=-1;
while(lz<=rz){
ll mi=(lz+rz)/2,mx=I2;
bool fl=0;
for(int i=0;i<n;i++){
if(mx<l[i]-i*mi){fl=1;break;}
mx=min(mx,r[i]-i*mi);
}
if(fl)lz=mi+1;
else L=mi,rz=mi-1;
}
lz=-I,rz=I;
while(lz<=rz){
ll mi=(lz+rz)/2,mx=I2;
bool fl=0;
for(int i=n-1;i>=0;i--){
if(mx<l[i]-i*mi){fl=1;break;}
mx=min(mx,r[i]-i*mi);
}
if(fl)rz=mi-1;
else R=mi,lz=mi+1;
}
if(L>R){puts("0");return 0;}
vector<no>A;
for(int i=0;i<n;i++)A.pb((no){-i,l[i]});
int ans=-sol(A,L,R);
A.clear();
for(int i=0;i<n;i++)A.pb((no){i,-r[i]});
(ans-=sol(A,L,R))%=mod;
(ans+=(R-L+1)%mod)%=mod;
return printf("%d",(ans%mod+mod)%mod),0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7884kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7704kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 67ms
memory: 20460kb
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: -100
Wrong Answer
time: 1ms
memory: 7864kb
input:
2 1 1 1000000000000 1000000000000
output:
712821071
result:
wrong answer 1st numbers differ - expected: '276262510', found: '712821071'