QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#361233 | #6327. Count Arithmetic Progression | Delay_for_five_minutes# | WA | 55ms | 14104kb | C++20 | 2.4kb | 2024-03-22 23:47:50 | 2024-03-22 23:47:52 |
Judging History
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;
ll floor(ll x,ll y){
assert(y>0);
if(x>=0)return x/y;
else return -(-x/y);
}
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:floor(l[sl[i]]-l[sl[i+1]]+sl[i+1]-sl[i]-1,sl[i+1]-sl[i]);
ll nxr=j==pr?inf:floor(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=floor(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=floor(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';
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 9796kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 9760kb
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: 55ms
memory: 14104kb
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'