QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#622407#6311. 火车站propane100 ✓25ms5952kbC++201.5kb2024-10-08 21:28:052024-10-08 21:28:07

Judging History

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

  • [2024-10-08 21:28:07]
  • 评测
  • 测评结果:100
  • 用时:25ms
  • 内存:5952kb
  • [2024-10-08 21:28:05]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, m, x;
    cin >> n >> m >> x;
    vector<pair<int, int> > p(m);
    for(auto &[l, r] : p) cin >> l >> r;
    vector<int> ans;
    // 向左
    {
        vector<bool> ed(n + 1);
        vector<int> d(n + 1);
        for(auto [l, r] : p){
            r = min(r, x);
            if (l >= r) continue;
            ed[l] = true;
            d[l + 1] += 1;
            d[r + 1] -= 1;
        }
        for(int i = 1; i <= x; i++){
            d[i] += d[i - 1];
        }
        for(int i = x - 1; i >= 1; i--){
            if (d[i + 1] == 0) break;
            if (ed[i]) ans.push_back(i);
        }
    }
    // 向右
    {
        vector<bool> ed(n + 1);
        vector<int> d(n + 1);
        for(auto [l, r] : p){
            l = max(l, x);
            if (l >= r) continue;
            ed[r] = true;
            d[l] += 1;
            d[r] -= 1;
        }
        for(int i = x; i <= n; i++){
            d[i] += d[i - 1];
        }
        for(int i = x + 1; i <= n; i++){
            if (d[i - 1] == 0) break;
            if (ed[i]) ans.push_back(i);
        }
    }
    sort(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] << " \n"[i + 1 == ans.size()];
    }

}

详细


Pretests


Final Tests

Test #1:

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

input:

46 50 24
38 39
14 18
38 41
38 40
38 44
1 9
20 32
2 31
6 23
4 11
38 40
38 40
24 30
10 32
1 15
13 30
7 29
3 7
15 36
17 30
5 9
38 44
38 46
22 29
2 25
4 32
38 44
38 45
33 36
1 20
38 41
38 40
9 20
23 26
38 40
29 31
8 23
2 6
1 24
10 29
38 42
38 42
38 40
38 44
5 8
38 45
10 20
14 34
9 33
16 28

output:

1 2 3 4 5 6 7 8 9 10 13 14 15 16 17 20 22 23 25 26 28 29 30 31 32 33 34 36

result:

ok 28 numbers

Test #2:

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

input:

46 49 22
25 28
5 14
24 29
43 46
13 14
5 14
9 14
12 14
24 33
18 33
3 14
17 40
26 32
1 14
43 46
33 36
4 14
43 44
20 21
2 14
25 30
23 28
43 45
43 46
29 38
43 45
3 14
9 14
11 14
13 14
33 38
25 41
9 14
3 14
1 14
3 14
43 46
30 38
10 14
3 14
9 14
31 33
17 38
6 14
6 14
10 14
5 14
11 14
17 20

output:

17 18 20 28 29 30 32 33 36 38 40 41

result:

ok 12 numbers

Test #3:

score: 10
Accepted
time: 1ms
memory: 3924kb

input:

4901 4742 2784
1660 2698
1184 1582
3644 3650
860 1582
12 1582
4284 4750
693 1582
4284 4420
530 1582
4284 4778
213 1582
1346 1582
2456 3284
1951 2247
2526 3899
1748 3843
1840 4158
1847 3233
2710 4082
17 1582
1217 1582
2732 3868
2176 3652
1440 1582
3392 3778
115 1582
51 1582
4284 4410
343 1582
696 158...

output:

1584 1585 1586 1587 1588 1589 1593 1598 1599 1602 1603 1604 1606 1607 1610 1613 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1632 1634 1639 1643 1644 1645 1647 1648 1651 1652 1653 1654 1655 1657 1658 1659 1660 1661 1663 1664 1665 1667 1670 1672 1673 1674 1676 1680 1682 1683 ...

result:

ok 1446 numbers

Test #4:

score: 10
Accepted
time: 1ms
memory: 3700kb

input:

4752 4916 2637
631 1748
1958 2543
976 1748
4059 4176
1753 2555
1293 1748
400 1748
1531 1748
439 1748
814 1748
752 1748
4059 4745
1500 1748
410 1748
4059 4543
860 1748
3244 3846
1484 1748
2949 3200
365 1748
490 1748
533 1748
159 1748
2145 3211
938 1748
2104 2499
4059 4568
1321 1748
114 1748
257 1748
...

output:

1750 1752 1753 1755 1757 1760 1761 1762 1763 1764 1765 1768 1769 1771 1773 1774 1776 1779 1780 1781 1782 1784 1785 1787 1790 1792 1794 1795 1798 1799 1800 1803 1804 1806 1808 1809 1816 1817 1818 1819 1820 1822 1823 1824 1828 1829 1830 1831 1832 1833 1835 1836 1837 1838 1841 1843 1844 1848 1849 1851 ...

result:

ok 1183 numbers

Test #5:

score: 10
Accepted
time: 1ms
memory: 3936kb

input:

4638 4800 2174
763 2920
3689 3981
1696 1863
2225 3298
4041 4197
514 565
955 2677
982 1067
4041 4426
369 565
1280 1583
2033 2897
4041 4147
2216 3385
2470 3479
4041 4231
284 565
333 565
4041 4496
2471 3315
156 565
1449 2938
1754 3500
1634 3795
236 565
4041 4626
934 3865
2513 2835
239 565
1239 3066
136...

output:

567 569 570 571 574 575 576 579 581 582 584 585 586 587 588 589 590 593 594 595 596 597 598 599 602 603 604 605 606 610 611 612 614 617 618 619 622 623 624 625 626 627 628 629 630 631 632 633 634 636 637 638 639 640 641 642 643 645 646 648 649 650 651 653 654 655 659 660 661 662 663 664 665 667 668 ...

result:

ok 2365 numbers

Test #6:

score: 10
Accepted
time: 20ms
memory: 5532kb

input:

193872 190790 1
1 55918
61723 111652
61723 106905
61723 146471
8591 47114
3781 26833
61723 175724
61723 105145
12561 22256
61723 167628
61723 152637
61723 89452
61723 126604
61723 87227
61723 80698
61723 72291
61723 96877
61723 122100
61723 83795
10417 42641
61723 158895
61723 107569
61723 164698
61...

output:

781 920 964 1035 1110 1131 1395 1426 1485 1691 1731 1818 1888 1983 2056 2124 2215 2224 2269 2333 2347 2400 2419 2440 2442 2446 2469 2477 2482 2626 2681 2683 2818 2822 2848 2858 2887 2931 2992 3004 3012 3040 3091 3120 3124 3134 3138 3172 3182 3188 3195 3267 3293 3366 3398 3492 3497 3514 3553 3622 363...

result:

ok 15827 numbers

Test #7:

score: 10
Accepted
time: 19ms
memory: 5496kb

input:

183551 186029 1
1 18923
46775 110591
46775 147364
46775 151335
46775 154945
46775 178847
46775 173705
46775 91772
46775 81093
46775 103570
46775 66868
46775 91670
46775 129650
46775 149481
46775 182893
46775 115551
46775 167292
46775 182574
46775 95438
46775 167281
46775 160712
46775 121691
46775 12...

output:

745 804 865 899 1129 1205 1261 1366 1431 1491 1572 1695 1700 1740 1835 1862 1871 1883 1926 1986 1994 2198 2214 2229 2285 2313 2359 2374 2413 2440 2459 2477 2486 2493 2506 2529 2532 2545 2546 2557 2588 2622 2642 2676 2771 2778 2812 2821 2822 2825 2939 2963 3039 3058 3061 3106 3138 3143 3167 3199 3209...

result:

ok 10193 numbers

Test #8:

score: 10
Accepted
time: 25ms
memory: 5952kb

input:

180643 198737 94738
48353 166027
87663 136789
93307 135408
19654 33351
26552 33351
19265 33351
111942 134907
65187 149795
119612 170991
2417 33351
79279 166110
114686 162975
54701 163928
43129 116584
66103 139188
107280 147888
26067 33351
104751 139808
63876 148071
39714 129382
72905 148130
25384 33...

output:

33355 33356 33357 33358 33359 33361 33362 33363 33364 33365 33366 33367 33369 33371 33372 33373 33374 33375 33376 33377 33379 33380 33381 33385 33386 33387 33388 33392 33394 33396 33397 33398 33399 33401 33402 33403 33404 33405 33406 33407 33408 33410 33414 33415 33416 33417 33418 33419 33420 33421 ...

result:

ok 100917 numbers

Test #9:

score: 10
Accepted
time: 18ms
memory: 5852kb

input:

191508 185305 100905
63990 91135
7954 91135
17174 91135
39427 91135
1129 91135
78418 91135
75781 91135
7987 91135
51528 91135
148938 181214
40890 91135
67657 91135
56216 91135
29882 91135
33981 91135
76412 91135
115229 151727
98300 104478
182577 190282
125477 163728
68488 91135
64154 91135
20562 911...

output:

91137 91138 91139 91140 91143 91145 91146 91147 91148 91149 91153 91154 91155 91157 91158 91159 91161 91163 91164 91166 91167 91168 91169 91171 91174 91175 91177 91178 91180 91181 91182 91183 91184 91186 91187 91188 91191 91192 91194 91195 91196 91197 91199 91200 91201 91208 91210 91211 91213 91214 ...

result:

ok 37028 numbers

Test #10:

score: 10
Accepted
time: 14ms
memory: 5672kb

input:

191846 183854 90869
55728 85721
9713 85721
57235 85721
130204 144564
77210 85721
161065 162256
8962 85721
168055 177244
168055 174207
6371 85721
89768 136908
45508 85721
168055 185778
35520 85721
43450 85721
18758 85721
161027 162664
73184 85721
11364 85721
45366 85721
121115 163577
168055 190467
16...

output:

85723 85726 85728 85730 85732 85734 85736 85741 85742 85744 85745 85747 85748 85749 85750 85751 85752 85756 85758 85762 85763 85765 85767 85768 85771 85773 85776 85778 85780 85782 85787 85788 85789 85790 85791 85792 85793 85794 85795 85797 85798 85799 85800 85801 85802 85803 85804 85808 85809 85810 ...

result:

ok 28882 numbers

Extra Test:

score: 0
Extra Test Passed