QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#645569#7685. Barkley II22016020736TL 158ms20216kbC++172.5kb2024-10-16 19:00:212024-10-16 19:00:23

Judging History

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

  • [2024-10-16 19:00:23]
  • 评测
  • 测评结果：TL
  • 用时：158ms
  • 内存：20216kb
查看
  • [2024-10-16 19:00:21]
  • 提交

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>=5) 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: 5ms
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: 73ms
memory: 20188kb

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: 68ms
memory: 18192kb

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: 20216kb

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: 158ms
memory: 18172kb

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:39:16 | 開源專案