QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#71783#4780. 完美的队列He_Ren100 ✓899ms14260kbC++144.5kb2023-01-12 01:12:412023-01-12 01:12:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-12 01:12:44]
  • 评测
  • 测评结果：100
  • 用时：899ms
  • 内存：14260kb
查看
  • [2023-01-12 01:12:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXX = 1e5 + 5;
const int B = 300;
const int inf = 0x3f3f3f3f;

inline void chk_max(int &a, int b) {
    if (a < b)
        a = b;
}
inline void chk_min(int &a, int b) {
    if (a > b)
        a = b;
}

int a[MAXN];

int ql[MAXM], qr[MAXM], qx[MAXM];
int res[MAXM];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    for (int i = 1; i <= m; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        ql[i] = l;
        qr[i] = r;
        qx[i] = x;
        res[i] = i;
    }

    for (int bl = 1, br; bl <= n; bl = br + 1) {
        br = min(n, bl + B);

        static int big[MAXM], small[MAXM], bigcnt[MAXM];
        static int small_l[MAXM], small_r[MAXM];

        static int allbig[MAXM], allsmall[MAXM], allsmall_l[MAXM], allsmall_r[MAXM];
        int bigtot = 0, smalltot = 0;

        memset(big, 0, (m + 2) << 2);
        memset(small, 0, (m + 2) << 2);

        for (int i = 1; i <= m; ++i) {
            int l = ql[i], r = qr[i];

            if (l <= bl && br <= r) {
                big[i] = i;
                allbig[++bigtot] = i;
            } else if (max(l, bl) <= min(r, br)) {
                small[i] = i;
                small_l[i] = max(l, bl);
                small_r[i] = min(r, br);
                allsmall[++smalltot] = i;
                allsmall_l[smalltot] = small_l[i];
                allsmall_r[smalltot] = small_r[i];
            }

            bigcnt[i] = bigcnt[i - 1] + (big[i] != 0);
        }

        bigcnt[m + 1] = bigcnt[m];

        {
            static int val[MAXN];
            int mn = 0, tag = 0;

            for (int i = bl; i <= br; ++i)
                val[i] = -a[i], mn = min(mn, val[i]);

            auto upd_small = [&](int i, int k) {
                mn = inf;

                for (int j = small_l[i]; j <= small_r[i]; ++j)
                    val[j] += k;

                for (int j = bl; j <= br; ++j)
                    chk_min(mn, val[j]);
            };
            auto upd = [&](int i, int k) {
                if (big[i])
                    tag += k;
                else if (small[i])
                    upd_small(i, k);
            };

            upd(1, 1);

            for (int i = 1, j = 1; i <= m; ++i) {
                while (j <= m && mn + tag <= 0)
                    upd(++j, 1);

                if (big[i])
                    chk_max(res[i], j);

                upd(i, -1);
            }
        }

        {
            for (int rn = bl; rn <= br; ++rn) {
                static int pos[MAXM];
                int tot = 0;

                for (int i = 1; i <= smalltot; ++i)
                    if (allsmall_l[i] <= rn && rn <= allsmall_r[i])
                        pos[++tot] = allsmall[i];

                if (!tot)
                    continue;

                pos[tot + 1] = m + 1;

                for (int i = 1, j = 1; i <= tot; ++i) {
                    while (j <= tot && (j - i + 1) + bigcnt[pos[j]] - bigcnt[pos[i]] <= a[rn])
                        ++j;

                    int cur = (j - i + 1) + bigcnt[pos[j]] - bigcnt[pos[i]];

                    if (j > tot)
                        --cur;

                    if (cur <= a[rn]) {
                        res[pos[i]] = m + 1;
                    } else if (j <= tot) {
                        if (cur == a[rn] + 1)
                            chk_max(res[pos[i]], pos[j]);
                        else {
                            int t = cur - a[rn] - 2;
                            chk_max(res[pos[i]], allbig[bigcnt[pos[j]] - t]);
                        }
                    } else {
                        int t = cur - a[rn] - 1;
                        chk_max(res[pos[i]], allbig[bigtot - t]);
                    }
                }
            }
        }
    }

    static vector<pii> eff[MAXM];

    for (int i = 1; i <= m; ++i) {
        eff[i].emplace_back(qx[i], 1);
        eff[res[i]].emplace_back(qx[i], -1);
    }

    static int cnt[MAXX];
    int has = 0;

    for (int i = 1; i <= m; ++i) {
        for (auto t : eff[i]) {
            int x = t.first;
            has -= cnt[x] != 0;
            cnt[x] += t.second;
            has += cnt[x] != 0;
        }

        cout << has << '\n';
    }

    return 0;
}
源文件, 语言: C++14

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 22ms
memory: 8224kb

input:

5000 4999
99 36 47 78 58 58 64 12 42 54 29 56 57 32 99 21 1 6 42 97 82 8 79 92 3 56 19 41 29 59 23 34 76 34 82 20 44 51 60 73 89 65 51 65 15 87 65 70 51 26 40 95 44 62 97 81 43 13 20 81 76 64 47 95 54 56 99 62 91 63 98 58 70 60 47 97 31 74 76 70 10 30 99 33 52 100 14 65 4 6 87 4 8 1 8 87 18 70 76 43...

output:

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
10...

result:

ok 4999 numbers

Subtask #2:

score: 5
Accepted

Dependency #1:

100%
Accepted

Test #2:

score: 5
Accepted
time: 53ms
memory: 6840kb

input:

9999 10000
60 75 4 70 26 87 8 77 16 6 20 88 95 44 60 10 71 93 68 33 30 71 21 19 88 61 26 93 21 83 35 83 25 72 33 75 40 14 92 54 10 42 60 93 73 82 13 50 50 25 99 16 68 38 78 14 4 1 58 72 2 96 69 57 43 71 68 100 5 49 50 58 50 61 53 22 88 55 95 37 67 96 50 46 55 97 84 28 62 56 44 35 80 5 59 45 50 14 48...

output:

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
102
...

result:

ok 10000 numbers

Subtask #3:

score: 5
Accepted

Dependency #2:

100%
Accepted

Test #3:

score: 5
Accepted
time: 76ms
memory: 7124kb

input:

15000 15000
8 2 78 69 72 23 22 79 69 75 63 19 90 94 45 5 1 44 53 34 80 80 26 43 9 86 85 38 71 88 90 2 22 46 60 7 14 18 77 44 5 80 80 48 9 51 38 49 7 2 73 64 67 84 44 7 53 9 84 21 90 35 69 46 5 74 27 73 78 91 10 68 50 5 98 55 17 99 99 81 38 20 99 81 91 19 87 26 71 19 49 44 70 29 5 33 21 49 75 5 79 84...

output:

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
102
...

result:

ok 15000 numbers

Subtask #4:

score: 5
Accepted

Dependency #3:

100%
Accepted

Test #4:

score: 5
Accepted
time: 107ms
memory: 7608kb

input:

20000 20000
96 95 34 72 28 92 86 48 37 22 76 41 18 23 56 52 32 48 37 96 75 17 69 22 81 79 60 82 79 12 69 15 58 79 7 7 63 70 58 69 68 18 96 29 69 70 4 7 75 27 18 44 49 53 89 15 10 97 75 58 52 54 65 91 48 33 5 91 59 12 2 6 30 99 79 45 91 14 36 15 98 88 11 73 98 3 8 22 45 41 42 71 31 29 16 44 72 100 57...

output:

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
102
...

result:

ok 20000 numbers

Subtask #5:

score: 5
Accepted

Test #5:

score: 5
Accepted
time: 105ms
memory: 7968kb

input:

25000 25000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1
2
3
4
5
5
5
3
3
4
4
4
5
4
4
5
6
7
6
6
7
8
9
6
7
8
8
7
8
9
7
8
9
10
8
8
9
10
10
11
12
12
5
6
7
8
9
4
5
6
7
5
6
7
8
6
7
8
7
8
9
10
11
10
11
12
13
13
12
12
9
10
7
8
7
8
8
6
7
8
8
9
9
10
7
8
9
9
9
10
11
10
11
12
12
13
13
14
15
16
15
15
11
4
5
6
7
8
8
9
9
8
9
9
10
11
10
8
8
8
9
9
10
10
10
6
6
7
8
9
4
5...

result:

ok 25000 numbers

Subtask #6:

score: 5
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #6:

score: 5
Accepted
time: 175ms
memory: 8260kb

input:

30000 30000
68 5 42 87 7 80 19 79 72 80 13 85 83 48 90 63 4 37 40 96 77 7 16 94 52 72 28 84 30 15 46 65 45 62 55 51 11 89 57 61 52 41 25 10 72 94 38 68 79 97 56 89 15 11 78 5 10 36 13 11 9 25 46 3 50 98 100 86 23 56 59 38 12 29 50 94 73 7 7 59 74 4 98 21 42 1 37 35 12 67 2 7 37 17 19 60 91 64 57 95 ...

output:

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
102
...

result:

ok 30000 numbers

Subtask #7:

score: 5
Accepted

Test #7:

score: 5
Accepted
time: 167ms
memory: 8872kb

input:

34999 35000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
11
7
7
8
9
10
10
11
12
11
12
12
11
9
8
9
4
5
6
7
8
9
10
10
11
12
13
13
14
15
16
17
17
17
16
14
11
11
12
13
14
15
14
14
13
14
14
15
14
15
16
17
18
19
19
19
20
19
16
16
15
15
15
12
13
14
15
16
17
18
19
18
19
19
19
19
17
18
18
19
20
21
21
21
22
18
19
20
21
20
20
19
20
21
2...

result:

ok 35000 numbers

Subtask #8:

score: 5
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Test #8:

score: 5
Accepted
time: 243ms
memory: 9120kb

input:

40000 40000
17 23 52 38 20 94 83 41 49 13 61 29 39 58 31 87 29 63 23 94 63 95 78 64 8 3 72 67 30 54 51 34 1 97 52 6 8 64 68 97 2 63 12 30 43 2 46 86 56 58 58 36 3 89 49 79 37 38 57 15 45 3 55 76 60 76 92 51 7 15 5 34 87 31 67 24 6 52 31 95 23 58 59 44 74 77 92 7 21 50 10 76 84 21 34 95 2 5 59 61 18 ...

output:

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
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
1...

result:

ok 40000 numbers

Subtask #9:

score: 5
Accepted

Test #9:

score: 5
Accepted
time: 260ms
memory: 9800kb

input:

45000 45000
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
17
18
19
20
21
22
23
24
24
25
26
27
28
29
29
30
31
30
31
32
31
31
32
32
33
34
34
35
36
37
38
38
39
39
39
38
38
39
40
41
40
41
42
40
40
41
42
43
43
44
45
46
47
48
44
45
44
45
46
45
44
44
45
45
46
47
48
47
48
49
50
51
52
51
52
51
51
50
50
51
52
52
52
52
52
53
...

result:

ok 45000 numbers

Subtask #10:

score: 5
Accepted

Dependency #8:

100%
Accepted

Dependency #9:

100%
Accepted

Test #10:

score: 5
Accepted
time: 329ms
memory: 9876kb

input:

50000 50000
93 35 69 99 23 3 93 39 95 53 2 59 1 25 67 8 73 72 65 33 60 11 96 99 40 56 88 72 32 60 48 49 42 63 75 50 35 80 34 46 38 54 71 36 81 52 46 32 19 54 10 20 36 29 4 83 93 3 72 21 37 1 30 48 32 99 91 65 12 27 13 81 11 59 22 89 90 6 30 15 62 91 8 2 38 98 57 77 62 93 86 17 95 97 73 11 16 2 28 87...

output:

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
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
1...

result:

ok 50000 numbers

Subtask #11:

score: 5
Accepted

Dependency #5:

100%
Accepted

Dependency #7:

100%
Accepted

Dependency #9:

100%
Accepted

Test #11:

score: 5
Accepted
time: 351ms
memory: 10800kb

input:

54444 55000
3 5 10 6 4 10 10 6 2 10 5 2 6 9 10 6 5 9 3 4 7 6 9 1 1 2 6 10 5 2 6 3 10 3 4 7 3 3 3 5 9 2 2 8 6 10 6 9 1 1 3 2 6 8 9 3 10 4 10 5 6 5 7 6 9 4 7 4 10 8 5 10 1 5 8 4 4 5 9 3 9 3 2 1 2 7 5 10 3 4 6 10 4 8 6 9 6 6 6 8 8 3 3 2 9 9 7 3 8 9 4 4 3 5 10 5 10 6 7 2 10 1 1 10 6 1 6 3 7 1 8 7 9 4 5 ...

output:

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
32
33
33
33
32
33
34
35
36
37
38
38
39
38
37
38
39
40
40
40
41
42
43
44
45
46
46
47
48
48
49
50
51
50
51
51
52
53
54
55
54
53
53
52
53
54
52
53
52
51
52
52
53
54
55
52
53
54
53
54
54
54
55
56
56
56
55
55
56
55
54
...

result:

ok 55000 numbers

Subtask #12:

score: 5
Accepted

Dependency #11:

100%
Accepted

Test #12:

score: 5
Accepted
time: 454ms
memory: 11004kb

input:

60000 60000
55 3 74 22 46 71 40 1 41 52 27 48 31 19 84 36 89 45 7 36 91 41 79 43 43 64 58 6 80 80 66 52 60 58 47 84 31 11 74 43 74 23 79 31 45 17 85 49 53 96 45 92 59 30 30 15 59 63 52 47 17 10 72 91 8 29 1 74 86 100 91 13 85 77 79 34 10 83 76 54 52 63 5 76 45 62 80 47 21 46 36 12 9 93 28 50 86 43 9...

output:

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
102
...

result:

ok 60000 numbers

Subtask #13:

score: 5
Accepted

Test #13:

score: 5
Accepted
time: 436ms
memory: 11324kb

input:

65000 65000
5 7 8 6 3 6 8 7 2 3 5 10 9 9 4 3 9 1 2 9 1 1 6 10 1 10 5 4 7 1 9 6 6 8 10 5 8 3 2 5 2 3 6 8 7 3 2 3 6 5 1 10 6 2 4 7 8 1 3 3 5 4 2 5 2 5 3 3 6 7 6 9 5 3 10 3 6 2 8 10 9 10 2 5 4 10 3 3 6 3 5 7 141 3 6 3 10 2 7 6 3 5 9 4 10 1 3 9 9 8 2 5 10 1 7 1 8 5 3 3 7 7 9 7 4 1 9 2 2 4 8 6 10 5 7 3 3...

output:

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
102
...

result:

ok 65000 numbers

Subtask #14:

score: 5
Accepted

Dependency #12:

100%
Accepted

Dependency #13:

100%
Accepted

Test #14:

score: 5
Accepted
time: 541ms
memory: 11944kb

input:

70000 70000
54 42 81 48 90 100 68 36 70 5 93 14 38 37 27 29 66 51 92 69 40 74 70 59 69 85 38 24 24 83 53 66 58 69 26 5 31 19 34 19 92 31 80 65 39 22 61 44 18 84 69 4 28 81 60 16 54 90 10 44 63 100 52 10 65 14 28 42 25 46 89 82 67 92 61 15 40 87 72 49 31 57 52 71 16 27 28 33 96 11 75 12 35 1 23 93 80...

output:

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
102
...

result:

ok 70000 numbers

Subtask #15:

score: 5
Accepted

Dependency #13:

100%
Accepted

Test #15:

score: 5
Accepted
time: 542ms
memory: 12100kb

input:

75000 75000
1 8 2 4 4 7 1 2 5 4 1 3 2 4 2 2 3 3 3 6 1 4 8 5 3 6 8 3 9 4 5 5 3 6 9 2 9 6 1 4 2 8 5 8 2 7 4 3 4 4 1 9 4 5 8 1 4 8 6 5 8 6 6 5 4 7 6 3 3 6 6 4 7 4 4 1 9 6 6 4 6 4 1 9 7 3 4 7 7 5 9 9 7 3 5 9 7 3 5 7 3 8 6 2 6 2 8 8 8 6 9 5 1 3 3 2 9 7 6 8 2 3 4 6 7 4 8 1 4 5 5 7 7 4 5 8 9 6 2 1225 7 9 6...

output:

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
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
1...

result:

ok 75000 numbers

Subtask #16:

score: 5
Accepted

Dependency #14:

100%
Accepted

Dependency #15:

100%
Accepted

Test #16:

score: 5
Accepted
time: 659ms
memory: 12668kb

input:

80000 80000
36 90 42 28 58 80 90 68 41 93 51 46 31 59 94 62 17 48 63 27 64 83 69 43 81 1 4 32 98 57 38 56 83 21 6 95 29 63 44 88 74 45 75 75 51 45 89 33 37 50 3 11 1 69 66 87 12 44 11 90 4 66 17 97 37 21 89 11 84 71 53 60 11 63 34 86 99 61 60 79 37 24 50 15 2 88 11 16 79 36 70 89 81 41 55 51 18 99 8...

output:

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
102
...

result:

ok 80000 numbers

Subtask #17:

score: 5
Accepted

Dependency #16:

100%
Accepted

Test #17:

score: 5
Accepted
time: 708ms
memory: 12992kb

input:

85000 85000
35 30 17 21 1 8 55 71 93 22 77 80 62 1 37 55 95 53 83 60 49 83 84 34 32 90 17 51 65 29 57 71 89 32 18 16 5 39 36 8 92 53 99 85 81 18 42 72 2 74 51 15 34 12 20 76 8 39 2 64 5 81 64 80 94 31 92 47 91 10 19 98 85 21 16 66 38 20 24 98 80 19 29 43 81 85 82 46 22 65 41 89 75 49 50 70 88 2 85 5...

output:

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
102
...

result:

ok 85000 numbers

Subtask #18:

score: 5
Accepted

Dependency #17:

100%
Accepted

Test #18:

score: 5
Accepted
time: 755ms
memory: 13556kb

input:

90000 90000
81 45 45 33 1 89 77 35 65 10 35 12 63 23 72 87 69 19 55 63 29 36 84 42 44 46 58 3 15 35 41 29 81 85 21 81 3 91 81 77 75 23 26 95 26 65 62 62 22 15 53 54 76 100 26 47 66 49 71 10 22 47 29 67 10 70 77 48 14 35 39 44 29 84 57 61 97 26 12 59 98 10 51 11 67 77 10 17 37 90 4 99 45 89 37 95 26 ...

output:

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
102
...

result:

ok 90000 numbers

Subtask #19:

score: 5
Accepted

Dependency #18:

100%
Accepted

Test #19:

score: 5
Accepted
time: 834ms
memory: 13852kb

input:

95000 95000
48 85 52 2 4 17 29 38 93 62 69 46 27 9 15 57 15 24 39 96 14 93 99 34 94 27 95 21 83 38 60 7 80 28 33 95 3 67 29 53 69 7 95 37 31 6 14 33 86 3 77 3 9 83 24 4 29 45 5 39 92 37 85 86 99 48 48 84 22 81 12 38 80 74 71 42 36 30 32 23 41 4 30 7 38 42 81 47 88 32 75 98 71 97 33 39 21 33 35 87 91...

output:

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
102
...

result:

ok 95000 numbers

Subtask #20:

score: 5
Accepted

Dependency #19:

100%
Accepted

Test #20:

score: 5
Accepted
time: 899ms
memory: 14260kb

input:

100000 100000
15 56 36 27 48 45 25 41 22 91 96 12 58 50 99 18 25 5 92 29 31 57 14 50 84 15 99 71 15 66 79 21 54 38 76 84 79 74 21 30 87 60 95 71 25 87 67 72 59 60 1 39 33 58 78 37 56 80 96 13 61 27 33 38 88 33 7 20 29 84 10 7 86 32 53 23 42 65 29 75 44 99 9 70 18 31 93 9 62 29 38 98 65 73 28 58 15 4...

output:

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
102
...

result:

ok 100000 numbers
English 繁體中文 简体中文

伺服器時間: 2024-11-30 06:55:13 | 開源專案