QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#618088#7685. Barkley IImulberryWA 64ms11856kbC++232.4kb2024-10-06 18:37:512024-10-06 18:37:52

Judging History

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

  • [2024-10-06 18:37:52]
  • 评测
  • 测评结果：WA
  • 用时：64ms
  • 内存：11856kb
查看
  • [2024-10-06 18:37:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define endl "\n"
#define fi first
#define se second
#define pb push_back
struct dd {
    ll l, r;
    ll num;
} xd[2002000];
ll idx = 0;
ll head[500500];
ll a[500500];
ll pos[500500];
ll js[500500];
bool cmp(dd a, dd b) {
    if (pos[a.l] == pos[b.l])
        return a.r < b.r;
    else
        return pos[a.l] < pos[b.l];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    cin >> t;
    while (t--) {
        ll n, m;
        cin >> n >> m;
        idx = 0;
        int sz = sqrt(n);
        for (int i = 1; i <= n; i++) {
            cin >> a[i], pos[i] = i / sz;
            if (i == 1) {
                head[a[i]] = 1;
                continue;
            }
            if (head[a[i]] + 1 > i - 1)
                head[a[i]] = i;
            else
                xd[++idx] = {head[a[i]] + 1, i - 1, a[i]};
            head[a[i]] = i;
        }
        // cout << "000" << endl;
        for (int i = 1; i <= min(n, m) + 10; i++) {
            if (head[i] != n) xd[++idx] = {head[i] + 1, n, i};
        }
        // for (int i = 1; i <= idx; i++) {
        //     cout << xd[i].l << " " << xd[i].r << " " << xd[i].num << endl;
        // }
        sort(xd + 1, xd + idx + 1, cmp);
        // cout << " 000 " << endl;
        int p1 = 1, p2 = 0;
        ll tot = 0;
        ll ans = -1;
        for (int i = 1; i <= idx; i++) {
            // cout << xd[i].l << " " << xd[i].r << endl;
            while (p2 < xd[i].r) {
                p2++;
                js[a[p2]]++;
                if (js[a[p2]] == 1) tot++;
            }
            while (p1 > xd[i].l) {
                p1--;
                js[a[p1]]++;
                if (js[a[p1]] == 1) tot++;
            }
            while (p2 > xd[i].r) {
                js[a[p2]]--;
                if (js[a[p2]] == 0) tot--;
                p2--;
            }
            while (p1 < xd[i].l) {
                js[a[p1]]--;
                if (js[a[p1]] == 0) tot--;
                p1++;
            }
            // cout << p1 << " " << p2 << endl;
            ans = max(ans, tot - xd[i].num);
        }
        cout << ans << endl;
        for (int i = 1; i <= min(n, m) + 10; i++) head[i] = 0, js[i] = 0;
    }
}
/*
2
5 4
1 2 2 3 4
5 10000
5 2 3 4 1
*/
源文件, 语言: C++23

详细

Test #1:

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

input:

2
5 4
1 2 2 3 4
5 10000
5 2 3 4 1

output:

2
3

result:

ok 2 number(s): "2 3"

Test #2:

score: 0
Accepted
time: 61ms
memory: 11788kb

input:

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

output:

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

result:

ok 50000 numbers

Test #3:

score: 0
Accepted
time: 54ms
memory: 11856kb

input:

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

output:

1
1
2
1
2
2
0
2
2
2
1
0
2
1
1
2
2
2
3
0
3
1
2
2
3
3
1
3
0
0
3
2
2
0
2
2
1
0
2
2
3
3
3
1
3
2
2
3
2
3
2
1
2
3
1
3
3
1
2
3
1
1
2
2
2
2
0
1
0
1
0
2
1
3
0
2
2
3
2
2
1
3
1
3
1
1
1
3
1
1
4
0
1
3
2
2
2
0
3
2
4
3
3
2
1
0
4
4
3
2
1
2
1
2
3
2
3
4
4
3
0
0
1
4
1
3
3
2
3
1
3
4
3
1
2
2
3
2
3
2
3
3
1
3
1
1
4
1
1
3
...

result:

ok 100000 numbers

Test #4:

score: -100
Wrong Answer
time: 64ms
memory: 11848kb

input:

25000
20 28
4 28 8 7 8 23 13 27 1 3 24 19 21 7 21 6 10 3 1 8
20 18
6 13 17 2 4 11 12 5 10 8 1 3 5 18 10 2 8 15 4 17
20 17
5 9 5 15 7 11 16 2 16 17 15 11 3 12 13 12 11 17 15 14
20 28
12 17 26 1 21 18 9 12 22 3 7 24 5 8 20 3 25 28 17 20
20 13
9 10 4 9 10 13 4 3 3 9 12 8 4 12 2 2 6 10 13 5
20 22
17 13 ...

output:

12
9
11
14
9
12
9
15
6
11
8
13
14
13
7
11
8
13
11
11
14
14
7
14
10
10
10
12
9
13
12
10
10
14
14
11
9
8
9
10
10
5
11
14
11
13
13
8
8
12
10
10
14
12
7
13
9
11
14
12
6
12
12
13
14
11
9
8
11
14
9
12
11
13
13
10
12
10
10
16
12
13
12
11
14
12
9
12
5
9
12
11
12
11
7
14
12
6
11
13
7
8
12
10
11
14
9
11
7
16
...

result:

wrong answer 24th numbers differ - expected: '15', found: '14'
English 繁體中文 简体中文

服务器时间: 2024-12-05 03:34:06 | 开源项目