QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618070#7685. Barkley IImulberryWA 116ms11948kbC++232.4kb2024-10-06 18:30:272024-10-06 18:30:30

Judging History

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

  • [2024-10-06 18:30:30]
  • 评测
  • 测评结果：WA
  • 用时：116ms
  • 内存：11948kb
查看
  • [2024-10-06 18:30:27]
  • 提交

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 <= m; i++) head[i] = 0, js[i] = 0;
        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 <= m; 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 = 0;
        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;
    }
}
/*
2
5 4
1 2 2 3 4
5 10000
5 2 3 4 1
*/
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11948kb

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: 81ms
memory: 11848kb

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: -100
Wrong Answer
time: 116ms
memory: 11920kb

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:

wrong answer 2377th numbers differ - expected: '-1', found: '0'
English 繁體中文 简体中文

Server Time: 2024-12-12 07:10:25 | OpenSource Project