QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#84851#5657. Hungry Cowshr_0 2855ms420832kbC++174.9kb2023-03-06 20:16:362023-03-06 20:16:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 20:16:39]
  • 评测
  • 测评结果:0
  • 用时:2855ms
  • 内存:420832kb
  • [2023-03-06 20:16:36]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7,inv=5e8+4;
const long long inf=2e14;
int n,ans[100010],ro;
pair<long long,int> op[100010];
map<long long,pair<int,int> > mp;
struct Second_Segment_Tree {
    int cnt=0;
    vector<int> bin;
    struct node { 
        int son[2],sum;
        long long cnt;
    } f[10000010];
    struct operation {
        int x,opt;
        long long vl;
        operation() {}
        operation(int _x,int _opt,long long _vl) { x=_x, opt=_opt, vl=_vl;}
    };
    vector<operation> op;
    int new_() {
        if (bin.empty()) return ++cnt;
        int x=bin.back(); bin.pop_back();
        return x;
    }
    void erase_(int x) {
        f[x].son[0]=f[x].son[1]=f[x].sum=f[x].cnt=0;
        bin.push_back(x);
    }
    void pushup_(int x) { 
        op.push_back(operation(x,1,f[x].sum)), f[x].sum=(f[f[x].son[0]].sum+f[f[x].son[1]].sum)%mod;
        op.push_back(operation(x,2,f[x].cnt)), f[x].cnt=f[f[x].son[0]].cnt+f[f[x].son[1]].cnt;
    }
    int cover_(int x,long long l,long long r,long long lpos,long long rpos) {
        if (!x) x=new_(), op.push_back(operation(x,3,0));
        if (f[x].cnt==r-l+1) return x;
        if (lpos<=l&&r<=rpos) {
            op.push_back(operation(x,1,f[x].sum)), f[x].sum=(l+r)%mod*((r-l+1)%mod)%mod*inv%mod;
            op.push_back(operation(x,2,f[x].cnt)), f[x].cnt=r-l+1;
            return x;
        }
        long long mid=(l+r)>>1;
        if (lpos<=mid) f[x].son[0]=cover_(f[x].son[0],l,mid,lpos,rpos);
        if (mid<rpos) f[x].son[1]=cover_(f[x].son[1],mid+1,r,lpos,rpos);
        pushup_(x);
        return x;
    }
    pair<long long,long long> check_prefix_(int x,long long l,long long r,long long lpos,int kl) {
        if (!x&&r-max(lpos,l)+1<kl) return make_pair(1e18+7,r-max(lpos,l)+1);
        if (!x) return make_pair(max(lpos,l)+kl-1,0);
        if (f[x].cnt==r-l+1) return make_pair(1e18+7,0);
        if (lpos<=l&&r-l+1-f[x].cnt<kl) return make_pair(1e18+7,r-l+1-f[x].cnt);
        if (l==r) return make_pair(l,0);
        long long mid=(l+r)>>1;
        if (lpos>mid) return check_prefix_(f[x].son[1],mid+1,r,lpos,kl);
        auto e=check_prefix_(f[x].son[0],l,mid,lpos,kl);
        if (e.first==1e18+7) {
            auto o=check_prefix_(f[x].son[1],mid+1,r,lpos,kl-e.second);
            if (o.first==1e18+7) return make_pair(1e18+7,e.second+o.second);
            return o;
        }
        return e;
    }
    int check_sum_(int x,long long l,long long r,long long lpos,long long rpos) {
        if (!x) return 0;
        if (f[x].cnt==r-l+1) {
            lpos=max(lpos,l), rpos=min(rpos,r);
            return (lpos+rpos)%mod*((rpos-lpos+1)%mod)%mod*inv%mod;
        }
        if (lpos<=l&&r<=rpos) return f[x].sum;
        int ans=0;
        long long mid=(l+r)>>1;
        if (lpos<=mid) ans=(ans+check_sum_(f[x].son[0],l,mid,lpos,rpos))%mod;
        if (mid<rpos) ans=(ans+check_sum_(f[x].son[1],mid+1,r,lpos,rpos))%mod;
        return ans;
    }
    int check_ver_() { return op.size();}
    void rollback_(int ver) {
        while ((int)op.size()>ver) {
            operation e=op[(int)op.size()-1]; op.pop_back();
            if (e.opt==1) f[e.x].sum=e.vl;
            if (e.opt==2) f[e.x].cnt=e.vl;
            if (e.opt==3) erase_(e.x);
        }
    }
} sst;
struct First_Segment_Tree {
    struct node { vector<pair<long long,int> > op;} f[400010];
    void insert_(int k,int l,int r,int lpos,int rpos,pair<long long,int> key) {
        if (key.second==0) return;
        if (lpos<=l&&r<=rpos) { f[k].op.push_back(key); return;}
        int mid=(l+r)>>1;
        if (lpos<=mid) insert_(k<<1,l,mid,lpos,rpos,key);
        if (mid<rpos) insert_(k<<1|1,mid+1,r,lpos,rpos,key);
    }
    void solve_(int k,int l,int r) {
        int ver=sst.check_ver_();
        for (auto o : f[k].op) {
            long long lr=sst.check_prefix_(ro,1,inf,o.first,o.second).first;
            ro=sst.cover_(ro,1,inf,o.first,lr);
        }
        if (l==r) { ans[l]=sst.check_sum_(ro,1,inf,1,inf), sst.rollback_(ver); return;}
        int mid=(l+r)>>1;
        solve_(k<<1,l,mid), solve_(k<<1|1,mid+1,r);
        sst.rollback_(ver);
    }
} fst;
int main() {
//    freopen("in.in","r",stdin);
//    freopen("out.out","w",stdout);

    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld %d\n",&op[i].first,&op[i].second);

    for (int i=1;i<=n;i++) {
        if (mp.count(op[i].first)) fst.insert_(1,1,n,mp[op[i].first].first,i-1,pair<long long,int> (op[i].first,mp[op[i].first].second));
        mp[op[i].first]=pair<int,int> (i,op[i].second);
    }
    for (int i=1;i<=n;i++) if (mp.count(op[i].first)) fst.insert_(1,1,n,mp[op[i].first].first,n,pair<long long,int> (op[i].first,mp[op[i].first].second)), mp.erase(op[i].first);

    fst.solve_(1,1,n);

    for (int i=1;i<=n;i++) printf("%d\n",ans[i]);

    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 15340kb

input:

3
4 3
1 5
1 2

output:

15
36
21

result:

wrong answer 3rd numbers differ - expected: '18', found: '21'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 16060kb

input:

9
1 89
30 7
101 26
1 24
5 1
60 4
5 10
101 0
1 200

output:

4005
4656
10731
27504
60809
1485981
1587021
1191463
4815109

result:

wrong answer 3rd numbers differ - expected: '7607', found: '10731'

Test #3:

score: 0
Wrong Answer
time: 85ms
memory: 36792kb

input:

5000
1 255364995
414918035 212844
1 112266691
321122438 191414
1 277615842
848755093 61676
1 432591689
892259443 53755
1 263753018
173404455 173565
1 178341924
878941367 221276
1 65332960
439468128 240741
1 812238377
191076090 108732
1 180383041
927440330 112995
1 595696140
579818784 85614
1 5057816...

output:

235118030
699918971
797282574
902064730
545133458
280939836
340604482
333839266
9720010
543842184
918835528
399009519
163077436
584353639
32894659
897542719
651796867
593713660
237334343
864415848
858668186
555580288
467947892
334356890
148782995
780231816
504222094
702491808
29875558
639342623
7560...

result:

wrong answer 3rd numbers differ - expected: '430865692', found: '797282574'

Test #4:

score: 0
Memory Limit Exceeded

input:

100000
1 500000000
1000000001 500000000
2000000001 500000000
3000000001 500000000
4000000001 500000000
5000000001 500000000
6000000001 500000000
7000000001 500000000
8000000001 500000000
9000000001 500000000
10000000001 500000000
11000000001 500000000
12000000001 500000000
13000000001 500000000
1400...

output:


result:


Test #5:

score: 0
Wrong Answer
time: 2855ms
memory: 420832kb

input:

100000
49998999950002 500000000
49997999950003 500000000
49996999950004 500000000
49995999950005 500000000
49994999950006 500000000
49993999950007 500000000
49992999950008 500000000
49991999950009 500000000
49990999950010 500000000
49989999950011 500000000
49988999950012 500000000
49987999950013 500...

output:

376399979
752799930
259866744
636266639
553419310
955426208
542231930
745568363
572294863
416129117
300715132
755630975
730371263
2236198
939110298
215902353
208920353
752329693
280880719
502529311
469305233
540162306
436452929
903886246
937402235
160288776
758659701
48343048
535206467
291269236
531...

result:

wrong answer 3rd numbers differ - expected: '129199846', found: '259866744'

Test #6:

score: 0
Wrong Answer
time: 2142ms
memory: 395108kb

input:

100000
92303348842417 121458
92270522994821 852054850
93765096269940 752161890
97779083359973 984327853
90030769679569 439157849
99462493683485 45660
95578441605501 614317411
92236129196525 474149928
96065411631989 429943696
90394247621798 382840249
89263934750729 791122796
93577089467158 99679481
9...

output:

601385635
274004134
601850367
341926487
525622685
105816858
98270591
649703194
370392468
705149600
786695578
34755535
193963469
619358637
743478589
916995296
887419699
718273715
470995442
531934769
635618491
441251273
418808083
833992242
33665364
489309068
812518308
127890999
801876689
921863715
954...

result:

wrong answer 6th numbers differ - expected: '365740738', found: '105816858'

Test #7:

score: 0
Wrong Answer
time: 2127ms
memory: 384960kb

input:

100000
98001410246890 641673458
94816407430628 495030536
95979591652947 43208
95979591652947 183686
97163521776290 904784415
91640049592559 875129980
95914835187460 844802426
94846379383324 974270031
99639652388956 311664277
99298294827771 913614463
99476866913169 221766107
97248342663994 669489020
...

output:

805408268
531436018
27866346
628799395
526589961
842320033
947374779
840544081
578197250
176433577
251899446
704144124
43445401
416743355
194492651
393569861
450106291
695932127
282262002
71245081
657861752
753427144
472682353
431446771
898909012
760097336
22929489
305086904
745978553
402350668
8925...

result:

wrong answer 3rd numbers differ - expected: '575810846', found: '27866346'

Test #8:

score: 0
Wrong Answer
time: 2216ms
memory: 382444kb

input:

100000
97338601145206 191999210
97657969728741 875988993
92559675348135 8552565
99354409480201 960853995
93648768326445 343671323
97400841247229 104463842
98844341051398 508718383
96144328794112 187050711
98030257583732 365513
92378049740181 852725611
98301676983212 360931360
99458914124366 80234576...

output:

201835835
176681780
438095378
20098382
164708249
330646604
554380658
948878124
502403442
324527197
570703898
376033492
928212223
235466900
432105182
674622761
471404262
118897938
935122222
324245057
707815830
300971504
981823432
427248251
128275316
710365674
106620523
937909758
754818331
343637929
1...

result:

wrong answer 3rd numbers differ - expected: '819965610', found: '438095378'

Test #9:

score: 0
Wrong Answer
time: 2086ms
memory: 376416kb

input:

100000
96119987448606 658315028
98644701118435 280992389
98180676447908 56168
99822794299596 237183170
94655838918825 563695131
95744558879343 686204820
93739311062176 263266841
97630990881452 96901680
98683433984282 380708175
98141920320037 147598812
98095513966598 814629225
97882900659205 55097258...

output:

284288958
357751095
461366660
88799158
762093221
590247457
94454182
178875265
57888705
829186946
801487777
65122010
672288592
156666978
557353731
648386361
136318791
456758992
860464819
209394785
946728816
851394278
737232334
100628749
917773936
686712117
509176653
764336125
862018547
167909633
7640...

result:

wrong answer 3rd numbers differ - expected: '58956281', found: '461366660'

Test #10:

score: 0
Wrong Answer
time: 2114ms
memory: 376364kb

input:

100000
98169641631056 170946511
99452522210742 393032132
98797460964704 393706377
98747209012224 529219651
99152468691953 362194103
99410753036475 215295
97096873124809 1315725
96106202009957 124516158
95176405230280 853965254
99359463136784 622839995
96635771520630 550456203
96368792029394 93630831...

output:

692991104
373664255
846604839
394426111
851697704
456801584
582680219
687727357
819191446
260038216
844409456
243689313
748704439
850541794
595621419
152106562
653696590
961130674
824172930
386672291
760873389
661499404
564640640
961043408
812759050
476686347
686320784
798870136
199957839
454785766
...

result:

wrong answer 3rd numbers differ - expected: '485258530', found: '846604839'

Test #11:

score: 0
Wrong Answer
time: 1816ms
memory: 354756kb

input:

100000
97499080763005 475255826
97499083333242 9347
97499080763005 395470349
97499924236501 4654
97499080763005 148122052
97499213182916 2365
97499080763005 544025506
97499777050346 9912
97499080763005 41736833
97499401163067 12607
97499080763005 127843558
97499125181305 7144
97499080763005 13152858...

output:

655956691
428350171
159167788
718598219
697782676
60290222
765234432
657425973
898379955
507684503
348071114
145700257
521717103
72005509
948410215
537589376
714354605
827485360
975617113
268204252
706420543
622193221
505852834
539746758
690465404
985456282
745131482
687185541
644399345
393545009
27...

result:

wrong answer 3rd numbers differ - expected: '548564542', found: '159167788'

Test #12:

score: 0
Wrong Answer
time: 1914ms
memory: 353112kb

input:

100000
98999026537234 929244389
98999182418499 5182
98999026537234 774643967
98999646433835 17857
98999026537234 760743518
98999980664456 7597
98999026537234 573421161
98999090975969 6621
98999026537234 95191521
98999947586610 17798
98999026537234 953104244
98999116462517 15643
98999026537234 100617...

output:

526240962
808910950
484071840
8981473
817026076
210981320
113521579
308494502
781707132
804817601
123570495
222840685
445758439
871797808
894853599
191010567
967894416
2616394
374788440
183641375
597752620
966535525
633308293
195047663
440222754
884382615
580479201
891182096
758897401
115273049
5244...

result:

wrong answer 3rd numbers differ - expected: '692662359', found: '484071840'

Test #13:

score: 0
Wrong Answer
time: 1722ms
memory: 355008kb

input:

100000
99499024212061 630391525
99499061152079 3864
99499024212061 16505706
99499878275777 4812
99499024212061 776185964
99499757280269 12059
99499024212061 356565635
99499399237611 8902
99499024212061 972528120
99499256994518 9171
99499024212061 419476867
99499909552451 17146
99499024212061 6767939...

output:

358833000
63285979
36439376
508625679
327759427
818027427
219457158
810202616
896331877
382564032
473921144
371494567
17613206
176627720
867222913
365948476
455768696
90616414
624354962
570993467
936745215
375188684
52989947
618496718
762528670
777116196
783453744
821321644
755151257
404879216
28560...

result:

wrong answer 3rd numbers differ - expected: '813032842', found: '36439376'

Test #14:

score: 0
Wrong Answer
time: 2160ms
memory: 214508kb

input:

99999
10490328589436 1000000000
13762508396295 1000000000
40632115714511 1000000000
32834989282081 1000000000
29091918306598 1000000000
24352818172350 1000000000
23447797352860 1000000000
38073075086135 1000000000
14288530509239 1000000000
36463049009868 1000000000
10562334120356 1000000000
34490016...

output:

700388007
142288329
334277755
410912131
137460226
411447094
72765590
279964696
222368623
890983317
250548181
402114844
415089730
858947688
522024178
316519062
847522490
40392229
942260653
18297758
528074508
595025553
517324334
218245395
762520503
900138162
528624348
779162474
27422081
1602062
752121...

result:

wrong answer 5th numbers differ - expected: '984191481', found: '137460226'

Test #15:

score: 0
Wrong Answer
time: 2362ms
memory: 370860kb

input:

99999
61585049539216 1000000000
58981995705940 1000000000
44247484521936 1000000000
70916218483207 1000000000
47696673638497 1000000000
60781033156530 1000000000
55859922511212 1000000000
59143999312357 1000000000
57175954090596 1000000000
71328224891428 1000000000
46047599292678 1000000000
47510666...

output:

656243188
689191754
943169527
417261997
171887800
942770394
487929071
540825920
189160873
266750944
983404384
360385067
283101006
109650889
640733677
287448091
620766509
782336883
375792613
606491752
337503123
827396224
298942960
229294638
564733535
633756719
762206705
377714702
706713375
885055315
...

result:

wrong answer 3rd numbers differ - expected: '299706354', found: '943169527'

Test #16:

score: 0
Wrong Answer
time: 2232ms
memory: 223324kb

input:

99999
21219982576425 1000000000
42260400232639 1000000000
26412110792985 1000000000
11035481121988 1000000000
13219690258669 1000000000
19550933913223 1000000000
32679237390903 1000000000
15679803374289 1000000000
23896051833122 1000000000
20099950455987 1000000000
14778766729432 1000000000
21547991...

output:

123004833
323447149
549190477
181877325
102074593
684313368
487743819
426819671
65158749
306798875
973561287
33871166
212335882
447109903
319012380
889669158
963876353
496776372
363918835
241658155
462078167
859686412
929133640
369515080
711263558
149241112
172067501
56817314
411347021
205502198
677...

result:

wrong answer 5th numbers differ - expected: '350714436', found: '102074593'

Test #17:

score: 0
Wrong Answer
time: 2007ms
memory: 220428kb

input:

99999
28503598869279 1000000000
32397709666940 1000000000
25833502058723 1000000000
38020841213328 1000000000
54560138759501 1000000000
42230929758874 1000000000
28972613620824 1000000000
28498598787317 1000000000
54070131397843 1000000000
22084267818956 1000000000
37776835952805 1000000000
44465973...

output:

809311757
843230693
816940310
930310064
576914663
202937503
649004278
440287696
523152260
775851192
926032651
199093802
890061746
128914494
786259944
571978094
8544195
544032252
963947819
230934227
203630938
559839140
812622938
576473144
517822501
628817641
279065674
115218077
489559983
214009331
21...

result:

wrong answer 3rd numbers differ - expected: '330085498', found: '816940310'

Test #18:

score: 0
Wrong Answer
time: 2326ms
memory: 202128kb

input:

99999
18175781548542 1000000000
40883228277118 1000000000
33828113807745 1000000000
17817771477758 1000000000
22749897023579 1000000000
18015777423352 1000000000
28920025506062 1000000000
18799798298070 1000000000
27979006765970 1000000000
17103749421004 1000000000
24329932307643 1000000000
29798042...

output:

530050851
934114334
549124503
149653293
662653821
426576547
249451221
19812996
973822212
483604376
774679909
481877742
256424997
497248231
368156530
909359214
154282868
116727722
923056623
112502812
946532984
102752336
538391130
36466617
183517377
276794373
819039064
486866287
677649533
876378151
82...

result:

wrong answer 3rd numbers differ - expected: '139117719', found: '549124503'

Test #19:

score: 0
Wrong Answer
time: 2278ms
memory: 199408kb

input:

99999
13631696063382 1000000000
19095823575649 1000000000
18048800926387 1000000000
17060779354093 1000000000
15768748767399 1000000000
30886037572930 1000000000
26814970558482 1000000000
8165534157289 1000000000
27914989206121 1000000000
34170089895536 1000000000
27764986366439 1000000000
145187181...

output:

128224308
364130490
152929909
479550802
586285899
324788831
9199284
244116022
321041038
770371667
259990937
469741656
954528533
837855124
121709092
130114356
166490073
378283633
963080197
233134184
311265812
300703745
354988888
666412988
723713086
403206389
691696759
924763823
378102561
570462243
85...

result:

wrong answer 3rd numbers differ - expected: '758530203', found: '152929909'

Test #20:

score: 0
Wrong Answer
time: 2627ms
memory: 372516kb

input:

99999
71091006018203 1000000000
42267334298998 1000000000
53421686894439 1000000000
52992676205010 1000000000
49055576058012 1000000000
70721000416119 1000000000
43151374327143 1000000000
70716000332404 1000000000
51528640431406 1000000000
65945925001029 1000000000
39524135856472 1000000000
66414932...

output:

961356073
623334212
817690831
86852425
876836101
877388625
87058493
967071236
487128846
15353018
239000979
714101409
70166384
904225143
320506176
530484870
452070556
573710862
51539607
791278044
120476984
786764004
587762186
968746090
79533773
125391526
718492497
960896258
637952125
43647825
6565935...

result:

wrong answer 5th numbers differ - expected: '56850092', found: '876836101'

Test #21:

score: 0
Wrong Answer
time: 2131ms
memory: 197844kb

input:

99999
43981987091230 1000000000
41793950053258 1000000000
23385527966154 1000000000
32049759202175 1000000000
48927065970165 1000000000
26694629471843 1000000000
27661655640242 1000000000
37241867113918 1000000000
49110069037684 1000000000
20323405372655 1000000000
43304975621086 1000000000
48021052...

output:

92516536
444191664
406632471
93787710
625033966
763549761
999171028
521049642
40192272
530354145
529452044
887950651
520726526
627713891
581673626
525365115
241014908
546491920
511959282
892449391
23451207
719580212
115746037
558061089
901581263
963867029
428602691
855300388
705835452
143008432
7570...

result:

wrong answer 3rd numbers differ - expected: '749574507', found: '406632471'

Test #22:

score: 0
Wrong Answer
time: 2243ms
memory: 213432kb

input:

99999
31159466866911 1000000000
28413414847308 1000000000
25948364344910 1000000000
31236468095715 1000000000
22036273821032 1000000000
24056321657736 1000000000
36031551606814 1000000000
37935581367999 1000000000
40624624246259 1000000000
18857191994835 1000000000
22179277697755 1000000000
29154428...

output:

733458470
830919600
830094985
554955593
456990021
206564655
96657166
141149331
773416157
221739552
991491917
85361375
11954739
908103928
979400064
703487467
811953569
675798994
65650723
411931685
289478631
113688856
278551660
918207399
724995053
876685202
496293308
621442374
859612377
736045879
3645...

result:

wrong answer 3rd numbers differ - expected: '281776724', found: '830094985'