QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#303321	#7685. Barkley II	ivaziva	TL	0ms	31056kb	C++17	2.2kb	2024-01-12 06:48:10	2024-01-12 06:48:10

Judging History

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

[2024-01-12 06:48:10]
评测

测评结果：TL
用时：0ms
内存：31056kb

查看

[2024-01-12 06:48:10]
提交

answer

#include <bits/stdc++.h>

using namespace std;

#define MAXN 500010

long long niz[MAXN];
vector<long long> pozicije[MAXN];
long long bit[MAXN];
long long last_visit[MAXN];
vector<pair<long long,long long>> query[MAXN];

void update(long long x,long long val,long long n)
{
    for (long long i=x;i<=n;i+=(i&(-i))) bit[i]+=val;
}

long long sol(long long x)
{
    long long br=0;
    for (long long i=x;i>=1;i-=(i&(-i))) br+=bit[i];
    return br;
}

void answer_queries(long long n)
{
    for (long long i=1;i<=n;i++) bit[i]=0;
    for (long long i=1;i<=n;i++) last_visit[i]=-1;
    long long ans=-LLONG_MAX;
    for (long long i=1;i<=n;i++)
    {
        if (last_visit[niz[i]]!=-1) update(last_visit[niz[i]],-1,n);
        last_visit[niz[i]]=i;
        update(i,1,n);
        long long s=query[i].size();
        for (long long j=0;j<s;j++)
        {
            long long l=query[i][j].first;
            long long mex=query[i][j].second;
            long long val=sol(i)-sol(l-1);
            ans=max(ans,val-mex);
        }
    }
    cout<<ans<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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<=n;i++) cin>>niz[i];
        for (long long i=1;i<=n;i++) pozicije[niz[i]].clear();
        for (long long i=1;i<=n;i++) query[i].clear();
        for (long long i=1;i<=n;i++) pozicije[niz[i]].push_back(i);
        for (long long i=1;i<=n;i++)
        {
            long long s=pozicije[niz[i]].size();
            for (long long j=1;j<s;j++)
            {
                long long poz1=pozicije[niz[i]][j-1];
                long long poz2=pozicije[niz[i]][j];
                if (poz2-1<poz1+1) continue;
                query[poz2-1].push_back({poz1+1,niz[i]});
            }
            long long poz1=pozicije[niz[i]][0];
            if (poz1-1>=1) query[poz1-1].push_back({1,niz[i]});
            long long poz2=pozicije[niz[i]][s-1];
            if (n>=poz2+1) query[n].push_back({poz2+1,niz[i]});
        }
        answer_queries(n);
    }
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 31056kb

input:

output:

2
3

result:

ok 2 number(s): "2 3"

Test #2:

score: -100

Time Limit Exceeded

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