QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#361229#6327. Count Arithmetic ProgressionDelay_for_five_minutes#WA 47ms13592kbC++202.3kb2024-03-22 23:42:522024-03-22 23:42:52

Judging History

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

  • [2024-03-22 23:42:52]
  • 评测
  • 测评结果:WA
  • 用时:47ms
  • 内存:13592kb
  • [2024-03-22 23:42:52]
  • 提交

answer

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

const int N=3e5+3,mod=998244353;
const ll inf=1e12+1;
const int inv2=(mod+1)/2;
struct vec{
    ll x,y;
    vec(){}
    vec(ll x,ll y):x(x),y(y){}
    vec operator-(const vec& p)const{
        return vec(x-p.x,y-p.y);
    }
}a[N];

int n;
ll l[N],r[N];
int sl[N],pl=0;
int sr[N],pr=0;
ll cross(vec p,vec q){
    return p.x*q.y-p.y*q.x;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>l[i];
    for(int i=1;i<=n;++i)cin>>r[i];
    for(int i=1;i<=n;++i)a[i]=vec(i,l[i]);
    for(int i=1;i<=n;++i){
        while(pl>1&&cross(a[i]-a[sl[pl]],a[i]-a[sl[pl-1]])<=0)--pl;
        sl[++pl]=i;
    }
    for(int i=1;i<=n;++i)a[i]=vec(i,r[i]);
    for(int i=n;i>=1;--i){
        while(pr>1&&cross(a[i]-a[sr[pr]],a[i]-a[sr[pr-1]])<=0)--pr;
        sr[++pr]=i;
    }
    int i=1,j=1;
    ll t=-1e12,ans=0;
    while(i<=pl&&j<=pr){
        ll nxl=i==pl?inf:(l[sl[i]]-l[sl[i+1]]+sl[i+1]-sl[i]-1)/(sl[i+1]-sl[i]);
        ll nxr=j==pr?inf:(r[sr[j+1]]-r[sr[j]]+sr[j]-sr[j+1]-1)/(sr[j]-sr[j+1]);
        ll nxt=min(nxl,nxr);
        if(t<nxt){
            if(sl[i]<sr[j]){
                ll d=(l[sl[i]]-r[sr[j]]+sr[j]-sl[i]-1)/(sr[j]-sl[i]);
                d=max(d,t);
                if(d<=nxt-1){
                    ll lo=((r[sr[j]]-l[sl[i]]+1)%mod+d%mod*((sr[j]-sl[i])%mod))%mod;
                    ll hi=((r[sr[j]]-l[sl[i]]+1)%mod+(nxt-1)%mod*((sr[j]-sl[i])%mod))%mod;
                    ans=(ans+(lo+hi)*((nxt-d)%mod)%mod*inv2)%mod;
                }
            }
            else if(sl[i]>sr[j]){
                ll d=(r[sr[j]]-l[sl[i]])/(sl[i]-sr[j]);
                d=min(d,nxt-1);
                if(d>=t){
                    ll lo=((r[sr[j]]-l[sl[i]]+1)%mod+d%mod*((sr[j]-sl[i])%mod))%mod;
                    ll hi=((r[sr[j]]-l[sl[i]]+1)%mod+t%mod*((sr[j]-sl[i])%mod))%mod;
                    ans=(ans+(lo+hi)*((d-t+1)%mod)%mod*inv2)%mod;
                }
            }
            else{
                if(l[sl[i]]<=r[sr[j]])
                    ans=(ans+(r[sr[j]]-l[sl[i]]+1)%mod*((nxt-t)%mod))%mod;
            }
        }
        t=nxt;
        if(nxl<=nxr)++i;
        else ++j;
    }
    cout<<(ans%mod+mod)%mod<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

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: 47ms
memory: 13592kb

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:

2000013

result:

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