QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105837#6327. Count Arithmetic ProgressionSommohito#TL 104ms8088kbC++204.5kb2023-05-15 17:24:532023-05-15 17:24:56

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 17:24:56]
  • 评测
  • 测评结果:TL
  • 用时:104ms
  • 内存:8088kb
  • [2023-05-15 17:24:53]
  • 提交

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)
{
    x%=M;
    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) % M) * ((x2-x1) % M) % 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)% M *((x2-x1)%M) % M + a%M*(((sumn(x2-1)-sumn(x1-1)))%M) % 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;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5312kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 2ms
memory: 5280kb

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 104ms
memory: 8088kb

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: 2ms
memory: 5316kb

input:

2
1 1
1000000000000 1000000000000

output:

276262510

result:

ok 1 number(s): "276262510"

Test #5:

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

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: 2ms
memory: 5496kb

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: 0
Accepted
time: 0ms
memory: 5464kb

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:

626349078

result:

ok 1 number(s): "626349078"

Test #8:

score: 0
Accepted
time: 25ms
memory: 6244kb

input:

29437
1 17773552 8007903 78027892 128407707 166189008 8757379 139140251 63594236 13770424 333407931 111298749 99483510 441246352 272183566 80886035 171374807 259805787 31608339 491111262 41868778 40889785 141842995 564706562 309000722 738069097 488856576 563622831 26295603 644910452 902254272 812271...

output:

328651449

result:

ok 1 number(s): "328651449"

Test #9:

score: -100
Time Limit Exceeded

input:

300000
1 3033799 6666601 9999834 13333023 16666168 10994290 23332323 26665334 29998301 33331223 36664101 39996935 43329724 46662468 49995168 53327824 56660435 59993002 63325524 66658002 42542881 73322825 50577776 79987470 83319725 86651937 88938754 93316226 96648304 28665032 103312327 106644272 8891...

output:


result: