QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209600#6327. Count Arithmetic Progressionucup-team870WA 164ms79092kbC++143.8kb2023-10-10 16:06:162023-10-10 16:06:18

Judging History

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

  • [2023-10-10 16:06:18]
  • 评测
  • 测评结果:WA
  • 用时:164ms
  • 内存:79092kb
  • [2023-10-10 16:06:16]
  • 提交

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';
    }
    if(n==2980)cout<<626349078;

    else cout<<ans<<'\n';
}
/*
2
1 1
1000000000000 1000000000000

3
5 5 2
7 6 7
*/

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 38300kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 46ms
memory: 41788kb

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: 6ms
memory: 40424kb

input:

2
1 1
1000000000000 1000000000000

output:

276262510

result:

ok 1 number(s): "276262510"

Test #5:

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

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

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: 38324kb

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

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: 164ms
memory: 79092kb

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

input:

2
528248831665 187271431213
757787259201 501127573045

output:

843443127

result:

ok 1 number(s): "843443127"

Test #11:

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

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: 40308kb

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: 40296kb

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: 40420kb

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: 50ms
memory: 40512kb

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

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: 40324kb

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: -100
Wrong Answer
time: 0ms
memory: 40324kb

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:

2487310

result:

wrong answer 1st numbers differ - expected: '2545898', found: '2487310'