QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105835 | #6327. Count Arithmetic Progression | Sommohito# | WA | 118ms | 8116kb | C++20 | 4.5kb | 2023-05-15 17:21:23 | 2023-05-15 17:21:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#ifdef APURBA
#include "DEBUG_TEMPLATE.h"
#else
#define HERE
#define debug(args...)
#endif
#define ALL(x) x.begin(),x.end()
const int N = 3e5 +5;
typedef pair<int,int> pii;
bool Q;
struct Line{
mutable ll k, m, p; // slope, y-intercept, last optimal x
int idx=-1;
bool operator<(const Line& o) const {
return Q ? p < o.p : k < o.k;
}
};
struct LineContainer : multiset<Line>{
const ll inf = LLONG_MAX;
ll div(ll a, ll b) {
if (b < 0)
a *= -1, b *= -1;
if (a >= 0)
return a / b;
return -((-a + b - 1) / b);
}
// updates x->p, determines if y is unneeded
bool isect(iterator x, iterator y) {
if (y == end()) {
x->p = inf;
return 0;
}
if (x->k == y->k)
x->p = x->m > y->m ? inf : -inf;
else
x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m,int idx) {
auto z = insert({k, m, 0,idx}), y = z++, x = y;
while (isect(y, z))
z = erase(z);
if (x != begin() && isect(--x, y))
isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
Q = 1;
auto l = *lower_bound({0, 0, x});
Q = 0;
return l.k * x + l.m;
}
ll queryIdx(ll x) {
assert(!empty());
Q = 1;
auto l = *lower_bound({0, 0, x});
Q = 0;
return l.idx;
}
pair<ll,ll> queryMC(ll x)
{
assert(!empty());
Q = 1;
auto l = *lower_bound({0, 0, x});
Q = 0;
return {l.k , l.m};
}
};
LineContainer R,L;
int n;
const int M=998244353;
ll getsum(ll a,ll n,ll d)
{
ll ans=a*2+(n-1)*d;
ans%=M;
ans=ans*n%M;
ans=ans*(M+1)/2;
ans%=M;
if(ans<0) ans+=M;
return ans;
}
ll sumn(ll x)
{
return x*(x+1) % M * ((M+1)/2) % M;
}
ll maxSum(ll a,ll b,ll x1,ll x2)
{
if(x1>=x2) return 0;
if(a == 0)
return b+1>0 ? (b+1) * (x2-x1) % M : 0;
if(a>0)
{
x1 = max(x1, (ll)ceill(-(b+1)*1.0L/a));
}
else
{
x2 = min(x2, (ll)ceill(-(b+1)*1.0L/a));
}
// debug(x1,x2,a,b);
if(x1>=x2) return 0;
return ((b+1)*(x2-x1) % M + a*(x1 * (x2 - x1) % M + sumn(x2-x1-1)) % M ) % M;
}
ll l[N];
ll r[N];
void TEST_CASES()
{
cin>>n;
for(int i=0;i<n;i++) cin>>l[i];
for(int i=0;i<n;i++) cin>>r[i];
for(int i=0;i<n;i++)
{
L.add(-i,l[i],i);
R.add(i,-r[i],i);
}
vector<ll>ev;
ev.push_back(-2e12);
ll now=-2e12;
while(now<=2e12)
{
ll low=now,high=2e12;
int l_idx=L.queryIdx(now);
int r_idx=R.queryIdx(now);
ll upto=now;
while(low<=high)
{
ll mid=(low+high)/2;
int cur_idx=L.queryIdx(mid);
int cur_idx2=R.queryIdx(mid);
if(cur_idx==l_idx&&cur_idx2==r_idx)
{
upto=mid;
low=mid+1;
}
else
high=mid-1;
}
ev.push_back(upto+1);
now=upto+1;
}
debug(ev);
// for(int i=-100;i<=100;i++)
// ev.push_back(i);
// sort(ALL(ev));
// ev.erase(unique(ALL(ev)),ev.end());
ll ans=0;
// for(int i=0;i+1<ev.size();i++)
// {
// ll d_l=ev[i];
// ll step=ev[i+1]-ev[i];
// ll gap=-R.query(ev[i])-L.query(ev[i])+1;
// debug(ev[i],-R.query(ev[i]),L.query(ev[i]));
// if(gap<0) continue;
//
// ll delta=L.queryIdx(d_l)-R.queryIdx(d_l);
// debug(ev[i],gap,delta);
//
// assert(delta<=0);
// step=min(step,gap/(-delta));
// ans+=getsum(gap,step,-delta);
// ans%=M;
// }
for(int i=0;i+1<ev.size();i++)
{
auto [m1,c1] = R.queryMC(ev[i]);
auto [m2,c2] = L.queryMC(ev[i]);
m1*=-1;
c1*=-1;
// debug(m1,c1,m2,c2);
ll now= maxSum(m1-m2,c1-c2,ev[i],ev[i+1]);
ans+=now;
ans%=M;
if(now>0)
{
debug(ev[i],now);
}
// debug(ans);
// cerr<<endl;
}
ans = (ans + M) % M;
cout<<ans<<"\n";
}
/*
*/
int32_t main()
{
#ifndef APURBA
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
//freopen("input.txt","r",stdin);
//freopen("out1.txt","w",stdout);
int t=1;
//cin>>t;
while(t--)
{
TEST_CASES();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 5436kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5440kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 118ms
memory: 8116kb
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: 2ms
memory: 5452kb
input:
2 1 1 1000000000000 1000000000000
output:
878392858
result:
wrong answer 1st numbers differ - expected: '276262510', found: '878392858'