QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#640583#6258. Find my FamilyBaBamBa#AC ✓160ms28492kbC++172.2kb2024-10-14 14:27:252024-10-14 14:27:26

Judging History

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

  • [2024-10-14 14:27:26]
  • 评测
  • 测评结果：AC
  • 用时：160ms
  • 内存：28492kb
查看
  • [2024-10-14 14:27:25]
  • 提交

answer

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

using ll = long long;

ll query(vector<ll> &segtree, ll node, ll start, ll end, ll left, ll right)
{
    if (right < start || end < left)
        return INT32_MAX;
    if (left <= start && end <= right)
        return segtree[node];
    ll mid = (start + end) / 2;

    return min(query(segtree, 2 * node, start, mid, left, right), query(segtree, 2 * node + 1, mid + 1, end, left, right));
}

void update(vector<ll> &segtree, ll node, ll start, ll end, ll ind, ll upd)
{
    if (ind < start || end < ind)
        return;
    if (start == end)
    {
        segtree[node] = upd;
        return;
    }
    ll mid = (start + end) / 2;

    update(segtree, 2 * node, start, mid, ind, upd);
    update(segtree, 2 * node + 1, mid + 1, end, ind, upd);
    segtree[node] = min(segtree[2 * node], segtree[2 * node + 1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll K;
    cin >> K;
    vector<ll> ans;
    for (int k = 1; k <= K; k++)
    {
        ll N;
        cin >> N;

        vector<ll> inp(N + 2);
        vector<ll> coord;

        vector<ll> segtree(4 * N + 10);
        for (int i = 1; i <= N; i++)
        {
            cin >> inp[i];
            coord.push_back(inp[i]);
        }
        sort(coord.begin(), coord.end());
        coord.erase(unique(coord.begin(), coord.end()), coord.end());
        vector<ll> suf_max(4 * N + 10);
        for (int i = N; i >= 1; i--)
        {
            if (i == N)
                suf_max[i] = inp[i];
            else
                suf_max[i] = max(suf_max[i + 1], inp[i]);
        }
        for (int i = 0; i < N; i++)
            update(segtree, 1, 0, N - 1, i, INT32_MAX);
        for (int i = 1; i <= N - 1; i++)
        {
            ll pos = lower_bound(coord.begin(), coord.end(), inp[i]) - coord.begin();
            if (query(segtree, 1, 0, N - 1, pos, N - 1) < suf_max[i + 1])
            {
                ans.push_back(k);
                break;
            }
            update(segtree, 1, 0, N - 1, pos, inp[i]);
        }
    }
    cout << ans.size() << '\n';
    for (auto &x : ans)
        cout << x << '\n';
}
源文件, 语言: C++17

詳細信息

Test #1:

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

input:

1
3
2 1 3

output:

1
1

result:

ok 2 lines

Test #2:

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

input:

4
4
140 157 160 193
5
15 24 38 9 30
6
36 12 24 29 23 15
6
170 230 320 180 250 210

output:

2
2
4

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 154ms
memory: 24708kb

input:

1
271273
43747 45949 45991 59771 62951 78721 90843 96669 105382 125056 190481 223823 234273 241140 245677 331310 332730 342496 346873 364619 374954 395547 396228 402197 405521 425867 463937 465115 480404 509574 527742 529523 531604 542717 555276 567633 607526 642706 675568 702732 726193 728907 74120...

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 65ms
memory: 26672kb

input:

1
278011
727061307 368308202 520895620 233571177 962866275 741680843 264488440 68105796 948966820 466360363 79235752 189876633 279183294 707022089 551954537 533095838 391251801 821128899 372263578 515707123 232234930 644859992 86801330 757154237 807459900 586448507 672723131 452745534 295498461 6162...

output:

1
1

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 153ms
memory: 28492kb

input:

179
6
172113495 59803164 782209477 34402441 69284247 650685671
5
985712353 368711252 482009833 526445043 916859899
4
590307238 387574595 458391611 853071135
5
955235353 236771554 596823814 599387985 431401542
5
671335527 489612401 642100211 68409147 878368953
6
221011605 485556690 458137100 74629254...

output:

111
1
3
5
6
8
9
10
13
14
15
16
18
19
20
21
23
24
25
27
30
34
36
37
38
39
40
44
46
48
49
50
51
52
53
56
57
62
64
67
68
69
70
71
72
73
74
75
77
78
81
83
84
85
86
87
89
91
92
93
94
95
96
97
100
101
103
105
110
111
112
115
116
117
118
121
124
128
130
131
133
134
135
136
137
138
140
141
142
143
145
148
1...

result:

ok 112 lines

Test #6:

score: 0
Accepted
time: 95ms
memory: 26140kb

input:

1
288746
999999370 2776 3638 5685 8396 12385 18448 23357 23431 24053 26821 33895 33945 35216 35300 36819 40030 44278 51793 52147 57398 58637 58728 63060 66539 66967 72436 75943 77018 80903 92283 94711 97461 99142 110430 111376 116246 120415 122030 123053 137856 138352 141665 142800 143899 146476 154...

output:

1
1

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 75ms
memory: 25216kb

input:

1
280064
885432160 861890271 673081765 825997141 437019843 205150918 806237225 48809019 485906688 783124092 765117869 77410200 246637319 426923837 989652416 529199714 544609173 856902025 418963906 520673430 894792506 589045874 276081433 847047770 736503907 575852738 303448189 440901305 254285356 605...

output:

1
1

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 115ms
memory: 26564kb

input:

1
273892
4359 8492 10734 11826 12190 12708 14672 14946 17262 20178 32936 36767 37934 41456 41630 46058 46599 51950 54505 61746 67806 69860 70046 71276 72922 73909 80434 81117 83964 84565 88337 101068 102201 126256 144238 144819 146515 149961 154097 157945 160142 165975 174404 176795 177856 178971 18...

output:

1
1

result:

ok 2 lines

Test #9:

score: 0
Accepted
time: 58ms
memory: 26916kb

input:

1
292321
999992502 999999232 999953997 999972314 999968675 999969643 999971979 999959059 999967020 999962829 999965766 999933787 999946276 999943724 999935703 999942587 999936208 999936986 999913123 999929772 999931248 999913910 999929441 999920813 999919847 999708017 999800743 999802562 999912504 9...

output:

1
1

result:

ok 2 lines

Test #10:

score: 0
Accepted
time: 150ms
memory: 25812kb

input:

1
283540
999994672 7078 10898 14599 15805 19110 19403 23876 999994003 28002 999988106 39387 49540 999983736 52054 52356 999983671 52978 999981538 53495 55704 58197 59565 999981411 999981045 60013 60837 63188 67064 74245 82957 84967 999978228 87089 999977896 87206 88258 89758 999973328 90535 95797 98...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 145ms
memory: 26352kb

input:

1
283720
999998167 999994333 999991914 999988107 999988015 999986737 999986446 999985780 999983355 999980752 999976517 999975025 999974668 999970593 999966984 999959203 999953577 999949243 999948272 999941984 999939687 999938004 999936549 999936215 999928003 999926573 999926303 999922714 999919226 9...

output:

0

result:

ok single line: '0'

Test #12:

score: 0
Accepted
time: 155ms
memory: 25344kb

input:

1
278135
2849 7950 11487 15949 16685 18371 18623 22902 24591 27298 28816 30720 33537 33861 36065 40533 40744 41971 51011 61179 66659 72903 74048 75590 83036 93430 95904 103357 115621 118231 123049 125806 131178 132153 133800 135986 139846 145987 149972 150744 150914 155527 156346 156922 163168 16413...

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 147ms
memory: 27140kb

input:

1
286929
999993115 999996977 999989261 999980582 999981165 999974515 999975296 999976150 999462245 999926880 999943523 999961264 999967698 999959793 999951605 999953434 999954738 999947963 999949379 999945025 999947164 999934247 999938867 999936719 999926932 999932075 999463352 999925342 999920434 9...

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 36ms
memory: 4084kb

input:

13
9878
993857412 945170909 94222906 795839035 85863620 606456606 339859566 410007811 198312053 483907208 297030184 333083866 22795124 198113650 171472766 690075705 500811241 875559507 386458136 505369043 119417165 86978308 152840700 308175881 522618794 734545031 949707575 470071730 38017276 3609640...

output:

6
1
5
7
8
10
11

result:

ok 7 lines

Test #15:

score: 0
Accepted
time: 151ms
memory: 26780kb

input:

1
280553
878700327 878700899 878704269 878708099 878710723 878716287 878725220 878728251 878728809 878732035 878733685 878736110 878743881 878744391 878745156 878745676 878748060 878749582 878750716 878750758 878757024 878758046 878758948 878762077 878772056 878773358 878774114 878776556 878776716 8...

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 144ms
memory: 26496kb

input:

1
286166
999997508 999987924 999992602 999974154 999986525 999974959 999985286 999977261 999984627 999961581 999972550 999965238 999969094 998306262 999959433 999940294 999940970 999952334 999949129 999946370 999948631 999942783 999758419 999926802 999935945 999936945 999918390 999923141 999919471 9...

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 142ms
memory: 25892kb

input:

1
286052
1520 102457711 102459663 102460060 102466770 102470521 102476053 102477733 102477840 102482499 102494856 102495424 102501905 102504219 102506301 102506784 102508074 102518828 102528040 102529074 102535896 102537367 102543545 102552598 102560707 102562724 102562933 102565547 102568603 102569...

output:

1
1

result:

ok 2 lines

Test #18:

score: 0
Accepted
time: 127ms
memory: 25952kb

input:

1
275592
9154 999994589 999992891 999985960 9966 11875 999985284 28975 999972077 999971584 999971075 999967914 29689 38898 59488 999961496 79228 81500 999960558 90313 999958383 999956096 92834 999956028 99415 103267 999954086 999954068 999948601 106187 999948554 999945983 108329 999942911 999941426 ...

output:

1
1

result:

ok 2 lines

Test #19:

score: 0
Accepted
time: 80ms
memory: 25496kb

input:

1
284359
999998088 2351 27666 39695 48641 999998025 999986735 999985299 999984085 113157 999982458 999978892 149991 190322 232549 999975199 999966687 999966583 999966229 999962253 999960017 249919 999958416 999955595 999953466 276726 999952247 288326 999951648 999946232 999944431 999940672 374076 99...

output:

1
1

result:

ok 2 lines

Test #20:

score: 0
Accepted
time: 160ms
memory: 26524kb

input:

1
292570
12530 14660 15360 22897 22912 29457 35183 44718 47982 54260 56402 61653 62682 63955 68559 69420 72054 83084 104105 112294 112775 116343 123786 129775 132884 133777 135472 141678 146791 156630 156863 166853 167611 170211 173311 176654 187119 189291 204114 210255 218809 232777 234922 239586 2...

output:

0

result:

ok single line: '0'

Test #21:

score: 0
Accepted
time: 158ms
memory: 27608kb

input:

1
295148
74202 999996121 999988358 91220 94045 999981793 999981480 106402 108359 108859 999977828 999972349 999964837 117751 999867821 999869769 999961059 999953414 999955846 999956985 999958436 999958686 999944231 999945505 999870409 999904925 999910683 999915908 999944195 999939255 999907070 99987...

output:

0

result:

ok single line: '0'

Test #22:

score: 0
Accepted
time: 91ms
memory: 25808kb

input:

1
277088
415 961 9105 10499 18447 18783 24622 26102 39574 40655 42370 42646 43667 43830 44010 44587 48866 51336 58156 60433 64674 66512 74568 80778 81161 87057 88800 90915 92713 96105 105962 106089 111851 111932 113823 120593 122011 123036 125532 133545 134413 144480 145384 150348 151321 154750 1557...

output:

1
1

result:

ok 2 lines

Test #23:

score: 0
Accepted
time: 143ms
memory: 26956kb

input:

1
290322
839052438 839157763 999369202 999859175 999890139 999996540 999904524 999905498 999909851 999973984 999993264 999976763 999922590 999923002 999965540 999969252 999970561 999945454 999955477 999961850 999960001 999939899 999944954 999926906 999927570 999927993 999928900 999932443 999933687 9...

output:

0

result:

ok single line: '0'

Test #24:

score: 0
Accepted
time: 138ms
memory: 26604kb

input:

1
284258
2043 8784 13427 14954 16027 18312 19166 20649 22168 27445 29288 30577 34717 37135 37808 38434 41762 47008 48536 48571 56265 57615 63961 74356 74639 77851 85525 99923 106928 110220 113551 116352 117793 119906 121857 122246 122830 123051 124114 127271 129180 131810 136970 140730 142492 147659...

output:

0

result:

ok single line: '0'

Test #25:

score: 0
Accepted
time: 151ms
memory: 27024kb

input:

1
296169
6214 999998872 999998839 8516 999995616 999989910 999987141 999983896 999981799 999981202 999975618 999970052 999969792 999965049 999964570 999962308 999962161 999948586 13360 999943198 999940844 999936298 999935396 999934220 999926908 999922252 999918136 999914799 999913305 999911396 99990...

output:

0

result:

ok single line: '0'

Test #26:

score: 0
Accepted
time: 146ms
memory: 27044kb

input:

1
289433
999996039 999995880 999987622 2821 999987425 999985330 13623 16310 999974556 999972521 999969791 999963639 999958081 999954910 999953932 18340 19521 999947699 999947032 20867 21664 999945593 23797 999945110 27023 999938586 999936687 999933741 999932352 999927249 999913357 999905002 44562 99...

output:

1
1

result:

ok 2 lines

Test #27:

score: 0
Accepted
time: 123ms
memory: 27972kb

input:

40
6
408076530 273971198 804974770 715302215 663446017 908284135
6
414679550 5263165 115421774 412762783 346113067 132633234
6
397786079 717982033 321661863 783126452 551754505 566975416
100
25222230 885612561 967266588 986653695 973674026 889510606 965088039 903148955 915196845 925888669 941957415 ...

output:

31
1
3
5
6
7
8
9
11
13
14
16
18
19
20
22
23
24
25
26
27
28
29
30
31
32
33
34
35
37
38
40

result:

ok 32 lines

Test #28:

score: 0
Accepted
time: 142ms
memory: 26524kb

input:

1
271056
999969369 999973283 999975239 999990158 999972073 999897202 999941005 999964450 999968489 999963006 999942131 999951223 999952736 999946941 999900960 999928388 999930630 999937532 999917531 999920744 999922293 999922908 999905744 999913455 999916402 999917475 999909995 999912020 999735769 9...

output:

0

result:

ok single line: '0'

Test #29:

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

input:

71
9635
773916304 999810704 999949927 999966304 999766222 999774684 999809119 773929181 999545855 999750820 999760634 999759991 999742584 999137739 999045174 998008844 998604395 998831122 998984779 998863084 998973069 998861238 998531582 998149683 998262175 998409264 998164848 774164431 774342511 99...

output:

21
5
6
11
13
18
19
20
21
23
24
30
31
32
34
42
54
55
59
66
68
71

result:

ok 22 lines

Test #30:

score: 0
Accepted
time: 129ms
memory: 26556kb

input:

1
292602
2332 5905 8222 14327 23452 24783 26262 28423 29230 34661 34826 54172 64234 71507 75478 79125 89293 90498 112799 126999 128262 142601 152600 157334 172443 177692 185485 195965 197156 198245 198370 216835 225439 229494 229653 232464 247427 257251 263324 264255 272233 279766 285904 286476 2916...

output:

1
1

result:

ok 2 lines

Test #31:

score: 0
Accepted
time: 159ms
memory: 26328kb

input:

1
292745
912618964 912621910 912623485 912625318 912625714 912626995 912630877 912633145 912638407 912641510 912643628 912650129 912652753 912653238 912655808 912660447 912662173 912665286 912665358 912666217 912669998 912678804 912685736 912699855 912701714 912723271 912726707 912727100 912732457 9...

output:

0

result:

ok single line: '0'

Test #32:

score: 0
Accepted
time: 146ms
memory: 26008kb

input:

1
283986
999992054 7189 999990818 999984276 999987833 999975894 9347 997258626 997276994 999974813 999964189 999955400 999956617 999831648 999835253 999858941 999879492 999880920 999889688 999955001 999951374 999933226 999935551 999945950 999951192 999947193 999942621 999933690 999931575 999930783 9...

output:

0

result:

ok single line: '0'

Test #33:

score: 0
Accepted
time: 25ms
memory: 3608kb

input:

999
6
423407509 816208142 283446356 342834437 162798357 429531869
6
568606180 367367883 648283397 381508612 137175150 957065968
6
678592502 973813601 713256217 305653789 490077288 123395004
90
4687014 27864592 39430184 984646053 997837938 40192792 975834087 41235464 330550689 339860560 947915932 403...

output:

668
1
2
5
7
8
9
10
11
15
16
18
19
21
22
26
28
29
30
32
33
34
38
41
43
45
46
47
50
51
52
54
56
57
60
62
63
64
66
67
69
70
71
73
74
75
76
77
80
81
83
85
86
87
90
91
92
94
97
98
99
100
101
102
104
105
106
108
109
110
111
114
115
119
121
123
124
125
126
127
129
130
131
133
134
135
137
138
139
140
141
14...

result:

ok 669 lines

Test #34:

score: 0
Accepted
time: 72ms
memory: 27460kb

input:

1
289166
820723203 422083011 70529690 915209705 880220976 740427960 467704351 399839950 660102439 335964703 514609129 196049950 124833641 700925211 380179534 541456624 873698697 537638802 105254189 225720217 448362365 442684118 954868163 765145044 870397716 156783982 292856053 559184589 170867040 88...

output:

1
1

result:

ok 2 lines

Test #35:

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

input:

783
101
384625153 590120329 97474836 888818444 227568082 928475718 777165627 985470301 836880827 828008053 324298752 738825656 401355847 260496176 625916870 330768374 532157324 759160315 499291739 936070421 48863192 893466374 641170811 645571555 523700034 172420525 660357817 721522663 60218168 71012...

output:

779
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
...

result:

ok 780 lines

Test #36:

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

input:

270
27
322843267 326970746 182939003 762867750 495593852 603830331 624063851 776122580 468538547 134350504 709659683 884509149 810623679 801407553 132864447 646883144 446674405 718468236 470347616 590286881 21640629 126725103 225362604 930259301 593237079 489361081 169125187
26
899537341 65456184 89...

output:

253
1
2
3
4
5
6
7
8
9
10
11
12
13
14
16
17
18
19
20
21
22
23
24
25
26
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
61
62
63
64
65
66
67
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
10...

result:

ok 254 lines

Test #37:

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

input:

902
10
677268290 839831603 91860638 85717056 206965075 434289366 998277057 858655964 232235885 916577982
29
753356115 297404698 437132758 917118928 21499231 524684014 128116238 319450092 261526481 850173835 25961382 344709134 462402870 962478988 732341077 717613600 540351035 543421582 566414507 2757...

output:

844
1
2
3
4
5
6
7
8
9
10
11
12
13
15
16
17
18
19
20
21
23
24
25
26
27
28
29
30
31
32
33
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
61
63
64
65
66
67
68
69
70
73
74
76
77
78
79
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
109...

result:

ok 845 lines

Test #38:

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

input:

370
29
201164989 733517384 241942181 105272060 833797002 926140720 171924950 288356883 755173831 66984525 530205867 612459657 382636796 903487284 469599366 429036848 474889347 244783449 10264458 695222198 48892448 611930688 114947182 375168578 102323341 333344443 754406008 955146193 660450650
5
7014...

output:

345
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
69
70
71
72
73
74
75
78
79
80
81
82
83
84
85
86
87
88
90
91
92
93
94
96
97
98
99
100
101
102
103
104
105
10...

result:

ok 346 lines
English 繁體中文 简体中文

伺服器時間: 2024-12-11 21:25:16 | 開源專案