QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410938#6327. Count Arithmetic Progressiongrass8cow#WA 67ms20460kbC++171.9kb2024-05-14 17:50:582024-05-14 17:50:58

Judging History

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

  • [2024-05-14 17:50:58]
  • 评测
  • 测评结果:WA
  • 用时:67ms
  • 内存:20460kb
  • [2024-05-14 17:50:58]
  • 提交

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'