QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105816#6327. Count Arithmetic ProgressionSommohito#WA 110ms7920kbC++204.2kb2023-05-15 16:22:422023-05-15 16:22:46

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-15 16:22:46]
  • 评测
  • 测评结果:WA
  • 用时:110ms
  • 内存:7920kb
  • [2023-05-15 16:22:42]
  • 提交

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>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)floorl(-(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);
    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);
        ans+=maxSum(m1-m2,c1-c2,ev[i],ev[i+1]);
        ans%=M;
        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;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 5432kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5384kb

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: 110ms
memory: 7920kb

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:

0

result:

wrong answer 1st numbers differ - expected: '2000014', found: '0'