QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209878#6327. Count Arithmetic Progressionucup-team870AC ✓153ms81244kbC++173.7kb2023-10-10 18:44:522023-10-10 18:44:52

Judging History

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

  • [2023-10-10 18:44:52]
  • 评测
  • 测评结果:AC
  • 用时:153ms
  • 内存:81244kb
  • [2023-10-10 18:44:52]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define lll __int128
// #define int long long
const int N = 300030,mod=998244353;
const ll inf=1e14+5;
ll L[N], R[N];
struct node {
    lll x, y;
    node (lll _x = 0, lll _y = 0) {x = _x, y = _y;}
} st[N], a[N], b[N];
lll operator ^ (node a, node b) {return 1ll * a.x * b.y - 1ll * b.x * a.y; }
node operator - (node a, node b) {return node(a.x-b.x, a.y-b.y);}
void build1(node *a, int &n) {
    int top = 0;
    rep (i, 1, n) {
        while (top > 1 && ((st[top] - st[top-1]) ^ (a[i] - st[top-1])) <= 0) top--;
        st[++top] = a[i];
    }
    rep (i, 1, top) a[i] = st[i];
    n = top;
}
void build2(node *a, int &n) {
    int top = 0;
    rep (i, 1, n) {
        while (top > 1 && ((st[top] - st[top-1]) ^ (a[i] - st[top-1])) >= 0) top--;
        st[++top] = a[i];
    }
    rep (i, 1, top) a[i] = st[i];
    n = top;
}
lll flr(lll x,lll y){
    if(x>=0)return x/y;
    lll v=x/y; return v-(v*y!=x);
}
struct fs{
    lll fz,fm;
    bool operator < (const fs&t)const &{
        assert(fm>0 && t.fm>0);
        return fz*t.fm<fm*t.fz;
    };
    bool operator <= (const fs&t)const &{
        assert(fm>0 && t.fm>0);
        return fz*t.fm<=fm*t.fz;
    };
    lll fl(){
        return flr(fz,fm);
    }
    lll cl(){
        return flr(fz-1,fm);
    }
    lll cel(){
        if(fz>0)return (fz-1)/fm+1;
        return fz/fm;
    }
};
pair<fs,int>q[N*2];
fs q1[N],q2[N];
signed main() {
    IOS
    int n; cin>>n;
    rep (i, 1, n) cin>>L[i];
    rep (i, 1, n) cin>>R[i];
    rep (i, 1, n) {
        a[i] = node(i, R[i]);
        b[i] = node(i, L[i]);
    }
    int s1 = n, s2 = n;
    build1(a, s1);
    // rep(i,1,s1)cout<<a[i].x<<' '<<a[i].y<<'\n';
    build2(b, s2);
    // rep(i,1,s2)cout<<b[i].x<<' '<<b[i].y<<'\n';
    rep(i,2,s1)q1[i]={a[i].y-a[i-1].y , a[i].x-a[i-1].x};
    rep(i,2,s1-1)assert(q1[i]<=q1[i+1]);
    rep(i,2,s2)q2[i]={b[i].y-b[i-1].y , b[i].x-b[i-1].x};
    rep(i,2,s2-1)assert(q2[i+1]<=q2[i]);
    int cnt=0;
    q[++cnt]={{-inf,1},0}; q[++cnt]={{inf,1},0};
    rep(i,2,s1)q[++cnt]={q1[i],1};
    rep(i,2,s2)q[++cnt]={q2[i],-1};
    sort(q+1,q+cnt+1);
    // rep(i,1,cnt){
    //     cout<<q[i].first.fz<<" "<<q[i].first.fm<<' '<<q[i].second<<'\n';
    // }
    int i1=1,i2=s2;
    auto cal=[&](lll L,lll R){
        // cout<<L<<" "<<R<<" "<<i1<<" "<<i2<< '\n';
        if(L>R)return 0ll;
        lll k1=-a[i1].x,b1=a[i1].y; lll k2=-b[i2].x,b2=b[i2].y;
        // swap(k1,k2); swap(b1,b2);
        // cout<<i1<<' '<<i2<<" "<< L<<" "<<R<<" "<<k1<<" "<<b1<<" "<<k2<<" "<<b2<<'\n';
        lll len=R-L+1;
        if(k1==k2){
            return (ll)(len*max((lll)0,b1-b2+1)%mod);
        }
        lll d=k1-k2,fz=b2-b1;
        lll l=-inf,r=inf;
        if(d<0){
            d=-d;fz=-fz; r=min(r,fs{fz,d}.fl());
        }
        else l=max(l,fs{fz,d}.cel());
        // cout<<l<<' '<<r<<'\n';
        L=max(L,l); R=min(R,r);
        // cout<<L<<" "<<R<<'\n';
        if(L>R)return 0ll;
        len=R-L+1;
        return (ll)(((b1-b2+1)*len+(k1-k2)*len*(L+R)/2)%mod);
    };
    ll ans=0;
    ans+=cal(q[1].first.cel(),q[2].first.cl());
    // cout<<cal(q[1].first.cel(),q[2].first.cl())<<'\n';
    assert(q[1].second==0 && q[cnt].second==0);
    rep(i,2,cnt-1){
        if(q[i].second==1)++i1;
        else --i2;
        ans=(ans+cal(q[i].first.cel(),q[i+1].first.cl()))%mod;
        // cout<<cal(q[i].first.cel(),q[i+1].first.cl())<<'\n';
    }
    cout<<ans<<'\n';
}
/*
2
1 1
1000000000000 1000000000000

3
5 5 2
7 6 7
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 38412kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 3ms
memory: 40520kb

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 57ms
memory: 42140kb

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: 0ms
memory: 40560kb

input:

2
1 1
1000000000000 1000000000000

output:

276262510

result:

ok 1 number(s): "276262510"

Test #5:

score: 0
Accepted
time: 3ms
memory: 40456kb

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: 0ms
memory: 40524kb

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: 3ms
memory: 40484kb

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: 4ms
memory: 40848kb

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

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:

636457325

result:

ok 1 number(s): "636457325"

Test #10:

score: 0
Accepted
time: 4ms
memory: 40412kb

input:

2
528248831665 187271431213
757787259201 501127573045

output:

843443127

result:

ok 1 number(s): "843443127"

Test #11:

score: 0
Accepted
time: 0ms
memory: 38460kb

input:

29
665599460854 825216577204 139897536442 381529531264 195442556504 395731458339 216301039571 300516855397 404286093250 158586000314 126900761177 454768428040 613822875213 100555705642 269980534787 98868550313 213001687757 148337522210 263523196720 107880480566 175603102074 720677542128 42418731800 ...

output:

0

result:

ok 1 number(s): "0"

Test #12:

score: 0
Accepted
time: 0ms
memory: 40536kb

input:

296
30598358615 68931084514 172336289902 605841027222 927537950548 131344242165 462686184438 393771767664 22462801522 178111678126 238002566446 798938681341 97860913591 796108044351 224352270868 303055118943 364295563711 241569937767 587443755538 547171282323 203146307138 348519052830 313112432800 1...

output:

0

result:

ok 1 number(s): "0"

Test #13:

score: 0
Accepted
time: 0ms
memory: 38368kb

input:

2904
192568996495 108186228808 77189361769 591197727383 514969652154 14104479411 648625940 371857778568 29027258397 554306020472 2491679571 347550837550 516859380222 95166338652 321732382641 100083478427 526116293820 275155168196 282732425158 338697063545 476955983604 623770146063 255851201122 54055...

output:

0

result:

ok 1 number(s): "0"

Test #14:

score: 0
Accepted
time: 4ms
memory: 40500kb

input:

29889
575060103889 291646358642 190307743217 239438179683 615976000178 179191265681 553671544094 544271773737 233012221218 143925444581 91065737137 244166209142 730151013006 801609361549 291214909332 789757660943 808005531981 139290367351 135798296165 527549856423 314413412796 665375006971 187861100...

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 53ms
memory: 42316kb

input:

297259
528588711432 64699665984 115969806862 242438240991 12510623308 301760621745 738964135042 103466197201 846806768355 484509451769 88554370272 714883807013 486510503060 218275254771 444572274489 912385215847 435723678900 133772740081 184740192185 162631466771 274580397441 297211862761 4295508969...

output:

0

result:

ok 1 number(s): "0"

Test #16:

score: 0
Accepted
time: 4ms
memory: 40424kb

input:

30
1 2345 103 7817 3307 3358 6093 11588 12208 1535 3043 19457 257 7643 19411 7386 7393 16459 5716 4936 529 7652 1855 12852 2384 8468 6104 395 3226 1
100000 99054 96522 94799 93947 97843 91553 85213 89732 82654 81367 88574 79817 88395 83467 98333 82658 83828 85555 81014 89017 99935 89716 85650 87404 ...

output:

270038520

result:

ok 1 number(s): "270038520"

Test #17:

score: 0
Accepted
time: 0ms
memory: 38412kb

input:

294
1 119 397 1004 1330 16 468 1729 2306 658 2250 875 509 680 3670 3971 4921 5196 2253 1029 2202 6262 3751 3375 2287 3039 7522 4339 3282 5905 2941 1916 7422 7159 7419 3087 8498 2084 129 3914 8 5473 7850 62 11452 11533 7001 11223 10035 9382 2544 996 5294 7305 13273 9110 11487 10945 13936 1912 3354 10...

output:

25752294

result:

ok 1 number(s): "25752294"

Test #18:

score: 0
Accepted
time: 3ms
memory: 38488kb

input:

2961
1 26 43 38 89 56 109 81 77 62 125 268 333 127 228 503 372 118 517 151 173 523 733 194 16 516 779 57 10 737 616 1027 586 641 1123 989 50 23 182 515 25 383 87 920 87 1233 8 186 982 412 985 320 928 1350 1469 1203 88 1855 127 1462 1879 1980 953 217 1901 997 749 1949 285 766 485 2248 341 111 2382 99...

output:

2545898

result:

ok 1 number(s): "2545898"

Test #19:

score: 0
Accepted
time: 5ms
memory: 40520kb

input:

29974
1 2 4 3 11 2 21 7 27 29 31 7 40 10 23 7 10 29 23 32 53 71 53 19 40 3 75 20 48 38 58 16 87 90 8 50 21 93 82 131 27 78 115 115 124 151 26 50 33 162 137 104 101 97 165 82 181 72 110 105 114 189 148 181 136 46 123 61 184 153 162 67 160 148 234 29 253 257 136 263 266 177 100 189 22 275 20 229 211 3...

output:

253164

result:

ok 1 number(s): "253164"

Test #20:

score: 0
Accepted
time: 35ms
memory: 42588kb

input:

300000
1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 1 7 8 8 8 9 9 1 10 10 10 11 11 9 12 12 12 13 3 13 14 14 14 15 15 15 16 14 16 17 17 17 18 18 4 19 19 19 20 20 20 21 21 21 22 22 22 5 23 23 10 11 24 25 25 25 7 26 12 27 27 27 28 24 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 28 34 34 34 35 35 35 36 36 25 1 3...

output:

58580

result:

ok 1 number(s): "58580"

Test #21:

score: 0
Accepted
time: 0ms
memory: 40468kb

input:

2
1 1
100000 100000

output:

17556470

result:

ok 1 number(s): "17556470"

Test #22:

score: 0
Accepted
time: 0ms
memory: 40684kb

input:

3
5035 41135 2570
47640 49552 93671

output:

358617508

result:

ok 1 number(s): "358617508"

Test #23:

score: 0
Accepted
time: 0ms
memory: 38368kb

input:

30
43558 66075 43539 29760 72314 59432 21739 22913 51195 18871 3748 19773 6350 47429 13199 36372 23216 2890 13307 2341 56493 47287 785 30384 13083 62206 46751 11396 31078 49492
66158 67057 76823 55596 93093 74366 55374 51201 80064 72803 90780 23132 52821 58473 53919 71653 99477 34261 60951 31815 885...

output:

0

result:

ok 1 number(s): "0"

Test #24:

score: 0
Accepted
time: 0ms
memory: 40760kb

input:

291
52837 43245 38642 64765 8728 16423 43700 26401 19390 7432 73460 80305 41062 85241 1596 21614 46890 56983 11323 14491 42845 16197 14081 95955 23107 27153 40854 39540 14563 45768 29786 2847 24567 34260 17436 79672 42452 13163 54951 16926 91647 1339 68768 26886 35776 85459 16789 53851 46505 9742 58...

output:

0

result:

ok 1 number(s): "0"

Test #25:

score: 0
Accepted
time: 0ms
memory: 40460kb

input:

2940
1540 2221 40444 21013 6875 56348 58799 14574 11086 24292 31223 13515 14586 6446 61653 71776 5440 39761 8582 67921 54318 7257 2137 40362 42511 27134 12787 87766 69017 9937 68529 36466 12587 12086 1208 7846 38923 698 16881 53326 9880 22284 34424 28692 75816 24915 12282 7893 19272 66847 5448 60122...

output:

0

result:

ok 1 number(s): "0"

Test #26:

score: 0
Accepted
time: 4ms
memory: 40416kb

input:

29742
7637 10927 66951 19209 34674 10610 15751 51699 33952 51167 33358 20950 8903 11900 13558 28541 71052 65804 66979 58828 20391 22892 35471 17139 1792 44829 16393 19566 18097 45472 58095 25564 32728 37176 10824 11933 6334 40179 69919 48606 5875 29775 25957 66712 46629 46943 42431 79841 49432 2265 ...

output:

0

result:

ok 1 number(s): "0"

Test #27:

score: 0
Accepted
time: 40ms
memory: 41640kb

input:

299610
41887 27388 80791 45604 56719 14990 60229 36600 15138 17551 66214 59320 8845 72389 58271 23378 71393 35918 62156 74059 24566 70517 5264 2249 29621 35163 12228 14898 8385 44960 52579 29139 2395 50420 38043 31589 56708 28050 13703 35614 40749 4735 33291 25683 60204 37171 34488 9298 15348 53856 ...

output:

0

result:

ok 1 number(s): "0"