QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#638030#7685. Barkley IIwuma123WA 56ms7824kbC++233.0kb2024-10-13 14:42:232024-10-13 14:42:23

Judging History

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

  • [2024-10-13 14:42:23]
  • 评测
  • 测评结果：WA
  • 用时：56ms
  • 内存：7824kb
查看
  • [2024-10-13 14:42:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=1000050;
struct query {
    int l,r,mex;
}q[2000050];

int maxn;
bool cmp(query &x,query &y){
    if(x.l/maxn != y.l/maxn) return x.l < y.l;
    else return x.r < y.r;
}

int arr[N];
map<int,int> mp;
vector <int> a[N];

int tot[N];
int dst;
void add(int x){
    if(!tot[x] ){
        dst ++;
    }
    tot[x] ++;
}
void del(int x){
    if(tot[x] == 1){
        dst--;
    }
    tot[x]--;
}
int res=-998244353;
void MO(int cnt){
    
    int p1=q[1].l,p2=q[1].r;
    for (int i=p1;i<=p2;i++)add(arr[i]);
    res=max(res,dst-q[1].mex);
    for (int i=2;i<=cnt;i++){
        while (p1>q[i].l)p1--,add(arr[p1]);
        while (p2>q[i].r)del(arr[p2]),p2--;
        while (p1<q[i].l)del(arr[p1]),p1++;
        while (p2<q[i].r)p2++,add(arr[p2]);
      //  cout <<q[i].mex<<":"<<q[i].l<<" "<<q[i].r<<" "<<dst<<endl;
        res=max(res,dst-q[i].mex);
    }
}
void solve(){
    int n,m;
    cin >>n>>m;
    dst=0;res=-998244353;
    for (int i=1;i<=n;i++){
        cin >>arr[i];
        a[arr[i]].push_back(i);
        mp[arr[i]]++;
    }
    int cnt=0;
    for (int i=1;i<=m;i++){
        if (mp[i]){
            //cout <<i<<":";
            if (a[i][0]>1)q[++cnt]={1,a[i][0]-1,i};
            else {
                if (i==1)res=max(res,-1);
                else res=max(res,0);
            }
            for (int j=0;j<a[i].size()-1;j++){
                //cout <<a[i][j]<<" ";
                if (a[i][j+1]-1<a[i][j]+1){
                    if (i==1)res=max(res,-1);
                    else res=max(res,0);
                };
                q[++cnt]={a[i][j]+1,a[i][j+1]-1,i};
            }
            //cout <<endl;
            if (a[i][a[i].size()-1]<n)q[++cnt]={a[i][a[i].size()-1]+1,n,i};
            else {
                if (i==1)res=max(res,-1);
                else res=max(res,0);
            }
        }else {
            q[++cnt]={1,n,i};
            break;
        }
        if (i==m){
            q[++cnt]={1,n,i+1};
        }
    }
    // int front[500010];
    // for(int i = 1;i<=n;i++){
    //     if(front[i]){
    //         int l = front[i] + 1;
    //         int r = i-1;
    //         if(l>r){
    //             if(arr[i] == 1) res = max(res,-1);
    //             else res = max(res,0);
    //         }
    //         else{
    //             q[++cnt] = {l,r,arr[i]};
    //         }
    //     }
    // }
    //特判
    maxn = sqrt(cnt);
    int flag = 1;
    for(int i = 1;i<=n;i++){
        if(arr[i] != 1) {flag = 0;break;} 
    }
    if(flag){
        cout<<-1<<endl;
        return;
    }

    sort(q+1,q+1+cnt,cmp);
    MO(cnt);

    for (auto it:mp){
        a[it.first].clear();
        tot[it.first]=0;
    }
    mp.clear();

    cout<<res<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
}
源文件, 语言: C++23

详细

Test #1:

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

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: 56ms
memory: 7808kb

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: 55ms
memory: 7744kb

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 2378th numbers differ - expected: '4', found: '2'
English 繁體中文 简体中文

服务器时间: 2024-12-03 07:52:32 | 开源项目