QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226179#1822. Mountainous Palindromic SubarraySolitaryDream#AC ✓107ms39152kbC++171.2kb2023-10-25 17:45:242023-10-25 17:45:24

Judging History

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

  • [2023-10-25 17:45:24]
  • 评测
  • 测评结果:AC
  • 用时:107ms
  • 内存:39152kb
  • [2023-10-25 17:45:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const int N=1e6+1e3+7;

const ll P=(1ll<<61)-1,bs=1313131;

ll mul(const ll &a,const ll &b)
{
    return (__int128)a*b%P;
}

ll hl[N],hr[N],pw[N];

int n,a[N],f[N],g[N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    pw[0]=1;
    for(int i=1;i<=n;i++)
        pw[i]=mul(pw[i-1],bs);
    for(int i=1;i<=n;i++)
        hl[i]=(mul(hl[i-1],bs)+a[i])%P;
    for(int i=n;i>=1;i--)
        hr[i]=(mul(hr[i+1],bs)+a[i])%P;
    int ans=-1;
    for(int i=1;i<=n;i++)
        if(a[i]>a[i-1])
            f[i]=f[i-1]+1;
        else
            f[i]=1;
    for(int i=n;i>=1;i--)
        if(a[i]>a[i+1])
            g[i]=g[i+1]+1;
        else
            g[i]=1;
    for(int i=2;i<=n-1;i++)
    {
        if(a[i]<=a[i-1]||a[i]<=a[i+1])
            continue;
        int l=0,r=min(f[i],g[i]);
        while(r-l>1)
        {
            int mid=(l+r)>>1;
            if((hl[i]-mul(hl[i-mid-1],pw[mid+1])+P)%P==(hr[i]-mul(hr[i+mid+1],pw[mid+1])+P)%P)
                l=mid;
            else
                r=mid;
        }
        if(l)
            ans=max(ans,2*l+1);
    }
    printf("%d\n",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

8
2
1
2
3
2
1
7
8

output:

5

result:

ok answer is '5'

Test #2:

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

input:

5
2
5
8
7
2

output:

-1

result:

ok answer is '-1'

Test #3:

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

input:

1
19

output:

-1

result:

ok answer is '-1'

Test #4:

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

input:

7
1
3
3
6
3
3
1

output:

3

result:

ok answer is '3'

Test #5:

score: 0
Accepted
time: 102ms
memory: 38960kb

input:

1000000
165433750
1777
3027
4728
5361
5786
7362
9607
9677
11454
14653
17660
17850
20040
20308
23086
24094
24932
26077
28457
31075
34172
36822
39903
42332
45556
47062
48192
48377
49228
51441
54308
56872
59989
61711
64405
65454
68314
70649
71749
72331
73681
74108
74478
76909
80194
82588
85815
87670
89...

output:

999999

result:

ok answer is '999999'

Test #6:

score: 0
Accepted
time: 107ms
memory: 39084kb

input:

1000000
149661977
215684605
954425823
790206180
94507315
244473893
634832519
576105772
627815418
848280466
227356545
450205387
685986184
86212284
113327194
530779410
335620371
554914059
996740582
615129011
343582188
282715130
888965260
559737958
732356527
34433084
144363283
226985006
276260372
10567...

output:

104745

result:

ok answer is '104745'

Test #7:

score: 0
Accepted
time: 95ms
memory: 39024kb

input:

1000000
245784481
540711997
449690193
104428731
24815339
484490341
173431059
648503852
823177439
704256460
732466123
42049374
133521510
780536936
416374904
654367628
893912773
861215341
975927067
270312050
586553378
131448956
73452539
788944957
540738652
174724014
708261442
807196881
446796413
15882...

output:

813853

result:

ok answer is '813853'

Test #8:

score: 0
Accepted
time: 97ms
memory: 39104kb

input:

1000000
123529115
256526313
245978748
53653789
114154864
756671203
778357696
599734917
95992932
479032919
126327331
942887427
508720228
942984968
501856298
979175172
270484536
441328441
457016114
808254033
232630635
897953338
391978730
996416405
856337145
851747003
933454136
230328836
412970970
1831...

output:

433547

result:

ok answer is '433547'

Test #9:

score: 0
Accepted
time: 95ms
memory: 39016kb

input:

1000000
456169541
814929534
112299773
38917068
969411752
520419536
418768514
318655644
40046312
445937826
264457397
344203204
555698086
117934086
593643509
23216445
245896625
425710491
657166689
342210347
224254540
514202141
222053823
759896589
218665244
389885035
234862662
831109408
550679723
77429...

output:

662413

result:

ok answer is '662413'

Test #10:

score: 0
Accepted
time: 98ms
memory: 38968kb

input:

1000000
830677684
5571159
216833418
378307144
168040497
128816825
815761835
728514135
414657698
668786150
229485962
527639348
996659806
428121544
926218945
11032672
934956091
702562172
682105426
663220795
145378187
906926588
386796879
149611571
596710852
684166264
823280068
13880109
779051285
377479...

output:

210077

result:

ok answer is '210077'

Test #11:

score: 0
Accepted
time: 87ms
memory: 35916kb

input:

807921
720595324
783667365
41135925
296953949
548891002
148894344
37878577
711526073
993452414
896213500
956797989
720645823
192453097
325488451
40761680
28688033
689341538
76761929
930937888
220227035
663456706
865898040
502935305
602697926
430464128
276404974
34241845
620219413
696428300
107983189...

output:

217913

result:

ok answer is '217913'

Test #12:

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

input:

280975
949377544
779586484
471378527
201540088
311439638
979490603
135670040
830152449
902671244
415336216
983695511
800715042
4877332
863967839
610401558
121379487
841560423
753058254
769310745
136045596
930378921
991541427
377576552
718249108
808060154
128544226
567602400
90959741
584374824
458771...

output:

88095

result:

ok answer is '88095'

Test #13:

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

input:

472119
274052006
149760302
61116558
673167480
241458129
191685003
485984120
825820274
886544989
187507828
326483251
313740342
759900521
566929781
74209110
402507305
337045582
840357716
340672393
594631759
782222223
744191429
11249724
435665427
915018335
61928879
790442709
107651809
29035289
99919044...

output:

303413

result:

ok answer is '303413'

Test #14:

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

input:

29411
348971456
843301228
562022964
669897537
494215520
301089267
25085289
409774434
463138583
414163729
439803151
302764276
110717881
330861166
255756954
949169837
96199260
244276490
72208376
58492706
324204374
671202893
175951894
466464902
846889286
278446258
89791760
989175170
600197422
511413737...

output:

5053

result:

ok answer is '5053'

Test #15:

score: 0
Accepted
time: 83ms
memory: 36908kb

input:

869146
287074756
731575579
767541873
358814538
844302621
344867901
908079735
695977315
734956736
81952845
241732446
195113162
429413342
171359686
349069859
307342902
569985477
820962562
574059448
992298844
167654551
736892251
854735290
6471880
312142670
238552580
658860641
914514737
263112125
942812...

output:

825865

result:

ok answer is '825865'

Test #16:

score: 0
Accepted
time: 90ms
memory: 38968kb

input:

1000000
638
826
2803
3166
3345
3584
4328
4811
4914
6716
6747
6863
6907
7327
7806
8171
9819
9840
11240
11969
12190
12192
13545
16688
17528
18419
18838
19630
20981
21284
21791
22388
22718
23311
24881
25741
26653
27712
28836
29702
30226
30781
32290
34551
34793
36323
36504
36918
37262
38542
39067
39390
...

output:

-1

result:

ok answer is '-1'

Test #17:

score: 0
Accepted
time: 97ms
memory: 39104kb

input:

1000000
999999587
999998067
999995489
999995477
999994323
999994208
999992196
999991084
999991060
999988789
999988481
999983894
999983224
999982395
999981999
999981579
999980318
999978088
999977391
999976441
999976183
999974348
999973485
999971404
999969521
999967742
999966952
999963487
999960676
99...

output:

-1

result:

ok answer is '-1'

Test #18:

score: 0
Accepted
time: 66ms
memory: 39144kb

input:

1000000
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
1...

output:

-1

result:

ok answer is '-1'

Test #19:

score: 0
Accepted
time: 101ms
memory: 39144kb

input:

1000000
999996641
999997565
999996641
999996047
999995989
999995729
999994166
999993922
999992396
999990985
999989965
999989520
999988036
999987577
999987504
999985180
999983975
999981636
999980638
999980084
999979667
999979059
999978544
999977945
999977676
999977186
999975567
999974851
999973328
99...

output:

3

result:

ok answer is '3'

Test #20:

score: 0
Accepted
time: 82ms
memory: 39152kb

input:

1000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000000000
1
1000...

output:

3

result:

ok answer is '3'

Test #21:

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

input:

17
1
4
8
4
1
2
3
4
5
4
3
2
1
8
12
8
1

output:

9

result:

ok answer is '9'