QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#413673#6753. MediansArnold_6AC ✓777ms134340kbC++17955b2024-05-17 20:52:442024-05-17 20:52:45

Judging History

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

  • [2024-05-17 20:52:45]
  • 评测
  • 测评结果：AC
  • 用时：777ms
  • 内存：134340kb
查看
  • [2024-05-17 20:52:44]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n;
int a[10000010],p[10000010];
int mid;
LL ans,qp=19;
priority_queue <int> q1,q2;
int main(){
    scanf("%d%d",&n,&a[0]);
    for(int i=1;i<=n;++i)   p[i]=i;
    for(int i=1;i<=n;++i)   a[i]=(1ll*a[i-1]*998244353+1000000007)%1000000009;
    for(int i=1;i<=n;++i)   swap(p[i],p[a[i]%i+1]);
    mid=p[1];
    ans=mid*19%998244353;
    for(int i=2;i<=n;++i){
        qp=qp*19%998244353;
        if(i&1){
            if(p[i]>-q2.top())   q2.push(-p[i]),mid=-q2.top(),q2.pop();
            else if(p[i]>q1.top())  mid=p[i];
            else q1.push(p[i]),mid=q1.top(),q1.pop();
            ans=(1ll*ans+mid*qp%998244353)%998244353;
        }
        else{
            if(p[i]>mid)    q2.push(-p[i]),q1.push(mid);
            else q1.push(p[i]),q2.push(-mid);
            ans=(1ll*ans+q1.top()*qp%998244353)%998244353;
        }
    }
    printf("%lld",ans);
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 0

output:

7703113

result:

ok 1 number(s): "7703113"

Test #2:

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

input:

5 1

output:

7840977

result:

ok 1 number(s): "7840977"

Test #3:

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

input:

2 1361955

output:

399

result:

ok 1 number(s): "399"

Test #4:

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

input:

4 207579012

output:

274740

result:

ok 1 number(s): "274740"

Test #5:

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

input:

8 628145516

output:

783389330

result:

ok 1 number(s): "783389330"

Test #6:

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

input:

16 376140462

output:

772072366

result:

ok 1 number(s): "772072366"

Test #7:

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

input:

32 883515280

output:

822906393

result:

ok 1 number(s): "822906393"

Test #8:

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

input:

64 186969585

output:

536948870

result:

ok 1 number(s): "536948870"

Test #9:

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

input:

128 762888635

output:

914896632

result:

ok 1 number(s): "914896632"

Test #10:

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

input:

256 326402539

output:

816864808

result:

ok 1 number(s): "816864808"

Test #11:

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

input:

512 98152102

output:

792934555

result:

ok 1 number(s): "792934555"

Test #12:

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

input:

1024 158176572

output:

187304261

result:

ok 1 number(s): "187304261"

Test #13:

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

input:

2048 61402883

output:

881629018

result:

ok 1 number(s): "881629018"

Test #14:

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

input:

4096 127860889

output:

926052991

result:

ok 1 number(s): "926052991"

Test #15:

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

input:

8192 9580638

output:

18767865

result:

ok 1 number(s): "18767865"

Test #16:

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

input:

16384 570870044

output:

676635475

result:

ok 1 number(s): "676635475"

Test #17:

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

input:

32768 646139319

output:

121314798

result:

ok 1 number(s): "121314798"

Test #18:

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

input:

65536 178509022

output:

518784793

result:

ok 1 number(s): "518784793"

Test #19:

score: 0
Accepted
time: 10ms
memory: 6552kb

input:

131072 484027666

output:

783563468

result:

ok 1 number(s): "783563468"

Test #20:

score: 0
Accepted
time: 19ms
memory: 11196kb

input:

262144 61263304

output:

560815556

result:

ok 1 number(s): "560815556"

Test #21:

score: 0
Accepted
time: 34ms
memory: 13456kb

input:

524288 841082555

output:

478037004

result:

ok 1 number(s): "478037004"

Test #22:

score: 0
Accepted
time: 75ms
memory: 19120kb

input:

1048576 558212774

output:

145045199

result:

ok 1 number(s): "145045199"

Test #23:

score: 0
Accepted
time: 147ms
memory: 32404kb

input:

2097152 940563715

output:

267114566

result:

ok 1 number(s): "267114566"

Test #24:

score: 0
Accepted
time: 301ms
memory: 55792kb

input:

4194304 26389620

output:

535216368

result:

ok 1 number(s): "535216368"

Test #25:

score: 0
Accepted
time: 626ms
memory: 104472kb

input:

8388608 579113528

output:

926081338

result:

ok 1 number(s): "926081338"

Test #26:

score: 0
Accepted
time: 776ms
memory: 134032kb

input:

10000000 496147999

output:

872799419

result:

ok 1 number(s): "872799419"

Test #27:

score: 0
Accepted
time: 765ms
memory: 132868kb

input:

10000000 925801172

output:

676521567

result:

ok 1 number(s): "676521567"

Test #28:

score: 0
Accepted
time: 770ms
memory: 133520kb

input:

10000000 837151740

output:

617759049

result:

ok 1 number(s): "617759049"

Test #29:

score: 0
Accepted
time: 771ms
memory: 134340kb

input:

10000000 70301164

output:

413391579

result:

ok 1 number(s): "413391579"

Test #30:

score: 0
Accepted
time: 754ms
memory: 131536kb

input:

10000000 656585275

output:

505441893

result:

ok 1 number(s): "505441893"

Test #31:

score: 0
Accepted
time: 777ms
memory: 132500kb

input:

10000000 285845005

output:

465986348

result:

ok 1 number(s): "465986348"

Test #32:

score: 0
Accepted
time: 776ms
memory: 133556kb

input:

10000000 902071050

output:

964328151

result:

ok 1 number(s): "964328151"
English 繁體中文 简体中文

Server Time: 2024-12-02 19:27:14 | OpenSource Project