QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55112#1751. Automatic AccountantBeevo#AC ✓62ms5876kbC++232.3kb2022-10-12 11:43:012022-10-12 11:43:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-12 11:43:02]
  • 评测
  • 测评结果:AC
  • 用时:62ms
  • 内存:5876kb
  • [2022-10-12 11:43:01]
  • 提交

answer

#include <bits/stdc++.h>

#define el '\n'
#define ll long long
#define ld long double

#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e5 + 5, INF = 1e9;

struct Node {
    int mn;
};

struct segTree {
    Node tree[N * 4];
    Node neutral = {INF};

    Node merge(Node u, Node v) {
        return {min(u.mn, v.mn)};
    }

    Node single(int x) {
        return {x};
    }

    void build(int x, int l, int r) {
        if (l == r) {
            tree[x] = single(INF);

            return;
        }

        int m = (l + r) >> 1;

        build(x * 2, l, m);
        build(x * 2 + 1, m + 1, r);

        tree[x] = merge(tree[x * 2], tree[x * 2 + 1]);
    }

    void set(int x, int l, int r, int i, int v) {
        if (l == r) {
            tree[x] = single(min(v, tree[x].mn));

            return;
        }

        int m = (l + r) >> 1;

        if (i <= m)
            set(x * 2, l, m, i, v);
        else
            set(x * 2 + 1, m + 1, r, i, v);

        tree[x] = merge(tree[x * 2], tree[x * 2 + 1]);
    }

    Node query(int x, int lX, int rX, int l, int r) {
        if (lX > r || rX < l)
            return neutral;

        if (lX >= l && rX <= r)
            return tree[x];

        int m = (lX + rX) >> 1;

        Node u = query(x * 2, lX, m, l, r);
        Node v = query(x * 2 + 1, m + 1, rX, l, r);

        return merge(u, v);
    }
} st;

void testCase() {
    st.build(1, 0, N - 1);

    int s;
    cin >> s;

    int a, b;
    vector<pair<pair<int, int>, int>> v(s);
    for (int i = 0; i < s; i++) {
        cin >> a >> b;

        v[i] = {{a, b}, i + 1};
    }

    sort(v.rbegin(), v.rend());

    int c;
    cin >> c;
    vector<pair<int, int>> p(c);
    for (int i = 0; i < c; i++) {
        cin >> a >> b;

        p[i] = {a, b};
    }

    sort(p.rbegin(), p.rend());

    int l = 0;
    ll sol = 0;
    for (auto i: p) {
        while (l < s && v[l].first.first >= i.first)
            st.set(1, 0, N - 1, v[l].first.second, v[l].second), l++;

        sol += st.query(1, 0, N - 1, 0, i.second).mn;
    }

    cout << sol;
}

signed main() {
    Beevo

    int T = 1;
//    cin >> T;

    while (T--)
        testCase();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 4572kb

input:

1000
536 243
561 59
685 484
59 909
90 456
205 685
313 978
614 29
484 610
394 893
998 877
731 595
266 588
153 356
169 602
604 324
971 194
965 378
737 456
910 649
226 559
472 713
24 884
467 110
199 915
129 792
103 775
266 740
499 689
605 322
778 534
320 458
607 625
351 896
543 924
658 412
393 642
89 5...

output:

34010

result:

ok single line: '34010'

Test #2:

score: 0
Accepted
time: 30ms
memory: 5252kb

input:

50000
425 40
487 864
387 101
298 69
613 779
697 748
259 619
490 799
544 967
559 280
968 243
408 210
963 195
764 720
621 469
362 572
253 653
547 326
832 233
600 111
284 287
135 925
398 919
730 156
620 327
156 887
390 406
488 267
159 126
788 476
886 896
344 386
324 30
76 207
674 505
248 924
324 995
17...

output:

2225901

result:

ok single line: '2225901'

Test #3:

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

input:

100000
344 70883
664 5149
547 56373
734 77762
942 85742
576 16116
697 36821
483 86461
842 33224
171 80225
261 66481
150 98557
96 74605
871 7563
688 62312
276 14306
327 28166
879 41516
342 91811
795 47532
21 54376
557 34066
609 42833
385 58831
166 76728
775 62803
431 97310
181 87000
335 34912
999 841...

output:

4952460509

result:

ok single line: '4952460509'

Test #4:

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

input:

4
1 4
2 3
3 2
4 1
14
1 5
1 6
1 7
2 3
2 4
2 5
2 6
3 2
3 7
3 8
4 1
4 1
4 2
4 3

output:

36

result:

ok single line: '36'

Test #5:

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

input:

2
1 4
2 3
4
1 5
1 7
2 3
2 4

output:

6

result:

ok single line: '6'

Test #6:

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

input:

100000
536 91360
5472 58687
8634 89490
1666 68803
4255 61365
2262 66273
8981 87835
7352 88496
9052 67449
7417 53369
5914 66943
5053 96545
9605 89976
7322 98136
6964 97358
599 89520
7952 52036
4892 94862
6072 76025
7251 96224
8342 76484
8517 59186
7951 56909
5533 93128
8109 73319
3099 66680
9056 9605...

output:

192624333

result:

ok single line: '192624333'

Test #7:

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

input:

100000
3467 92538
7393 64628
5167 72427
4106 69623
7434 75928
1550 75422
1469 97990
3492 99809
1184 61840
1044 65584
1059 50915
3915 72112
794 59258
6535 76820
1847 96721
9079 55439
2289 75367
8447 73711
9064 67388
6988 87567
6263 94868
1304 86832
5638 70478
1414 84713
1014 52115
2658 51724
1680 752...

output:

86833243

result:

ok single line: '86833243'

Test #8:

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

input:

100000
1336 76287
4914 98927
3270 77118
5951 77018
9389 92898
5157 68291
3492 64168
8483 92504
2096 80229
8258 62694
8790 95061
5308 75071
9114 55452
9688 52639
1085 77688
60 61289
7783 99181
6792 81115
1102 95384
6531 99956
5249 72275
626 94209
6251 53549
7642 99174
9095 75483
2381 67589
7606 53232...

output:

211174161

result:

ok single line: '211174161'

Test #9:

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

input:

100000
9762 71056
4278 53813
8475 66814
9820 54215
6470 54488
2730 74216
5082 83964
4917 85856
2466 79249
6150 93207
1005 55098
9100 59112
2815 75931
8722 93838
9730 74634
7217 55679
5425 88884
925 77467
31 86579
8149 67264
7076 71927
1522 79536
263 72559
6433 90306
2960 51900
9144 56202
6751 91804
...

output:

682450186

result:

ok single line: '682450186'

Test #10:

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

input:

381
34063 44843
78955 93933
77299 63003
31323 85914
77715 93792
4489 81250
41638 2326
15804 99346
94871 91834
22977 4487
62591 56945
25778 27219
20808 70860
69444 92877
13005 89183
60671 81831
71338 10716
90617 18593
617 55938
5532 60698
12263 64615
37487 28803
35709 87335
44571 46819
45665 64948
96...

output:

1687312

result:

ok single line: '1687312'

Test #11:

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

input:

93847
27245 71216
9031 2413
50950 69512
76486 42656
86089 21036
3411 22944
97321 50594
61436 22436
86321 26088
27119 50232
39669 51897
66405 96933
74 64426
26918 56341
46469 13351
26148 60849
71881 62932
36336 67806
44508 46561
84999 34320
5494 92864
34638 70017
56374 27492
13975 74767
26710 32731
4...

output:

3642627

result:

ok single line: '3642627'

Test #12:

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

input:

7145
284 40737
54851 62340
56917 37726
20461 90958
95803 33759
54303 4625
40125 84580
2027 3762
6483 69360
53577 16974
14161 38052
46414 67980
51604 80470
33149 30626
33183 5943
35280 32027
34312 53289
75942 36963
88454 9761
24396 61087
1613 8255
10750 47291
47674 80309
52294 64459
48979 13762
24652...

output:

2649138

result:

ok single line: '2649138'

Test #13:

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

input:

61728
63028 16552
17238 23888
80325 21399
69224 41656
87329 24075
595 35018
60469 88655
16440 93563
27611 92576
1471 46543
44098 62010
33911 4882
39155 66396
67082 29923
96859 74886
37352 26564
1902 46854
45243 93700
88387 44411
22475 42234
5642 40753
70343 95121
54797 70598
99188 37521
19104 66035
...

output:

6759886

result:

ok single line: '6759886'

Test #14:

score: 0
Accepted
time: 15ms
memory: 4764kb

input:

32488
31971 83330
75982 47093
14723 68829
68023 2761
69744 79022
66950 76672
84410 61389
94737 95221
33222 69145
29790 98516
84909 77818
99584 25511
79710 32078
85547 23648
83684 47151
12706 16887
29784 81972
70192 40106
15695 70512
21345 96460
2070 43613
2540 99520
63826 32212
58442 97645
66767 454...

output:

565367

result:

ok single line: '565367'

Test #15:

score: 0
Accepted
time: 49ms
memory: 5876kb

input:

86116
72519 71498
20185 22717
81981 44779
81331 94303
53849 82698
2917 3473
21174 74906
18697 16350
29878 62357
71486 6131
36488 30645
64729 69913
25247 67692
69856 55760
77096 45465
6567 85845
36867 97646
51303 68660
23241 8797
16066 51135
48107 85556
31760 81298
6900 41747
85421 88289
66474 8563
9...

output:

3567813

result:

ok single line: '3567813'

Test #16:

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

input:

15819
76386 48192
17598 22982
83458 38023
57035 51014
7829 49234
44996 58908
47381 3322
6581 11216
95244 72381
14945 4612
29674 54484
85079 46095
45205 30736
12949 14609
13724 94741
69480 38685
40171 98537
48497 3978
44270 85234
6714 76758
1346 86997
26502 31115
85708 64239
43491 88023
99296 93201
7...

output:

3546178

result:

ok single line: '3546178'

Test #17:

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

input:

2224
18563 41189
80156 29622
50122 39962
781 95805
62029 11506
89006 79825
90444 166
79780 65800
70310 44124
56900 39963
74470 26514
94771 45239
19583 35313
48136 17189
22523 45609
60627 31467
54825 57270
98243 10634
67431 86383
58059 85017
51063 57547
66900 32143
91688 66730
80871 68749
20444 72304...

output:

200667

result:

ok single line: '200667'

Test #18:

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

input:

62500
88648 83247
78097 33402
93420 26443
51039 89097
45953 19324
10351 49457
74257 81833
40647 82351
74350 82260
4897 10070
98670 60695
57688 45967
57348 32933
29913 75229
8939 22254
61761 56175
32897 13409
79853 8981
47487 15643
60326 66341
7322 56495
22168 24726
57510 10582
29666 74996
26897 1225...

output:

7744886

result:

ok single line: '7744886'

Test #19:

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

input:

86915
8788 98538
94722 38241
94361 23730
72317 22381
46267 61806
20321 79560
60061 94962
74782 41475
33365 52624
39483 83332
45023 86357
96826 31313
98293 8360
13767 67396
27384 46460
8138 34976
82885 25437
26367 71766
71 77363
28077 55153
8840 53154
73994 1461
53648 49629
82446 90966
43576 5202
762...

output:

5693739

result:

ok single line: '5693739'

Test #20:

score: 0
Accepted
time: 51ms
memory: 5816kb

input:

65183
52277 11243
81595 27224
91599 17627
75648 90392
41851 61597
64845 30322
33931 43057
12435 13940
16926 92623
65492 37452
350 26126
13325 99980
51338 73636
59268 69419
3827 96832
22988 38022
61384 22806
17122 21809
92966 26751
6258 50989
40055 70005
43528 71701
5797 91980
32025 76753
38964 96727...

output:

7379530

result:

ok single line: '7379530'

Test #21:

score: 0
Accepted
time: 27ms
memory: 5236kb

input:

74336
98174 19008
58732 38070
65450 95581
20353 68174
35913 76299
11956 47458
79948 98266
51065 37752
61904 74200
81539 8114
21251 45499
46500 48053
34736 20322
1356 30379
2510 28725
28469 16037
20040 99453
19104 54819
67025 72580
71418 97327
5402 93516
67217 88365
36748 74460
86370 74212
49116 4339...

output:

492099

result:

ok single line: '492099'

Test #22:

score: 0
Accepted
time: 35ms
memory: 5568kb

input:

49672
35170 37693
56015 900
6795 79825
32912 30104
28465 25527
69585 70136
55161 74377
55012 96782
2226 20810
52698 49012
2873 59758
48318 8431
50309 58790
91877 59321
45806 1919
24287 84107
18326 7305
4396 2426
80228 41358
35584 23037
14124 31680
56104 73727
92606 66700
97951 84972
69971 70524
1138...

output:

4073658

result:

ok single line: '4073658'

Test #23:

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

input:

16642
82928 60743
76734 15217
46876 98348
7862 54426
82424 89039
13686 20762
7569 43296
9643 91109
20302 60653
61387 7850
22211 68697
45217 2336
910 51539
5474 97667
24871 64403
16946 50421
51463 47132
27516 92373
19343 86113
88722 99446
56726 49698
27580 70758
63051 68053
20444 42596
43284 11398
36...

output:

4267116

result:

ok single line: '4267116'

Test #24:

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

input:

64825
47009 71947
72985 8116
97471 91495
81149 59711
28908 92020
30372 71676
15653 57318
42681 75138
63395 3950
42209 58536
73352 57074
59421 52798
84417 75396
99443 89560
34471 64393
21936 37263
4172 12945
95325 17282
41685 10276
58144 87994
74045 91924
70738 44893
16926 22436
75608 97192
528 78976...

output:

2163257

result:

ok single line: '2163257'

Test #25:

score: 0
Accepted
time: 41ms
memory: 5560kb

input:

81151
14657 80636
55192 59831
81686 16642
44525 51023
66002 12853
29433 40145
8649 88679
14156 68206
14398 93693
7424 37154
85346 86877
72837 23166
39506 70323
12166 14240
31813 5874
40894 79983
29108 4737
17975 30698
80947 11993
80473 9630
63269 52986
49328 4682
48424 30405
41414 97076
95768 57094
...

output:

2300261

result:

ok single line: '2300261'

Test #26:

score: 0
Accepted
time: 46ms
memory: 5824kb

input:

81030
86621 70448
89695 31519
61270 72877
69211 48611
31911 51922
55085 68904
58037 69973
49564 68214
55449 51691
65637 92950
21830 13599
20849 49760
25777 43055
51736 84100
76580 73485
30001 63111
68285 55948
56970 82157
63334 32745
43664 83221
42256 80759
36570 40770
62505 2142
64216 55739
21899 1...

output:

5844374

result:

ok single line: '5844374'

Test #27:

score: 0
Accepted
time: 30ms
memory: 5820kb

input:

99838
99220 85275
43108 98944
91202 83710
49385 84869
63342 29296
30395 53568
29268 43303
40259 86156
89150 42909
89773 43799
22675 73201
29906 82397
38224 51687
94845 3214
83606 16091
53507 74361
5086 23684
473 42337
15276 73254
74333 19037
2007 30449
89176 86425
75385 30228
19521 68842
20718 69851...

output:

3411728

result:

ok single line: '3411728'

Test #28:

score: 0
Accepted
time: 16ms
memory: 4760kb

input:

35963
96016 46951
526 25672
54192 21595
61716 70793
16906 67345
74909 94643
98012 2264
57304 59279
41090 9394
65475 59134
50358 76498
32648 66959
48186 5153
70090 92065
42390 181
58622 65463
2620 7051
940 20956
58927 38435
48090 73876
33493 63081
79942 94264
78310 62683
81249 71204
51844 64687
22965...

output:

34752

result:

ok single line: '34752'

Test #29:

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

input:

44501
3976 21494
43962 4067
62185 33789
11684 34005
71553 8463
59329 73353
14857 84626
22080 93963
47564 40796
64698 83257
13983 5953
36796 87208
16434 24771
16839 47866
72337 94923
24846 87596
88569 68645
76906 56470
52576 33350
25414 98059
93901 2476
15855 35245
83747 68960
43193 10151
54381 69231...

output:

2799942

result:

ok single line: '2799942'

Test #30:

score: 0
Accepted
time: 21ms
memory: 4820kb

input:

43456
89824 58567
6490 90815
115 4204
72816 21027
81587 71958
18736 78284
81105 7770
26703 96977
69512 92307
44271 99562
78071 32047
58256 1613
5511 41557
55795 3239
98202 70168
75736 78314
70838 74639
57914 5877
14236 22121
5995 25519
98484 6284
34396 20689
96611 92572
9447 55269
5015 75569
81476 8...

output:

464727

result:

ok single line: '464727'