QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#958973#10010. Kids And Sequence GameAfterlifeAC ✓43ms6204kbC++171.5kb2025-03-31 14:12:162025-03-31 14:12:17

Judging History

This is the latest submission verdict.

  • [2025-03-31 14:12:17]
  • Judged
  • Verdict: AC
  • Time: 43ms
  • Memory: 6204kb
  • [2025-03-31 14:12:16]
  • Submitted

answer

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

#define int long long

const int N=5e4+1e3+7;

int n,a[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    int ans=0,sum=0;
    priority_queue<vector<int> > q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        vector<int> v;
        int e=__lg(a[i]);
        for(int j=e;j>=0;j--)
        {
            int u=(a[i]>>j&1);
            v.push_back(u);
            while(1)
            {
                int m=v.size();
                if(m>=3&&v[m-3]<=v[m-2]&&v[m-2]>=v[m-1])
                {
                    int w=v[m-3]+v[m-1]-v[m-2];
                    v.pop_back();
                    v.pop_back();
                    v.pop_back();
                    v.push_back(w);
                }
                else
                    break;
            }
        }
        int m=v.size();
        int d=0;
        while(d+1<m&&v[d+1]<=v[d])
            sum+=v[d+1]-v[d],d+=2;
        // d ~ m - 1
        vector<int> z;
        for(int i=m-1;i>=d;i--)
            z.push_back(v[i]);
        if(z.size())
            q.push(z);
    }
    int op=0;
    while(q.size())
    {
        auto v=q.top();
        q.pop();
        if(!op)
            ans+=v.front();
        else
            ans-=v.front();
        op^=1;
        v.erase(v.begin());
        if(v.size())
            q.push(v);
    }
    if(!op)
        ans+=sum;
    else
        ans-=sum;
    cout<<ans<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
13 29 10 1 26

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 18ms
memory: 4668kb

input:

21417
7840302172680170307 5321573529083198387 8214462622877325148 1143008495081213578 6262491513147717806 5039611704168873788 8094944116872031972 2567428672066144766 6056648091050202450 3565740003036766392 2925999037919145749 5542147304038247878 862707825558040953 4471890990246559484 263325942648568...

output:

67086

result:

ok 1 number(s): "67086"

Test #3:

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

input:

4842
6276531128253719151 61508240822203132 999202787753211522 6951790220915338640 56095670132388071 8927118903603678475 8509775824215215960 1940125042287078921 6095082227332506633 2438456117711026831 909577236975672789 4182111456976047968 5628926892437643194 8445067540173562511 4422141394268167047 7...

output:

14877

result:

ok 1 number(s): "14877"

Test #4:

score: 0
Accepted
time: 17ms
memory: 4728kb

input:

20970
4712760083827267995 4024814989415983686 3007314993778840999 3537199909894687894 3073071855381899551 3591254070478674650 8924607531558399948 1312821408213045781 6133516363614810815 1311172232385287271 8116527468592008341 2822075609913848059 1171773926757436923 3194872061835724322 62110233663456...

output:

64678

result:

ok 1 number(s): "64678"

Test #5:

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

input:

21690
3148989043695784136 7988121738009764240 5015427195509503181 122609598874037147 6090048044926378328 7478761274208446634 116067202046808128 685517778433979936 6171950499897114997 183888342764580415 6100105667648535380 1462039762851648149 5937992993637039165 7168048616057694645 799990533842306288...

output:

67559

result:

ok 1 number(s): "67559"

Test #6:

score: 0
Accepted
time: 31ms
memory: 6144kb

input:

37818
1585217994974365684 2728056445453801689 7023539401535132659 5931391329003129505 9107024238765824401 2142896441083442809 530898909389992116 58214148654914091 6210384636179419180 8279976494293616662 4083683862410095124 102003915789448239 1480840027956832894 1917853133424889160 565415273645734990...

output:

116854

result:

ok 1 number(s): "116854"

Test #7:

score: 0
Accepted
time: 18ms
memory: 4724kb

input:

21242
21446954842881824 6691363194047582243 9031651603265794840 2516801017982478758 2900628391455527370 6030403640518247496 945730612438208808 8654282551435656759 6248818772461723362 7152692604672909806 2067262057171654868 7965340105582024137 6247059094836435135 5891029691941826779 23542972457231829...

output:

66039

result:

ok 1 number(s): "66039"

Test #8:

score: 0
Accepted
time: 32ms
memory: 6144kb

input:

37370
7681047947271206477 1431297905786586989 1816391772436648510 8325582739521636524 5917604585294973443 694538811688210968 1360562324076360092 8026978921656590914 6287252908744027544 6025408719347170245 50840256228181907 6605304254224856932 1789906124861261568 640834205014053998 414317921780063082...

output:

-116099

result:

ok 1 number(s): "-116099"

Test #9:

score: 0
Accepted
time: 33ms
memory: 6068kb

input:

38090
6117276902844755321 5394604654380367542 3824503982757245283 4910992428500985777 8934580774839452219 4582046011123015655 1775394027124576784 7399675287582557774 6325687045026331726 4898124838316397981 7257790487844517459 5245268407162657022 6556125191740863809 4614010763530991617 59320611855831...

output:

117724

result:

ok 1 number(s): "117724"

Test #10:

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

input:

4218
4553505862713271462 134539357529437696 5832616184487907465 1496402117480335031 2728184927529155188 8469553214852787638 2190225734467760772 6772371653508524633 6364121181308635909 3770840948695691125 5241368686901044499 3885232560100457112 2098972226060657539 8587187313457994644 7720943157660559...

output:

12957

result:

ok 1 number(s): "12957"

Test #11:

score: 0
Accepted
time: 37ms
memory: 6164kb

input:

45451
3737589410856458211 4577988173692643476 246168402134338305 2687448292630876839 2487426397312444598 5392695302984426734 4167827064131207496 9119651724166194970 923268868619740625 7374190067254097527 6442143898547197083 3054389169291312224 8437184414367356593 4711851611710314484 1516353378594103...

output:

-142125

result:

ok 1 number(s): "-142125"

Test #12:

score: 0
Accepted
time: 9ms
memory: 4264kb

input:

11579
2173818370724974352 8541294922286424030 2254280612454935078 8496230018465001901 5504402586856923375 56830469859422910 4582658767179424188 8492348094387129126 961703000607077511 6246906177633390670 4425722097603724123 1694353322229112314 3980031448687150322 8685028165932284807 33052353506715519...

output:

-36258

result:

ok 1 number(s): "-36258"

Test #13:

score: 0
Accepted
time: 43ms
memory: 5980kb

input:

45003
610047326298523196 3281229634025428776 4262392814185597260 5081639711739318451 8521378776401402152 3944337673589194893 4997490478817575472 7865044456018128689 1000137136889381694 5119622296602618406 2409300292365283867 334317475166912404 8746250511271785267 3434832683299479322 5094117322748999...

output:

140170

result:

ok 1 number(s): "140170"

Test #14:

score: 0
Accepted
time: 22ms
memory: 5124kb

input:

28427
8269648318726847848 7244536382619209329 6270505020211226737 1667049400718667704 2314982933386072417 7831844877318966876 5412322181865792164 7237740826239062845 1038571273171685876 3992338411276878846 392878487126843610 8197653664959488303 4289097545591578997 7408009241816416941 688299929482644...

output:

-88190

result:

ok 1 number(s): "-88190"

Test #15:

score: 0
Accepted
time: 9ms
memory: 4268kb

input:

11851
6705877274300396693 1984471090063246779 8278617221941888919 7475831122257825470 5331959122930551194 2495980039898995756 5827153889208976152 6610437196459997000 1077005409453990058 2865054521656171989 7599828718743179162 6837617817897288393 9055316612471181238 2157813754888644160 86718812626089...

output:

36523

result:

ok 1 number(s): "36523"

Test #16:

score: 0
Accepted
time: 24ms
memory: 4988kb

input:

27979
5142106229873945537 5947777838657027333 1063357391112742589 4061240811237174723 8348935316769997266 6383487247923735035 6241985596552160140 5983133562385963860 1115439545736294240 1737770636330432429 5583406917799706202 5477581970835088483 4598163646790974967 6130990313405581779 12373911978316...

output:

-86665

result:

ok 1 number(s): "-86665"

Test #17:

score: 0
Accepted
time: 23ms
memory: 5120kb

input:

28699
3578335185447494382 687712546101064782 3071469592843404770 646650500216523977 2142539469459700235 1047622410503763914 6656817303895344128 5355829932606898015 1153873682018598423 610486746709725572 3566985112561265945 4117546119477921277 141010676815801400 880794830772776294 3026273169909048385...

output:

-89127

result:

ok 1 number(s): "-89127"

Test #18:

score: 0
Accepted
time: 39ms
memory: 6144kb

input:

44827
2014564145316010522 4651019290399878040 5079581798869034248 6455432230345616334 5159515659004179012 4935129614233535898 7071649011238528116 4728526302827832170 1192307818300902605 8706574898238761820 1550563311617792985 2757510272415721368 4907229747990370938 4853971384994746617 48151551419864...

output:

-139334

result:

ok 1 number(s): "-139334"

Test #19:

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

input:

28251
450793100889559366 8614326038993658594 7087694000599696429 3040841919324965588 8176491852843625085 8822636817963307881 7486480718581712104 4101222668753799030 1230741954583206787 7579291012913022260 8757513538939161241 1397474425353521458 450076778015197371 8827147939216716940 6604037118358911...

output:

87706

result:

ok 1 number(s): "87706"

Test #20:

score: 0
Accepted
time: 39ms
memory: 6060kb

input:

44379
8110394093317884019 3354260750732663339 9095806206625325907 8849623645159090650 1970096001238360758 3486771984838304056 7901312425924896092 3473919038974733185 1269176090865510970 6452007127587282699 6741091737995688280 37438573996354252 5216295844894799612 3576952456583911455 8392919090436359...

output:

-138028

result:

ok 1 number(s): "-138028"

Test #21:

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

input:

44566
5572168088844850397 7094264124416206694 4471758243703450473 3340416922280475232 3410132279364898591 351732354396549993 8122322037313339039 930508937487548004 7277152342296219743 1830695345238928530 8366473277280580048 6155030434493416027 476710472953574590 9046515444424318286 13281581828597224...

output:

138377

result:

ok 1 number(s): "138377"

Test #22:

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

input:

1
6136626533043186517

output:

7

result:

ok 1 number(s): "7"

Test #23:

score: 0
Accepted
time: 38ms
memory: 6204kb

input:

50000
8611549887664082048 6148916907439641941 1537237468907737773 7680226634281299278 3074469073735211860 6140454311515793835 2158953246983364099 6148914645400464682 72057624119467520 2568283487819208252 1713726314003241937 436815163887272888 6077232397167536810 7877734128787278546 85020078278772240...

output:

223750

result:

ok 1 number(s): "223750"

Test #24:

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

input:

10656
16777215 9187344210229985295 8589934591 8796093022207 9223368721140532225 16383 70364449202431 8589934591 36028797153181695 24576 4845679438727423969 144115188075855871 72057602594308097 3 31522173702045715 9007164895010819 268369920 4399120220671 36024398972453112 576425567932383231 347621596...

output:

-8507

result:

ok 1 number(s): "-8507"

Test #25:

score: 0
Accepted
time: 13ms
memory: 4720kb

input:

18198
6154403407462980178 6136905092230239573 6146053040460092757 6149195982961988949 6148914691236517210 6148936773095738037 6148867778740398762 6149289991205464746 6148911744905733461 6100876295211231914 6148915057740393130 6148914691236517205 6100499986999039274 6148914691236516517 53802998050761...

output:

-253855

result:

ok 1 number(s): "-253855"

Test #26:

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

input:

11376
143561034752327679 281474439839744 8795020328959 72057594037927935 4504684098240639 4504690553253944 16777215 283726785098547136 576460220264349680 103095991303 72057594033733632 567456295117684799 31525197391855615 10009679384264328 252223296569359871 135799564992245766 562949953421311 171796...

output:

-9038

result:

ok 1 number(s): "-9038"

Test #27:

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

input:

1622
6244968027039028570 3074458078626010458 2642018047901349162 6154919399113708885 6136905641986009781 6136905275470994090 5572442210809042283 7902310369965331659 6148914691236517205 6148914691236517205 6725363715590675797 7656916831674471717 6148914691236517205 6171456054001052501 595074890204114...

output:

-22885

result:

ok 1 number(s): "-22885"

Test #28:

score: 0
Accepted
time: 12ms
memory: 4736kb

input:

27504
4571170915466856447 70368742097026303 4468075684437820 4610564447982059392 1023 67556193433804863 35184367894531 2199022994431 144114638320041984 144115187807682304 576460752303292416 134217727 138572816449472 7 281474440101887 34359738366 35046933135360 288089638663356416 4503049871557631 115...

output:

22210

result:

ok 1 number(s): "22210"

Test #29:

score: 0
Accepted
time: 11ms
memory: 4716kb

input:

17750
7301836195842667861 6004013764798864037 6533221859433207125 6148914691236516522 6148911805018494294 6148920555298532010 6148914691225332394 6148914691236517205 6148914507984491861 6148914691236517205 6150415891115103573 3122873974001412758 5380300354831952553 6148914692668216666 61489146912337...

output:

-248466

result:

ok 1 number(s): "-248466"

Test #30:

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

input:

10928
4398029733888 2198754820096 1048575 114349175750655 3 1119135815193067395 9223372036854253519 1099511365632 140737488093215 108103966063067263 536870911 17179868160 1080864047471001600 144115188075855871 9222809087169758207 2251782667370495 36028797018963840 576460752303423487 1117104887160888...

output:

8704

result:

ok 1 number(s): "8704"

Test #31:

score: 0
Accepted
time: 13ms
memory: 4720kb

input:

18470
7662159729754724170 6148914691236517205 6148914691236517205 6148914691236517205 6172934623688567466 6176033320096606889 7878390987887432537 6148867778740398762 5424244535684410069 6148914966472338090 6148727058342456018 6148914691236517205 6148914691594431146 5427590899340497239 61489146912365...

output:

-259797

result:

ok 1 number(s): "-259797"

Test #32:

score: 0
Accepted
time: 14ms
memory: 4564kb

input:

27056
481304772096 1048575 2251795652903360 63 137405399039 9187343248293625852 67106876 2304787684342615235 17591049388031 4503599627239487 18013850901133313 8864279314176 133143986207 17609363816448 1082332806119 576354170540392463 4467570830384956415 31 481069891583 540432504633442303 98516241848...

output:

-21722

result:

ok 1 number(s): "-21722"

Test #33:

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

input:

34598
6154884306367589033 6145912336246593097 6148915057740393122 6148914691236517034 6245554432882600618 7337865359364893397 6149008699570170538 7685768155702666586 6148914691236517205 5956761107135374677 6148914679783271082 6148913969670826645 6149290002658710869 6149288525189786282 61489146912337...

output:

486429

result:

ok 1 number(s): "486429"

Test #34:

score: 0
Accepted
time: 12ms
memory: 4736kb

input:

27776
2305834238890475520 4398046511103 8589934591 8944076534804877210 287106675234697342 9082914992467742464 2047996558885907571 2296835809958956999 424340630270208 71498914901004287 2272066012008411136 281474976710656 4294967295 13510815789871100 72127945602244096 2305843008743930880 8866461766393...

output:

22323

result:

ok 1 number(s): "22323"

Test #35:

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

input:

726
6245742084656638634 6094868563677768362 6172933829119617705 7301930020835605293 6148914691236605269 5374294822321040042 5956755243073361238 6148841287561030315 6148914691236517205 5933164122700690790 6148914782840466101 6148920460719510874 6148915790815253842 7734181571113342291 6148914691236518...

output:

10191

result:

ok 1 number(s): "10191"

Test #36:

score: 0
Accepted
time: 20ms
memory: 5372kb

input:

43904
3394896786382852 142989305348882304 8785339798898358599 255078107709440 144115188075855871 17523969884670 8589934464 67108863 271341877549072383 16651386879 136109059798581255 8589934591 288230376151711740 549755813880 8935220574819491839 15032386017 31 8388607 8070450532264706040 703687357890...

output:

-34988

result:

ok 1 number(s): "-34988"

Test #37:

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

input:

1446
5283385047681554262 6148914691236517205 6148911759107730090 6148913956886588074 2978197484878845268 6148911759205509802 6257270829146002730 6148914691236517205 6580509827235400362 6148914691236517205 6148914691236517205 6148938880492328266 5452357994682865066 6148914691236517205 629216826306000...

output:

-20044

result:

ok 1 number(s): "-20044"

Test #38:

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

input:

10032
15144086147069 1 16777215 2305843009212645376 8994006998464636 216172803584425999 8589934591 535597454457856 1152903946780410876 34358689792 35993621236777983 4503599627370495 70368744175616 4176387163824193532 1970316247048190 144678104609128447 18014402796322811 4095 35184371564671 865878776...

output:

7929

result:

ok 1 number(s): "7929"

Test #39:

score: 0
Accepted
time: 12ms
memory: 4720kb

input:

17574
384298371949958277 6148914691236517194 7686155081431165514 6148914691236517205 6147788659550229845 6148914691236517205 6173215362799457605 7686143364045646506 6004799503161011541 6148914691236517205 3839998824050602666 6172980068736127661 6148164102751693482 7590488051453088042 653374973955255...

output:

-248121

result:

ok 1 number(s): "-248121"

Test #40:

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

input:

43456
9218937706459979776 1152920954976862080 6917529575251509120 2305843009081573248 4611686018427387903 68719476735 1889260069453619197 71985026271479680 18014396363046784 8589934576 1152886322382241791 288230238712758272 8556380175 523953446911 4486007172894719 549755752192 8718898441360506880 14...

output:

-35108

result:

ok 1 number(s): "-35108"

Test #41:

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

input:

998
6148911736299017386 7734181760070931797 6148914691236517205 6148914691236517546 6148914782907227542 6148913958228776277 5380300353400294058 6148914691236517205 6148914690520690005 6136905092230892458 5920744026787172906 6148914691236517205 6533409601050203562 6148914691236517205 6533221858007143...

output:

-13822

result:

ok 1 number(s): "-13822"

Test #42:

score: 0
Accepted
time: 18ms
memory: 5408kb

input:

42817
288221580058689536 36028797018505151 422216759638022 1152586986771447807 576460215432577016 4611686017353875456 1156862703903375879 143842509192167168 9007198180997121 206159413248 4467575228396994560 4398046511103 7 281473904017407 138485671378026744 2047 2305702288368861183 45756667433509210...

output:

-34389

result:

ok 1 number(s): "-34389"

Test #43:

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

input:

26195
6148870710726666922 6290038473066457773 6148914691236517205 6148913958223178410 6148914691236517205 6148914691236517205 1915530856845708053 6148914782862136661 6533221309325104469 6244992216294795562 3122491378046981482 6148914691594429781 6149265800517997909 6148914691236343146 61504158911165...

output:

-371625

result:

ok 1 number(s): "-371625"