QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303298#7685. Barkley IIivazivaTL 777ms109012kbC++172.7kb2024-01-12 04:41:482024-01-12 04:41:49

Judging History

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

  • [2024-01-12 04:41:49]
  • 评测
  • 测评结果：TL
  • 用时：777ms
  • 内存：109012kb
查看
  • [2024-01-12 04:41:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define MAXN 500010

long long niz[MAXN];
set<long long> seg[MAXN*4];
bool obrisano[MAXN];
vector<long long> pozicije[MAXN];

void build(long long node,long long l,long long r)
{
    if (l==r) {seg[node].insert(niz[l]);return;}
    else
    {
        long long mid=(l+r)/2;
        build(2*node,l,mid);
        build(2*node+1,mid+1,r);
        seg[node].insert(seg[2*node].begin(),seg[2*node].end());
        seg[node].insert(seg[2*node+1].begin(),seg[2*node+1].end());
    }
}

set<long long> sol(long long node,long long l,long long r,long long a,long long b)
{
    set<long long> rez;
    if (a>b) return rez;
    if (l==a and r==b) return seg[node];
    long long mid=(l+r)/2;
    set<long long> levo=sol(2*node,l,mid,a,min(b,mid));
    set<long long> desno=sol(2*node+1,mid+1,r,max(a,mid+1),b);
    rez.insert(levo.begin(),levo.end());
    rez.insert(desno.begin(),desno.end());
    levo.clear();desno.clear();
    return rez;
}

int main()
{
    long long t;cin>>t;
    for (long long z=0;z<t;z++)
    {
        long long n,m;cin>>n>>m;
        for (long long i=1;i<=4*n;i++) seg[i].clear();
        for (long long i=1;i<=n;i++) cin>>niz[i];
        build(1,1,n);
        for (long long i=1;i<=n;i++) obrisano[niz[i]]=false;
        vector<long long> vec;
        long long ans=-LLONG_MAX;
        set<long long> x;
        for (long long i=1;i<=n;i++)
        {
            if (obrisano[niz[i]]==false)
            {
                pozicije[niz[i]].clear();
                obrisano[niz[i]]=true;
                vec.push_back(niz[i]);
            }
            pozicije[niz[i]].push_back(i);
            if (pozicije[niz[i]].size()==1)
            {
                x=sol(1,1,n,1,i-1);long long val=x.size();
                ans=max(ans,val-niz[i]);
                x.clear();
            }
            else
            {
                long long siz=pozicije[niz[i]].size();
                x=sol(1,1,n,pozicije[niz[i]][siz-2]+1,pozicije[niz[i]][siz-1]-1);long long val=x.size();
                ans=max(ans,val-niz[i]);
                x.clear();
            }
        }
        sort(vec.begin(),vec.end());
        long long mex_niza=1;
        for (long long i=0;i<vec.size();i++)
        {
            if (mex_niza==vec[i]) mex_niza++;
            long long siz=pozicije[vec[i]].size();
            long long poz=pozicije[vec[i]][siz-1];
            x=sol(1,1,n,poz+1,n);long long val=x.size();
            ans=max(ans,val-vec[i]);
            x.clear();
        }
        x=sol(1,1,n,1,n);long long val=x.size();
        ans=max(ans,val-mex_niza);
        cout<<ans<<endl;x.clear();
    }
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 108976kb

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: 401ms
memory: 108888kb

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: 300ms
memory: 108892kb

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: 0
Accepted
time: 777ms
memory: 109012kb

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
15
10
10
10
12
9
13
12
10
10
14
14
11
9
8
9
10
10
5
11
14
13
14
13
8
8
12
10
10
17
12
7
14
9
11
14
13
8
12
15
13
14
11
9
8
11
17
9
12
11
13
13
10
14
10
10
16
12
13
12
11
14
12
9
12
5
9
15
16
13
15
7
14
12
6
12
13
7
8
12
10
13
15
9
16
7
16
...

result:

ok 25000 numbers

Test #5:

score: -100
Time Limit Exceeded

input:

5000
100 100
71 48 44 27 73 73 90 42 69 81 79 99 97 3 45 78 38 92 89 27 97 7 4 91 42 59 7 45 88 100 15 66 64 6 26 54 38 38 72 81 15 94 35 63 33 85 100 16 41 5 71 20 92 36 39 59 19 59 11 22 11 26 94 29 73 98 16 16 47 25 35 50 49 6 67 85 69 90 6 87 72 24 37 62 55 54 25 38 95 14 15 26 89 26 25 46 14 24...

output:

59
78
69
48
78
53
64
73
53
66
59
57
62
42
73
69
46
68
66
47
59
64
71
57
73
43
52
66
67
61
66
66
65
58
80
65
65
69
75
76
69
39
69
61
53
72
44
62
63
71
76
56
69
79
49
73
62
71
83
59
70
53
69
73
47
68
74
59
66
74
75
61
53
76
48
62
79
71
47
72
40
80
62
42
63
70
72
70
70
59
68
56
74
54
61
78
68
75
70
39
...

result:
English 繁體中文 简体中文

Server Time: 2024-12-05 03:34:25 | OpenSource Project