QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#547674#4373. Swap SpaceJooDdaeAC ✓195ms12712kbC++20695b2024-09-05 01:28:122024-09-05 01:28:12

Judging History

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

  • [2024-09-05 01:28:12]
  • 评测
  • 测评结果:AC
  • 用时:195ms
  • 内存:12712kb
  • [2024-09-05 01:28:12]
  • 提交

answer

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

int n;
vector<array<int, 2>> v[2];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++) {
        int a, b; cin >> a >> b;
        v[a <= b].push_back({a, b});
    }
    sort(v[1].begin(), v[1].end());

    ll ans = 0, cur = 0;
    for(auto [x, y] : v[1]) {
        if(cur < x) ans += x-cur, cur = x;
        cur += y-x;
    }

    sort(v[0].begin(), v[0].end(), [&](auto a, auto b){ return make_pair(b[1], a[0]) < make_pair(a[1], b[0]); });
    for(auto [x, y] : v[0]) {
        if(cur < x) ans += x-cur, cur = x;
        cur += y-x;
    }

    cout << ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
6 6
1 7
3 5
3 5

output:

1

result:

ok single line: '1'

Test #2:

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

input:

4
2 2
3 3
5 1
5 10

output:

5

result:

ok single line: '5'

Test #3:

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

input:

1
42 41

output:

42

result:

ok single line: '42'

Test #4:

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

input:

5
3000 500000
20 21
20 100
4000 4001
4000 4100

output:

2919

result:

ok single line: '2919'

Test #5:

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

input:

5
2000 1999
20 1
20 19
3500 1000
5000 4000

output:

5000

result:

ok single line: '5000'

Test #6:

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

input:

5
40 35
30 30
1000 1000
50 50
35 40

output:

995

result:

ok single line: '995'

Test #7:

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

input:

10
2 4
2 2
4 2
2 10
5 5
4 2
6 2
4 7
10 8
5 4

output:

2

result:

ok single line: '2'

Test #8:

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

input:

10
11 82
98 12
78 53
15 10
41 2
81 58
53 42
30 41
25 39
20 54

output:

61

result:

ok single line: '61'

Test #9:

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

input:

10
876 620
186 432
755 737
743 539
233 930
897 780
901 362
601 97
531 357
803 161

output:

1608

result:

ok single line: '1608'

Test #10:

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

input:

100
784 714
628 704
863 735
324 184
13 16
338 370
837 967
814 420
865 607
367 893
711 324
714 372
803 177
539 895
982 885
683 431
379 368
943 784
738 695
296 534
995 271
388 378
1000 334
545 429
351 748
993 4
579 529
975 113
110 985
748 258
893 50
549 770
952 246
845 534
900 564
907 834
975 632
304 ...

output:

12306

result:

ok single line: '12306'

Test #11:

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

input:

1000
889 85
684 844
919 123
527 182
990 401
288 725
211 914
217 800
649 704
462 866
782 24
357 499
233 966
535 788
883 327
15 176
41 702
358 85
699 990
9 890
5 326
744 995
551 426
475 47
362 798
459 475
770 509
258 775
291 336
536 798
153 979
59 635
968 281
338 798
692 815
102 238
622 70
581 345
660...

output:

1509

result:

ok single line: '1509'

Test #12:

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

input:

1000
4 9
9 8
6 5
6 4
5 6
7 5
5 10
5 4
4 2
1 3
8 10
9 7
7 5
3 7
3 2
1 4
9 6
7 9
8 3
8 4
8 2
10 2
5 1
2 9
8 8
1 1
3 2
3 1
4 5
6 3
10 4
4 4
5 1
6 10
9 2
8 7
8 5
4 1
3 4
1 7
2 3
10 7
3 1
9 1
2 4
6 8
6 8
10 9
10 4
1 3
7 2
1 1
9 9
8 8
3 8
9 2
7 10
1 9
10 5
2 8
6 6
1 9
3 4
10 5
8 10
8 3
10 7
9 5
8 5
10 4
9...

output:

74

result:

ok single line: '74'

Test #13:

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

input:

1009
24752 29284
10711 28166
25341 26786
14598 21733
4044 15830
5462 16034
8841 11651
15371 24736
6567 10740
3072 28882
15480 24751
26113 11619
32560 15744
10240 27697
30730 25341
16585 28655
5691 11080
13002 12287
35568 24268
25332 25832
34110 30696
15814 31829
18296 12225
25988 2913
7646 11350
284...

output:

38

result:

ok single line: '38'

Test #14:

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

input:

434
4148 9614
11024 12302
7647 2912
4695 2650
564 368
1738 4620
4859 5261
8956 8025
7520 3337
11522 11964
9305 12337
4775 9029
5310 7746
8739 8302
1497 9793
4139 8614
1546 6965
6088 11892
4912 12464
5779 9864
12078 4348
10084 10590
10736 6659
2314 7106
2209 3539
10350 4570
10108 11842
6004 11144
903...

output:

20

result:

ok single line: '20'

Test #15:

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

input:

213
11375 10927
815 15143
17007 21962
3043 24364
18732 14960
8643 29440
11089 4190
1444 21644
13952 11632
17242 7992
7059 23422
5226 1378
15012 27436
16842 10840
9962 24520
15712 28861
19344 26085
27918 12735
19708 6492
22167 2498
1881 23146
17505 27445
18425 12044
18343 8401
18322 21094
24073 3138
...

output:

596

result:

ok single line: '596'

Test #16:

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

input:

479
41422 69626
39666 39295
69555 32245
2440 81055
72277 43409
87492 1865
19622 4745
64929 41809
70335 39411
43627 65449
75013 38842
9496 10910
653 28647
67304 9222
58418 18522
55878 23377
33154 746
83012 80791
15207 28394
19333 54848
13866 63253
83921 25887
73228 2806
63480 23574
25646 40820
54139 ...

output:

60

result:

ok single line: '60'

Test #17:

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

input:

547
1951 2458
171 1536
2724 183
3238 1373
1328 1736
2667 1835
1386 298
3540 1851
433 3633
2510 319
805 3666
937 2568
2412 1421
1952 2065
932 1865
112 714
3667 3625
1531 2090
137 1601
1972 2675
159 20
1203 3341
2939 2715
1065 3586
2880 2864
583 1572
45 1066
3668 2505
3126 2519
31 1944
2837 3581
3047 ...

output:

1

result:

ok single line: '1'

Test #18:

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

input:

100
1451 1491
2366 2396
736 771
1149 1198
1491 1513
2032 2073
2733 2739
3389 3417
3373 3389
638 680
1863 1898
1898 1935
3087 3097
2624 2650
1334 1363
269 323
366 376
2862 2919
2463 2496
1081 1097
1689 1703
2518 2547
1138 1149
2411 2463
1408 1451
1977 1994
1097 1138
376 414
907 907
1561 1599
1658 168...

output:

186

result:

ok single line: '186'

Test #19:

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

input:

100
877 877
1081 1048
1323 1309
260 265
1175 1182
1493 1470
1654 1656
279 297
1237 1235
1542 1493
951 948
1462 1512
1229 1234
1234 1265
1073 1125
503 489
406 462
948 906
1364 1410
1182 1229
382 383
786 795
525 555
1027 1073
297 340
920 960
854 805
1010 1006
805 779
222 260
795 825
906 877
1309 1270
...

output:

190

result:

ok single line: '190'

Test #20:

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

input:

100
999997927 999997903
999998991 999998988
999997967 999997942
999997837 999997822
999997887 999997865
999997606 999997567
999998960 999998915
999999223 999999180
999997114 999997066
999998399 999998371
999997865 999997851
999998988 999998960
999997727 999997722
999997066 999997037
999997942 999997...

output:

999999638

result:

ok single line: '999999638'

Test #21:

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

input:

4
42 42
1000042 1000042
54321 54321
42 42

output:

1000042

result:

ok single line: '1000042'

Test #22:

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

input:

100
93393 999893231
152696 999836420
67384 999916692
44439 999942900
99973 999881531
119017 999870528
75798 999906493
68809 999913790
155896 999831474
254580 999744924
173154 999820555
93344 999897974
20162 999961351
47377 999942750
10883 999977579
63492 999917431
197392 999803306
139931 999851261
1...

output:

42

result:

ok single line: '42'

Test #23:

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

input:

100
999830352 156148
999939772 49803
999754808 252661
999901676 96675
999893848 103509
999962741 22746
999889612 106267
999920667 74332
999913819 85375
999986599 2562
999817339 175089
999950567 36802
999753328 254881
999759289 248639
999815372 180053
999960543 26759
999822180 171969
999917561 79633
...

output:

99972069589

result:

ok single line: '99972069589'

Test #24:

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

input:

100
5879 5879
394 417
4647 4696
4305 4332
2405 2419
5486 5545
1645 1687
2826 2879
199 201
2336 2393
1118 1159
2222 2249
765 770
5017 5051
3183 3209
2050 2061
5108 5133
4239 4270
4918 4940
1284 1309
2575 2625
503 558
1094 1102
2933 2972
2261 2308
1941 1992
3560 3590
4779 4811
259 301
5597 5627
1232 1...

output:

3257

result:

ok single line: '3257'

Test #25:

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

input:

100
999996209 999996161
999999359 999999342
999996103 999996066
999997179 999997174
999995655 999995651
999995308 999995298
999995135 999995086
999999318 999999298
999995496 999995477
999995431 999995424
999997654 999997618
999997716 999997689
999996276 999996238
999997842 999997842
999996431 999996...

output:

999999930

result:

ok single line: '999999930'

Test #26:

score: 0
Accepted
time: 189ms
memory: 12712kb

input:

1000000
17193536 17193575
11369756 11369797
18840002 18840059
19500726 19500729
11426864 11426907
924839 924844
1859847 1859874
5118441 5118479
24709985 24710018
2501817 2501836
13973892 13973918
10262507 10262518
15654470 15654524
13837184 13837227
14326891 14326947
17824444 17824495
5969608 596962...

output:

138

result:

ok single line: '138'

Test #27:

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

input:

2
999999950 999999800
999999950 999999999

output:

999999950

result:

ok single line: '999999950'

Test #28:

score: 0
Accepted
time: 105ms
memory: 12040kb

input:

1000000
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
100000...

output:

999999998999999

result:

ok single line: '999999998999999'

Test #29:

score: 0
Accepted
time: 195ms
memory: 11044kb

input:

1000000
683339867 45801853
241287142 602472005
27365007 436193629
432567302 202040851
720992109 740191251
145224567 661197883
399720904 516349020
188306726 681943302
224519143 639292672
300198611 227972747
177655346 659354544
166978836 101700738
315804105 264319709
391408283 970023124
634414210 3686...

output:

497623861777

result:

ok single line: '497623861777'