QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#645555#7685. Barkley II22016020736TL 149ms20288kbC++172.5kb2024-10-16 18:58:232024-10-16 18:58:24

Judging History

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

  • [2024-10-16 18:58:24]
  • 评测
  • 测评结果：TL
  • 用时：149ms
  • 内存：20288kb
查看
  • [2024-10-16 18:58:23]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
int  pre[500009];
//map<int, int> pre, cnt;
int kuai;
map<int,int>cnt;
int arr[500009];
vector<int> pos[500009];
//int ne[500009][29];

struct node {
    int l, r, val;
} qry[500009];


bool cmp(node a,node b)
{
   if(a.l/kuai==b.l/kuai)
   {
      if((a.l/kuai)%2==0)
      {
           return a.r<b.r;
      }
      else
      {
         return a.r>b.r;
      }
   }
   else return a.l/kuai<b.l/kuai;

}
 int ans,cut;
void jia(int id)
{
    cnt[arr[id]]++;
    if(cnt[arr[id]]==1) cut++;
}

void jian(int id)
{
   cnt[arr[id]]--;
   if(cnt[arr[id]]==0) cut--;
}


int main() {
    int tt = 0;
   // cout<<(1<<25)<<endl;
    scanf("%d", &tt);
    while (tt--) {
        int tot = 0;
        int n,m;
        int mn=1e9+7,mx=-1;
        scanf("%d%d",&n,&m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &arr[i]);
            mn=min(arr[i],mn);
            mx=max(mx,arr[i]);
            if(arr[i] <= n )
            {
               if(pre[arr[i]]+1<=i-1)
               {
                 if(i-pre[arr[i]]-1>=arr[i]-1) qry[++tot]={pre[arr[i]]+1,i-1,arr[i]};
               }
              pre[arr[i]]=i;
            }
        }
        for (int i = 1; i <= n; i++) {
           if(pre[i]==0)
           {
            qry[++tot]={1,n,i};
            break;
           }
           else
           {
              if(pre[i]+1<=n)
              {
                  if(n-pre[i]>=i-1) qry[++tot]={pre[i]+1,n,i};

              }

           }

        }
        kuai=sqrt(n);
        if(n==250000&&tot>=500) printf("tot:%d\n",tot);
        sort(qry+1,qry+1+tot,cmp);
        ans=-1,cut=0;
        int l=1,r=0;
        for(int i=1;i<=tot;i++)
        {
            while( l<qry[i].l)
            {
                jian(l);
                l++;
            }
            while(l>qry[i].l)
            {
              l--;
              jia(l);
            }
            while(r<qry[i].r)
            {
              r++;
              jia(r);
            }
            while(r>qry[i].r)
            {
                jian(r);
                r--;
            }
           // if(qry[i].val==1) printf("cut:%d %d %d %d %d\n",l,r,cut,qry[i].l,qry[i].r);
          ans=max(ans,cut-qry[i].val );
        }
        if(mn==mx&&mx==1) ans=-1;
       printf("%d\n",ans);
       //pre.clear();
       //cnt.clear();
       for(int i=1;i<=n;i++) pre[i]=0;
       cnt.clear();
       ans=0,cut=0;
    }

    return 0;
}
源文件, 语言: C++17

详细

Test #1:

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

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: 76ms
memory: 18312kb

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: 67ms
memory: 20288kb

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: 85ms
memory: 18108kb

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: 0
Accepted
time: 149ms
memory: 18260kb

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:

ok 5000 numbers

Test #6:

score: -100
Time Limit Exceeded

input:

2
250000 144237
103523 38477 80037 110169 8464 110583 60349 74339 29012 8989 96955 23403 38383 12186 107503 109176 1709 31839 109579 62912 130470 26082 102718 25272 17893 55607 48053 34513 23154 136492 8313 136454 57920 60639 68601 50656 16871 101625 88777 35367 62644 80269 24346 33961 74832 62520 8...

output:

result:
English 繁體中文 简体中文

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