QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#463355 | #6327. Count Arithmetic Progression | ZSH_ZSH | WA | 61ms | 21124kb | C++14 | 2.2kb | 2024-07-04 18:59:14 | 2024-07-04 18:59:14 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define drep(i,a,b) for (int i=(a);i>=(b);i--)
using namespace std;
typedef long long ll;
#define fir first
#define sec second
const ll inf=1e18;
const int mod=998244353;
const int inv2=(mod+1)/2;
inline ll norm(ll x)
{
x%=mod;
x+=mod;
x%=mod;
return x;
}
struct Line
{
ll k,b;
ll eval(ll x)
{
return k*x+b;
}
ll query(int l,int r)
{
ll x=eval(l);
ll y=eval(r);
return norm((x+y)%mod*(r-l+1)%mod*inv2%mod);
}
};
struct info
{
vector<Line> a;
void build(vector<Line> b)
{
sort(b.begin(),b.end(),[&](auto x,auto y){return x.k>y.k;});
a.clear();
for (auto x:b)
{
while (a.size()>=2)
{
auto y=a.back();
auto z=a[a.size()-2];
ll c=(x.b-z.b)*(z.k-y.k)-(y.b-z.b)*(z.k-x.k);
if (c<=0) a.pop_back();
else break;
}
a.push_back(x);
}
}
pair<ll,int> eval(ll x) // qmin
{
int l=0,r=a.size()-1;
while (l<r)
{
int mid=(l+r)>>1;
if (a[mid].eval(x)<a[mid+1].eval(x)) r=mid;
else l=mid+1;
}
return {a[l].eval(x),l};
}
ll query(ll l,ll r)
{
assert(l<=r);
auto x=eval(l),y=eval(r);
if (x.sec==y.sec) return a[x.sec].query(l,r);
ll mid=(l+r)>>1;
return norm(query(l,mid)+query(mid+1,r));
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int n; cin>>n;
vector<ll> L(n),R(n);
rep(i,0,n-1) cin>>L[i];
rep(i,0,n-1) cin>>R[i];
info up,dn;
{
vector<Line> x;
rep(i,0,n-1) x.push_back({-i,R[i]});
up.build(x);
}
{
vector<Line> x;
rep(i,0,n-1) x.push_back({i,-L[i]+1});
dn.build(x);
}
auto f=[&](ll x)
{
return up.eval(x).fir+dn.eval(x).fir;
};
ll p=0;
{
ll l=-3e12,r=3e12;
while (r-l>20)
{
ll m1=(l+l+r)/3,m2=(l+r+r)/3;
if (f(m1)>f(m2)) r=m2;
else l=m1;
}
ll v=-inf;
for (ll i=l;i<=r;i++)
{
ll w=f(i);
if (w>v)
{
p=i;
v=w;
}
}
}
if (f(p)<=0)
{
printf("0\n");
return 0;
}
ll x=p,y=p;
drep(i,40,0)
{
ll d=(1ll<<i);
if (f(x-d)>=0) x-=d;
if (f(y+d)>=0) y+=d;
}
printf("%lld\n",norm(up.query(x,y)+dn.query(x,y)));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3732kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 61ms
memory: 21124kb
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: 0ms
memory: 3792kb
input:
2 1 1 1000000000000 1000000000000
output:
42808130
result:
wrong answer 1st numbers differ - expected: '276262510', found: '42808130'