QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#84712#5657. Hungry CowMacesuted100 ✓5074ms484052kbC++144.6kb2023-03-06 17:37:102023-03-06 17:37:13

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 17:37:13]
  • 评测
  • 测评结果:100
  • 用时:5074ms
  • 内存:484052kb
  • [2023-03-06 17:37:10]
  • 提交

answer

/**
 * @file 5657.cpp
 * @author Macesuted ([email protected])
 * @date 2023-03-06
 *
 * @copyright Copyright (c) 2023
 *
 */

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

#ifndef LOCAL
#define endl '\n'
#endif

bool mem1;

#define maxn 100005
#define mod 1000000007
#define e9 1000000001

typedef pair<int, int> pii;
typedef pair<int64_t, int> pIi;

map<int64_t, vector<pii>> rec;

int Mod(int x) { return x >= mod ? x - mod : x; }

class SegmentTree1 {
   private:
    class SegmentTree2 {
       private:
        struct Node {
            int l, r, sum, ans, ver;
            bool laz;
            Node(void) = default;
            Node(int ver_, int64_t ql, int64_t qr) {
                l = r = 0, ver = ver_, sum = min((int64_t)e9, qr - ql + 1);
                ans = __int128_t(ql + qr) * (qr - ql + 1) / 2 % mod, laz = false;
            }
        };

        Node T[maxn * 160];
        vector<int> roots;
        stack<int> nodes;
        queue<int> emp;
        int64_t n;
        int ver;

        int newNode(Node x) {
            assert(!emp.empty());
            int p = emp.front();
            emp.pop(), nodes.push(p), T[p] = x;
            return p;
        }
        void chk(int& p, int64_t l, int64_t r) {
            if (!p) p = newNode(Node(ver, l, r));
            if (T[p].ver != ver) p = newNode(T[p]), T[p].ver = ver;
            return;
        }
        void upd(int p) { return T[p].sum = T[p].ans = 0, T[p].laz = true, void(); }
        void pushDown(int p, int64_t l, int64_t r) {
            int64_t mid = (l + r) >> 1;
            chk(T[p].l, l, mid), chk(T[p].r, mid + 1, r);
            if (T[p].laz) upd(T[p].l), upd(T[p].r), T[p].laz = false;
            return;
        }
        void pushUp(int p) {
            return T[p].sum = min(e9, T[T[p].l].sum + T[T[p].r].sum), T[p].ans = Mod(T[T[p].l].ans + T[T[p].r].ans), void();
        }
        int64_t update(int& p, int64_t l, int64_t r, int64_t qp, int& x) {
            chk(p, l, r);
            if (qp <= l && x >= T[p].sum) {
                int64_t ret = T[p].ans;
                return x -= T[p].sum, upd(p), ret;
            }
            pushDown(p, l, r);
            int64_t mid = (l + r) >> 1, ans = 0;
            if (qp <= mid) ans = Mod(ans + update(T[p].l, l, mid, qp, x));
            if (x) ans = Mod(ans + update(T[p].r, mid + 1, r, qp, x));
            return pushUp(p), ans;
        }

       public:
        SegmentTree2(void) {
            for (int i = 1; i < maxn * 160; i++) emp.push(i);
            roots.push_back(0), ver = 0, n = 2e14;
            return;
        }
        void copy(void) { return ver++, roots.push_back(roots.back()); }
        void destroy(void) {
            while (!nodes.empty() && T[nodes.top()].ver == ver) emp.push(nodes.top()), nodes.pop();
            return ver--, roots.pop_back();
        }
        int64_t update(int64_t p, int x) { return update(roots.back(), 1, n, p, x); }
    } ST;

    vector<pIi> T[maxn << 2];
    int n;

    void insert(int p, int l, int r, int ql, int qr, pIi v) {
        if (ql <= l && r <= qr) return T[p].push_back(v);
        int mid = (l + r) >> 1;
        if (ql <= mid) insert(p << 1, l, mid, ql, qr, v);
        if (qr > mid) insert(p << 1 | 1, mid + 1, r, ql, qr, v);
        return;
    }
    void solve(int p, int l, int r, int64_t tot = 0) {
        ST.copy();
        for (auto i : T[p]) tot = Mod(tot + ST.update(i.first, i.second));
        if (l == r)
            cout << tot << endl;
        else {
            int mid = (l + r) >> 1;
            solve(p << 1, l, mid, tot), solve(p << 1 | 1, mid + 1, r, tot);
        }
        ST.destroy();
        return;
    }

   public:
    void resize(int _n) { return n = _n, void(); }
    void insert(int l, int r, pIi v) { return insert(1, 1, n, l, r, v); }
    void solve(void) { return solve(1, 1, n); }
} ST;

void solve(void) {
    int n;
    cin >> n, ST.resize(n);
    for (int i = 1; i <= n; i++) {
        int64_t d, b;
        cin >> d >> b, rec[d].emplace_back(i, b);
    }
    for (auto& [x, y] : rec)
        for (int j = 0; j < (int)y.size(); j++)
            ST.insert(y[j].first, (j == (int)y.size() - 1 ? n : y[j + 1].first - 1), {x, y[j].second});
    rec.clear();
    ST.solve();
    return;
}

bool mem2;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
#ifdef LOCAL
    cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef LOCAL
    cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
#endif
    return 0;
}

詳細信息

Test #1:

score: 4.54545
Accepted
time: 60ms
memory: 79144kb

input:

3
4 3
1 5
1 2

output:

15
36
18

result:

ok 3 number(s): "15 36 18"

Test #2:

score: 4.54545
Accepted
time: 39ms
memory: 78840kb

input:

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

output:

4005
4656
7607
3482
3507
3753
4058
1107
24531

result:

ok 9 numbers

Test #3:

score: 4.54545
Accepted
time: 147ms
memory: 150884kb

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
430865692
80346613
848027326
568710394
340195238
190991083
826211664
180951671
569935857
679922008
650993948
624850177
428416731
646484944
727440627
230673871
429374754
412788182
52678570
76241310
668853821
636690710
209140532
869111458
915919167
837020724
313374684
328391122
903...

result:

ok 5000 numbers

Test #4:

score: 4.54545
Accepted
time: 3998ms
memory: 482392kb

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:

375000007
250000035
625000091
500000168
875000273
750000399
125000546
721
375000924
250001148
625001400
500001673
875001974
750002296
125002639
3010
375003409
250003829
625004277
500004746
875005243
750005761
125006300
6867
375007462
250008078
625008722
500009387
875010080
750010794
125011529
12292
...

result:

ok 100000 numbers

Test #5:

score: 4.54545
Accepted
time: 5074ms
memory: 483820kb

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
129199846
505599741
881999608
258399440
634799251
11199027
387598782
763998509
140398201
516797872
893197515
269597123
645996710
22396262
398795793
775195296
151594764
527994211
904393630
280793014
657192377
33591705
409991012
786390291
162789535
539188758
915587953
291987113
668...

result:

ok 100000 numbers

Test #6:

score: 4.54545
Accepted
time: 4438ms
memory: 481488kb

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
365740738
21596345
859480883
580170157
914927289
661716135
909776099
68984026
985299561
62059976
433237513
22193692
179214382
464433705
116140252
69331558
520739757
847567658
978624852
870869337
901728499
377623547
471976784
651283280
374283948
83055...

result:

ok 100000 numbers

Test #7:

score: 4.54545
Accepted
time: 4417ms
memory: 481592kb

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
575810846
354089953
881282091
197012156
542992808
330037707
67690876
366809043
605423814
304354015
643655299
699246853
588121501
342825464
777769194
872413897
6027603
922267250
117628699
92064221
939482410
178991612
254975956
70807789
333639949
4646949
912705360
569077475
5925366...

result:

ok 100000 numbers

Test #8:

score: 4.54545
Accepted
time: 4533ms
memory: 481612kb

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
819965610
401968614
20890476
624221975
244624530
639121996
822116848
14404016
994033112
460872597
65150286
328331667
840921149
115160143
363463649
332155031
785325903
716984735
408770118
205347955
98965262
622465068
710093452
22710273
62684742
300950961
746815491
377843574
921167...

result:

ok 100000 numbers

Test #9:

score: 4.54545
Accepted
time: 4395ms
memory: 480888kb

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
58956281
911721463
585015519
413169755
89222244
932165424
340803186
548439909
31415022
677081730
328873372
179565831
580252584
559784456
47716886
185178829
313960770
337437178
522873557
427539019
460970494
259155036
76300216
789547746
612012282
314138376
411820798
717711891
79388...

result:

ok 100000 numbers

Test #10:

score: 4.54545
Accepted
time: 4666ms
memory: 482068kb

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
485258530
240812376
150262690
495543044
930860978
914610240
46074322
963945774
548317007
947596871
579199746
42702946
224520750
410015800
535413307
842847391
705889647
660697667
310757164
211383179
211616198
608018966
63331840
943411679
25124419
748599649
149687352
404515279
1784...

result:

ok 100000 numbers

Test #11:

score: 4.54545
Accepted
time: 3659ms
memory: 478880kb

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
548564542
779715219
957292615
681253780
867332278
274556258
395033249
333056245
701438428
203273870
489695476
706378273
144580619
397623726
228895978
520643679
706764212
488871564
217475631
415165457
434314301
827566002
256029845
128298498
8136098
471027033
112802895
977816195
81...

result:

ok 100000 numbers

Test #12:

score: 4.54545
Accepted
time: 3447ms
memory: 478980kb

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
692662359
262454820
824971927
696977629
511671627
304096025
488742915
459595813
852048508
407821555
986580341
935810355
447338247
404215525
304626541
322321947
109610273
135672419
575250508
895903646
120155775
689920977
344461186
328119759
176168052
810451653
44880448
275429359
8...

result:

ok 100000 numbers

Test #13:

score: 4.54545
Accepted
time: 3454ms
memory: 478200kb

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
813032842
736093155
525127433
245134000
66495264
919121222
462185849
492634514
674820800
65951665
846808145
101614325
851611097
714978008
763173865
749817090
98969566
753942239
795699176
747343173
205025620
285496160
869383022
627352226
630521000
689283960
597006790
625528637
3140...

result:

ok 100000 numbers

Test #14:

score: 4.54545
Accepted
time: 3366ms
memory: 484052kb

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
984191481
258178342
677857295
154119955
441255450
99973089
761648184
646691916
83883467
838778257
902188794
274895250
996540178
97972629
746548049
437179563
944873128
373351594
86478829
745738023
758296750
198138061
826624254
77162373
383588308
924776713
31294...

result:

ok 99999 numbers

Test #15:

score: 4.54545
Accepted
time: 3535ms
memory: 483024kb

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
299706354
773798831
60666512
831549106
376707783
384419368
708586848
137841959
945049579
282524740
743882713
311828689
842911477
958543110
707388072
788173259
520781106
118191513
768417704
258310798
239964440
170316118
973093063
837827730
258264123
566018125
921479532
10650495
36...

result:

ok 99999 numbers

Test #16:

score: 4.54545
Accepted
time: 3467ms
memory: 483716kb

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
350714436
814279902
154144887
531293205
169632283
517425302
151043463
211353349
300585707
37295987
172488184
594505008
363056805
53085050
848434784
973071322
193491327
832548078
867271692
189854167
769886906
207484315
230310704
672685614
790862183
585017360
16...

result:

ok 99999 numbers

Test #17:

score: 4.54545
Accepted
time: 3541ms
memory: 483032kb

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
330085498
443455252
474812220
968569449
674643365
484528604
567393168
693742634
843924093
34120680
264443328
679557432
807567246
593285396
38090557
573578614
865484367
67374847
40071558
396279760
672779845
436630051
922477136
441997628
92245661
510321866
234415732
958865087
95651...

result:

ok 99999 numbers

Test #18:

score: 4.54545
Accepted
time: 3425ms
memory: 483200kb

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
139117719
739646516
461596234
20515568
843390249
256224973
210234182
965125271
440163961
147361794
921909056
951648485
822556784
173522019
389634215
352079069
954188705
647256232
481286397
915556038
523388437
669361047
614756087
263436426
323769185
444093816
222042331
122447902
7...

result:

ok 99999 numbers

Test #19:

score: 4.54545
Accepted
time: 3452ms
memory: 483188kb

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
758530203
303887555
63288457
801791396
9195978
270495096
347420112
719825725
816621165
790465702
301408035
302074086
68531898
76937162
96502351
339873068
454712180
72768600
44219985
119303763
740300677
658392029
723663040
169630548
458120918
551454608
724792283
752727170
98550141...

result:

ok 99999 numbers

Test #20:

score: 4.54545
Accepted
time: 3550ms
memory: 483800kb

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
56850092
57402616
439227063
440365347
959870440
488094612
539036019
14136442
370201424
86703456
502984496
3406527
819845957
241960918
297674702
744241678
73440618
406584128
446449664
827433568
979056809
489971921
83072885
941358982
121188376
450653101
757125941...

result:

ok 99999 numbers

Test #21:

score: 4.54545
Accepted
time: 3393ms
memory: 483140kb

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
749574507
436729746
977336049
572341210
984214968
916242421
435385051
598772342
771546713
406978768
973592236
582491879
363677243
678241075
516956308
822433320
805167001
893067100
24068916
922778589
318944414
630257643
973777817
269996876
734732545
161430235
778275261
602052056
56...

result:

ok 99999 numbers

Test #22:

score: 4.54545
Accepted
time: 3375ms
memory: 483200kb

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
281776724
6637332
90969914
840544555
981062432
913345310
545612129
202572312
259774840
258391315
911217939
564563428
539781959
288650831
397116933
260962358
455888226
805325749
682872695
888925253
521897811
161553543
64947370
166151994
785760107
848334640
927724641
70264903
97223...

result:

ok 99999 numbers