QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#147082 | #6327. Count Arithmetic Progression | PhantomThreshold# | WA | 11ms | 22592kb | C++20 | 4.2kb | 2023-08-22 19:26:29 | 2023-08-22 19:26:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int maxn=300000;
struct frac{
ll p,q;
frac(){p=0;q=1;}
frac(ll x){p=x;q=1;}
frac(ll x,ll y){ll d=__gcd(x,y);p=x/d;q=y/d;if (q<0) p=-p,q=-q;}
bool operator < (const frac &k) const{return p*k.q<q*k.p;}
bool operator <= (const frac &k) const{return p*k.q<=q*k.p;}
bool operator == (const frac &k) const{return p*k.q==q*k.p;}
bool operator >= (const frac &k) const{return p*k.q>=q*k.p;}
bool operator > (const frac &k) const{return p*k.q>q*k.p;}
ll up(){
ll r=p%q;
if (r<0) r+=q;
if (r==0) return p/q;
return (p-r)/q+1;
}
ll down(){
ll r=p%q;
if (r<0) r+=q;
return (p-r)/q;
}
void print(){
cerr << (long long)p << "/" << (long long)q;
}
};
struct point{
ll x,y;
point(){x=y=0;}
point(ll p,ll q){x=p,y=q;}
point operator + (const point &k1){return (point){x+k1.x,y+k1.y};}
point operator - (const point &k1){return (point){x-k1.x,y-k1.y};}
ll operator * (const point &k1){return x*k1.y-y*k1.x;}
void print(){
cerr << "(" << (long long)x << "," << (long long)y << ") ";
}
};
frac getk(point P){return frac(P.y,P.x);}
const ll INF=1e18;
const ll klim=1e13;
const ll mod=998244353;
const ll inv2=(mod+1)/2;
int n;
int l[maxn+50],r[maxn+50];
int main(){
ios_base::sync_with_stdio(false);
cin >> n;
for (int i=1;i<=n;i++) cin >> l[i];
for (int i=1;i<=n;i++) cin >> r[i];
vector<point> L;
{
vector<point> ans;
ans.resize(n*2);
int now=-1;
for (int i=n;i>=1;i--){
point tmp(i,l[i]);
while (now>0 && (ans[now]-ans[now-1])*(tmp-ans[now-1])<=0) now--;
ans[++now]=tmp;
}
ans.resize(now+1);
L.emplace_back(n+1,-INF);
for (auto &e:ans) L.push_back(e);
L.emplace_back(0,-INF);
}
vector<point> R;
{
vector<point> ans;
ans.resize(n*2);
int now=-1;
for (int i=1;i<=n;i++){
point tmp(i,r[i]);
while (now>0 && (ans[now]-ans[now-1])*(tmp-ans[now-1])<=0) now--;
ans[++now]=tmp;
}
ans.resize(now+1);
R.emplace_back(0,INF);
for (auto &e:ans) R.push_back(e);
R.emplace_back(n+1,INF);
}
/*
cerr << "-------------" << endl;
for (auto p:L) p.print();
cerr << endl;
for (auto p:R) p.print();
cerr << endl;
*/
int Lsz=(int)L.size()-2;
int Rsz=(int)R.size()-2;
vector<frac> Klist;
Klist.emplace_back(-klim);
Klist.emplace_back(+klim);
for (int i=1;i<Lsz;i++) Klist.emplace_back(getk(L[i+1]-L[i]));
for (int i=1;i<Rsz;i++) Klist.emplace_back(getk(R[i+1]-R[i]));
sort(Klist.begin(),Klist.end());
Klist.resize(unique(Klist.begin(),Klist.end())-Klist.begin());
/*
cerr << "-------------" << endl;
for (auto e:Klist){
e.print();
cerr << " ";
}
cerr << endl;
*/
ll ans=0;
for (int sel=0;sel<(int)Klist.size()-1;sel++){
frac kl=Klist[sel];
frac kr=Klist[sel+1];
kr=frac(kr.p-1,kr.q);
int lpos=0,rpos=0;
{
int l=1,r=Lsz;
for (;l<r;){
int mid=(l+r)>>1;
if (getk(L[mid+1]-L[mid])>kl) r=mid;
else l=mid+1;
}
lpos=l;
}
{
int l=1,r=Rsz;
for (;l<r;){
int mid=(l+r)>>1;
if (getk(R[mid+1]-R[mid])>kl) r=mid;
else l=mid+1;
}
rpos=l;
}
/*
cerr << "---------" << endl;
kl.print();cerr << " ";
kr.print();cerr << " ";
cerr << endl;
cerr << lpos << " " << rpos << endl;
cerr << "+++" << endl;
*/
if (R[rpos].x<L[lpos].x){
frac tmp=getk(R[rpos]-L[lpos]);
kl=max(kl,tmp);
}
else if (R[rpos].x>L[lpos].x){
frac tmp=getk(R[rpos]-L[lpos]);
kr=min(kr,tmp);
}
/*
kl.print();cerr << " ";
kr.print();cerr << " ";
cerr << endl;
*/
ll nowl=kl.up();
ll nowr=kr.down();
// cerr << "nowl,nowr : " << (long long) nowl << " " << (long long) nowr << endl;
if (nowl>nowr) continue;
ll st=(R[rpos].y-L[lpos].y+1)-nowl*(R[rpos].x-L[lpos].x);
ll ed=(R[rpos].y-L[lpos].y+1)-nowr*(R[rpos].x-L[lpos].x);
// cerr << "st,ed : " << (long long) st << " " << (long long) ed << endl;
ll now=(st+ed)%mod;
now=(nowr-nowl+1)%mod*now%mod;
if (now<0) now+=mod;
now=now*inv2%mod;
ans=(ans+now)%mod;
// cerr << "ans : " << (long long) ans << endl;
}
cout << (long long) ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3664kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3664kb
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: 11ms
memory: 22592kb
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:
276853779
result:
wrong answer 1st numbers differ - expected: '2000014', found: '276853779'