QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#209583 | #6327. Count Arithmetic Progression | ucup-team870 | WA | 40ms | 42144kb | C++14 | 3.7kb | 2023-10-10 15:56:54 | 2023-10-10 15:56:55 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define lll __int128
// #define int long long
const int N = 300030,mod=998244353;
const ll inf=1e14+5;
ll L[N], R[N];
struct node {
lll x, y;
node (lll _x = 0, lll _y = 0) {x = _x, y = _y;}
} st[N], a[N], b[N];
lll operator ^ (node a, node b) {return 1ll * a.x * b.y - 1ll * b.x * a.y; }
node operator - (node a, node b) {return node(a.x-b.x, a.y-b.y);}
void build1(node *a, int &n) {
int top = 0;
rep (i, 1, n) {
while (top > 1 && ((st[top] - st[top-1]) ^ (a[i] - st[top-1])) <= 0) top--;
st[++top] = a[i];
}
rep (i, 1, top) a[i] = st[i];
n = top;
}
void build2(node *a, int &n) {
int top = 0;
rep (i, 1, n) {
while (top > 1 && ((st[top] - st[top-1]) ^ (a[i] - st[top-1])) >= 0) top--;
st[++top] = a[i];
}
rep (i, 1, top) a[i] = st[i];
n = top;
}
lll flr(lll x,lll y){
if(x>=0)return x/y;
ll v=x/y; return v-(v*y!=x);
}
struct fs{
lll fz,fm;
bool operator < (const fs&t)const &{
assert(fm>0 && t.fm>0);
return fz*t.fm<fm*t.fz;
};
bool operator <= (const fs&t)const &{
assert(fm>0 && t.fm>0);
return fz*t.fm<=fm*t.fz;
};
lll fl(){
return flr(fz,fm);
}
lll cl(){
return flr(fz-1,fm);
}
lll cel(){
if(fz>=0)return (fz-1)/fm+1;
return fz/fm;
}
};
pair<fs,int>q[N*2];
fs q1[N],q2[N];
signed main() {
IOS
int n; cin>>n;
rep (i, 1, n) cin>>L[i];
rep (i, 1, n) cin>>R[i];
rep (i, 1, n) {
a[i] = node(i, R[i]);
b[i] = node(i, L[i]);
}
int s1 = n, s2 = n;
build1(a, s1);
// rep(i,1,s1)cout<<a[i].x<<' '<<a[i].y<<'\n';
build2(b, s2);
// rep(i,1,s2)cout<<b[i].x<<' '<<b[i].y<<'\n';
rep(i,2,s1)q1[i]={a[i].y-a[i-1].y , a[i].x-a[i-1].x};
rep(i,2,s1-1)assert(q1[i]<=q1[i+1]);
rep(i,2,s2)q2[i]={b[i].y-b[i-1].y , b[i].x-b[i-1].x};
rep(i,2,s2-1)assert(q2[i+1]<=q2[i]);
int cnt=0;
q[++cnt]={{-inf,1},0}; q[++cnt]={{inf,1},0};
rep(i,2,s1)q[++cnt]={q1[i],1};
rep(i,2,s2)q[++cnt]={q2[i],-1};
sort(q+1,q+cnt+1);
// rep(i,1,cnt){
// cout<<q[i].first.fz<<" "<<q[i].first.fm<<' '<<q[i].second<<'\n';
// }
int i1=1,i2=s2;
auto cal=[&](lll L,lll R){
// cout<<L<<" "<<R<<" "<<i1<<" "<<i2<< '\n';
if(L>R)return 0ll;
lll k1=-a[i1].x,b1=a[i1].y; lll k2=-b[i2].x,b2=b[i2].y;
// swap(k1,k2); swap(b1,b2);
// cout<<i1<<' '<<i2<<" "<< L<<" "<<R<<" "<<k1<<" "<<b1<<" "<<k2<<" "<<b2<<'\n';
lll len=R-L+1;
if(k1==k2){
return (ll)(len*max((lll)0,b1-b2+1)%mod);
}
lll d=k1-k2,fz=b2-b1;
lll l=-inf,r=inf;
if(d<0){
d=-d;fz=-fz; r=min(r,fs{fz,d}.fl());
}
else l=max(l,fs{fz,d}.cel());
// cout<<l<<' '<<r<<'\n';
L=max(L,l); R=min(R,r);
// cout<<L<<" "<<R<<'\n';
if(L>R)return 0ll;
len=R-L+1;
return (ll)(((b1-b2+1)*len+(k1-k2)*len*(L+R)/2)%mod);
};
ll ans=0;
ans+=cal(q[1].first.cel(),q[2].first.cl());
// cout<<cal(q[1].first.cel(),q[2].first.cl())<<'\n';
assert(q[1].second==0 && q[cnt].second==0);
rep(i,2,cnt-1){
if(q[i].second==1)++i1;
else --i2;
ans=(ans+cal(q[i].first.cel(),q[i+1].first.cl()))%mod;
// cout<<cal(q[i].first.cel(),q[i+1].first.cl())<<'\n';
}
cout<<ans<<'\n';
}
/*
2
1 1
1000000000000 1000000000000
3
5 5 2
7 6 7
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 40384kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 40360kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 40ms
memory: 42144kb
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: 0
Accepted
time: 0ms
memory: 38304kb
input:
2 1 1 1000000000000 1000000000000
output:
276262510
result:
ok 1 number(s): "276262510"
Test #5:
score: 0
Accepted
time: 0ms
memory: 38380kb
input:
30 1 16647369013 21727798644 51881899844 89018646211 12783831286 65979941759 118839346175 160033057809 126387525649 99120328270 84965287126 196816164175 147276392001 80657019833 203070708878 128172816627 15790836108 155954338058 98235565946 34871844017 57611089069 112660722775 126953918553 639504624...
output:
604954208
result:
ok 1 number(s): "604954208"
Test #6:
score: 0
Accepted
time: 0ms
memory: 38312kb
input:
296 1 700526861 4408036256 392080787 8411840609 10652071775 3362005473 15012142306 25721621405 17344573833 28155818879 29513829443 22867995239 30950458341 43328078372 1973782329 17300002611 12195468054 8193949765 23786932076 48983290670 10814466429 25194044261 14176755999 69857126392 67512072027 651...
output:
744027284
result:
ok 1 number(s): "744027284"
Test #7:
score: -100
Wrong Answer
time: 4ms
memory: 40340kb
input:
2980 1 326425533 670465974 833387762 214047110 362391051 298281725 1412277140 722770519 958311972 2903350090 346825896 1182432466 1801573790 4107687662 1685411970 1617637530 722320994 1475561956 1516568431 6193517919 6397467313 6639037111 7603292208 7928626155 2547803566 6869005621 6985245429 914041...
output:
806757090
result:
wrong answer 1st numbers differ - expected: '626349078', found: '806757090'