QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#708488#4780. 完美的队列TheZone100 ✓1516ms10964kbC++206.4kb2024-11-03 22:51:422024-11-03 22:51:43

Judging History

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

  • [2024-11-03 22:51:43]
  • 评测
  • 测评结果：100
  • 用时：1516ms
  • 内存：10964kb
查看
  • [2024-11-03 22:51:42]
  • 提交

answer

#include <bits/stdc++.h>

#define i64 long long
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)

using namespace std;

const int N = 1e5 + 5, B = 4e2 + 5;

struct Operator {
    int l, r, x;
    Operator(int _l = 0, int _r = 0, int _x = 0) { l = _l; r = _r; x = _x; }
} op[N];

int n, m, totD, totB;
int L[B], R[B];
int a[N], bel[N], need[N], endTime[N], sum[N], d[N], bucket[N], cov[N];
vector<int> popID[N];

void workBlock(int b) {
    int cnt = 0, Max = 0;
    rep(i, L[b], R[b]) need[i] = a[i], Max = max(Max, need[i]); 
    
    auto workOP = [&](int id, int v) -> void {
        int ql = op[id].l, qr = op[id].r;

        if(ql <= L[b] && R[b] <= qr) cnt += v;
        else if(qr >= L[b] && ql <= R[b]) {
            Max = 0;
            rep(i, L[b], R[b]) {
                if(ql <= i && i <= qr) need[i] -= v;
                Max = max(Max, need[i]);
            }
        }
    };  

    for(int l = 1, r = 0; l <= m; l++) {
        while(r <= m && Max >= cnt) workOP(++r, 1);
        if(op[l].l <= L[b] && R[b] <= op[l].r) endTime[l] = max(endTime[l], r);
        workOP(l, -1);
    }

    totD = totB = 0;
    rep(i, 1, m) sum[i] = 0;
    rep(i, 1, m) {
        int ql = op[i].l, qr = op[i].r;

        if(ql <= L[b] && R[b] <= qr) {
            cov[++totB] = i;
            sum[totB] = sum[totB - 1] + 1;
        }
        else if(qr >= L[b] && ql <= R[b]) {
            cov[++totB] = i;
            d[++totD] = totB;
            sum[totB] = sum[totB - 1];
        }
    }

    cov[totB + 1] = m + 1;

    auto add = [&](int pos, int id, int v, int tar) -> void {
        int ql = op[cov[d[id]]].l, qr = op[cov[d[id]]].r;
        if(id != tar) cnt += v * (sum[d[id]] - sum[d[id - 1]]);
        if(ql <= pos && pos <= qr) cnt += v;
    };  

    auto del = [&](int pos, int id) -> void {
        int ql = op[cov[d[id]]].l, qr = op[cov[d[id]]].r;
        cnt -= (sum[d[id + 1]] - sum[d[id]]);
        if(ql <= pos && pos <= qr) cnt -= 1;
    };

    rep(i, L[b], R[b]) {
        cnt = 0; Max = a[i];
        for(int l = 1, r = 0; l <= totD;) {
            while(r < totD && Max >= cnt) add(i, ++r, 1, l);
            if(op[cov[d[l]]].l <= i && i <= op[cov[d[l]]].r) {
                if(Max >= cnt) {
                    int rest = Max - cnt + 1;
                    endTime[cov[d[l]]] = max(endTime[cov[d[l]]], cov[min(d[r] + rest, totB + 1)]);
                }
                else {
                    add(i, r--, -1, l);
                    int rest = Max - cnt + 1;
                    endTime[cov[d[l]]] = max(endTime[cov[d[l]]], cov[min(d[r] + rest, totB + 1)]);
                    add(i, ++r, 1, l);
                }
            }
            del(i, l++);
        }
    }
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];

    int B = sqrt(n), block = (n - 1) / B + 1;
    rep(i, 1, n) bel[i] = (i - 1) / B + 1;
    rep(i, 1, block) L[i] = (i - 1) * B + 1, R[i] = i * B;
    R[block] = n;

    rep(i, 1, m) cin >> op[i].l >> op[i].r >> op[i].x;

    rep(i, 1, block) workBlock(i);

    rep(i, 1, m) popID[endTime[i]].push_back(i);

    int ans = 0;
    rep(i, 1, m) {
        if(++bucket[op[i].x] == 1) ans++;
        for(auto id : popID[i]) if(--bucket[op[id].x] == 0) ans--;

        cout << ans << "\n";
    }

    return 0;
}
/*#include <bits/stdc++.h>

#define i64 long long
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)

using namespace std;

const int N = 1e5 + 5, B = 4e2 + 5;

struct Operator {
    int l, r, x;
    Operator(int _l = 0, int _r = 0, int _x = 0) { l = _l; r = _r; x = _x; }
} op[N];

int n, m, totD, totB;
int L[B], R[B];
int a[N], bel[N], need[N], endTime[N], sum[N], d[N], bucket[N], cov[N];
vector<int> popID[N];

void workBlock(int b) {
    int cnt = 0, Max = 0;
    rep(i, L[b], R[b]) need[i] = a[i], Max = max(Max, need[i]); 
    
    auto workOP = [&](int id, int v) -> void {
        int ql = op[id].l, qr = op[id].r;

        if(ql <= L[b] && R[b] <= qr) cnt += v;
        else if(qr >= L[b] && ql <= R[b]) {
            Max = 0;
            rep(i, L[b], R[b]) {
                if(ql <= i && i <= qr) need[i] -= v;
                Max = max(Max, need[i]);
            }
        }
    };  

    for(int l = 1, r = 0; l <= m; l++) {
        while(r <= m && Max >= cnt) workOP(++r, 1);
        if(op[l].l <= L[b] && R[b] <= op[l].r) endTime[l] = max(endTime[l], r);
        workOP(l, -1);
    }

    totD = totB = 0;
    rep(i, 1, m) sum[i] = 0;
    rep(i, 1, m) {
        int ql = op[i].l, qr = op[i].r;

        if(ql <= L[b] && R[b] <= qr) {
            cov[++totB] = i;
            sum[totB] = sum[totB - 1] + 1;
        }
        else if(qr >= L[b] && ql <= R[b]) {
            cov[++totB] = i;
            d[++totD] = totB;
            sum[totB] = sum[totB - 1];
        }
    }

    cov[totB + 1] = m + 1;

    auto add = [&](int pos, int id, int v, int tar) -> void {
        int ql = op[cov[d[id]]].l, qr = op[cov[d[id]]].r;
        if(id != tar) cnt += v * (sum[d[id]] - sum[d[id - 1]]);
        if(ql <= pos && pos <= qr) cnt += v;
    };  

    auto del = [&](int pos, int id) -> void {
        int ql = op[cov[d[id]]].l, qr = op[cov[d[id]]].r;
        cnt -= (sum[d[id + 1]] - sum[d[id]]);
        if(ql <= pos && pos <= qr) cnt -= 1;
    };

    rep(i, L[b], R[b]) {
        cnt = 0; Max = a[i];
        for(int l = 1, r = 0; l <= totD;) {
            while(r < totD && Max >= cnt) add(i, ++r, 1, l);
            if(op[cov[d[l]]].l <= i && i <= op[cov[d[l]]].r) {
                if(Max >= cnt) {
                    int rest = Max - cnt + 1;
                    endTime[cov[d[l]]] = max(endTime[cov[d[l]]], cov[min(d[r] + rest, totB + 1)]);
                }
                else {
                    add(i, r--, -1, l);
                    int rest = Max - cnt + 1;
                    endTime[cov[d[l]]] = max(endTime[cov[d[l]]], cov[min(d[r] + rest, totB + 1)]);
                    add(i, ++r, 1, l);
                }
            }
            del(i, l++);
        }
    }
}

int main() {

    ios::sync_with_stdio(false);
    }

    return 0;
}*/
源文件, 语言: C++20

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 15ms
memory: 6568kb

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: 50ms
memory: 8916kb

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: 92ms
memory: 9324kb

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: 140ms
memory: 9388kb

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: 122ms
memory: 10632kb

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: 253ms
memory: 9888kb

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: 193ms
memory: 10328kb

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: 388ms
memory: 10480kb

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: 285ms
memory: 10688kb

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: 536ms
memory: 9960kb

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: 436ms
memory: 10824kb

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: 703ms
memory: 10180kb

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: 573ms
memory: 10792kb

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: 892ms
memory: 10296kb

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: 689ms
memory: 10964kb

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: 1080ms
memory: 10476kb

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: 1180ms
memory: 10332kb

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: 1270ms
memory: 10248kb

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: 1404ms
memory: 10408kb

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: 1516ms
memory: 10468kb

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:45:40 | 开源项目