QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#252976#7685. Barkley IIucup-team1321#TL 139ms10948kbC++231.2kb2023-11-16 16:05:012023-11-16 16:05:02

Judging History

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

  • [2023-11-16 16:05:02]
  • 评测
  • 测评结果：TL
  • 用时：139ms
  • 内存：10948kb
查看
  • [2023-11-16 16:05:01]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=500005;
int n,m;
int a[N];
int pos[N];
void solve()
{
  cin>>n>>m;
  for(int i=1;i<=n;i++)
    cin>>a[i];
  vector<int> t(n*2);
  auto upd=[&](int x,int v){
    x+=n;
    while(x){
      t[x]+=v;
      x/=2;
    }
    return;
  };
  auto query=[&](int l,int r){
    int ans=0;
    for(l+=n,r+=n;l<r;l/=2,r/=2){
      if(l&1)ans+=t[l++];
      if(r&1)ans+=t[--r];
    }
    return ans;
  };
  for(int i=1;i<=n;i++)pos[a[i]]=0;
  int ans=-1;
  for(int r=1;r<=n;r++)
  {
    int p=r;
    if(pos[a[r]])upd(pos[a[r]]-1,-1);
    pos[a[r]]=r;
    upd(r-1,1);
    for(int i=1;i<=m+1;i++)
    {
      int l=pos[i]+1;
      if(l<=p)
      {
        ans=max(ans,query(l-1,r)-i);
//        cerr<<"find"<<l<<" "<<r<<" "<<i<<"\n";
//        cerr<<query(l-1,r)<<"\n";
        //...
      }
      if(pos[i]==0) break;
      p=min(p,pos[i]);
    }
  }
  cout << ans << "\n";
  for(int i=1;i<=n;i++)pos[a[i]]=0;
  return;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr),cout.tie(nullptr);
  int T;
  cin>>T;
  while(T--)
    solve();
  return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5668kb

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: 34ms
memory: 5656kb

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: 33ms
memory: 5648kb

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: 34ms
memory: 5676kb

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: 41ms
memory: 5588kb

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: 0
Accepted
time: 100ms
memory: 9340kb

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:

118705
195099

result:

ok 2 number(s): "118705 195099"

Test #7:

score: 0
Accepted
time: 97ms
memory: 10796kb

input:

1
500000 500000
166333 42890 491246 340568 331305 268296 201428 53022 200493 362616 82079 492836 402998 214609 161141 471977 378791 107806 182516 265636 468917 104158 490409 221339 116329 325539 49370 262861 37122 78932 236317 431273 76912 177034 393086 455348 481306 290838 435357 444359 465017 1894...

output:

315937

result:

ok 1 number(s): "315937"

Test #8:

score: 0
Accepted
time: 35ms
memory: 5584kb

input:

50000
10 359848
3 7 9 4 5 2 8 10 1 6
10 418109
5 3 9 4 8 10 6 2 1 7
10 218272
3 4 6 5 2 1 9 10 8 7
10 35311
10 8 7 3 9 2 1 6 5 4
10 82600
4 10 6 9 7 5 2 1 3 8
10 265069
10 5 3 2 9 4 1 8 7 6
10 105624
7 2 3 1 9 10 5 8 4 6
10 440218
10 5 3 6 9 4 1 8 7 2
10 444968
1 2 4 7 5 10 3 9 8 6
10 199453
7 10 1 ...

output:

7
7
6
5
6
5
6
7
8
6
7
4
7
5
7
6
8
8
6
6
7
8
5
7
6
6
5
6
7
4
6
6
6
5
7
7
8
6
7
8
8
7
5
4
6
5
5
8
8
7
7
7
6
5
7
6
7
7
5
7
7
6
8
8
5
7
5
7
7
5
7
6
8
6
6
5
8
7
7
8
7
7
5
5
8
8
7
6
8
5
5
7
8
6
5
8
4
7
5
7
6
7
5
7
7
6
8
7
7
7
8
5
6
7
7
6
8
7
7
7
6
7
6
6
5
6
7
7
7
7
6
5
6
5
8
8
6
7
7
5
7
8
5
6
4
8
7
6
7
8
...

result:

ok 50000 numbers

Test #9:

score: 0
Accepted
time: 35ms
memory: 5568kb

input:

100000
5 5277
5 4 1 3 2
5 190469
3 1 4 5 2
5 238117
3 1 2 4 5
5 173164
4 5 1 3 2
5 21126
2 1 4 5 3
5 257869
2 4 3 1 5
5 58430
5 3 1 2 4
5 280066
4 2 3 5 1
5 406541
4 2 5 3 1
5 462388
1 2 4 3 5
5 140796
3 4 1 2 5
5 290933
4 1 5 2 3
5 69105
1 3 5 4 2
5 379211
2 5 1 4 3
5 337951
4 1 3 2 5
5 266310
4 2 ...

output:

2
2
2
2
2
2
1
3
3
3
1
2
3
2
2
2
1
3
1
3
1
2
2
3
3
1
2
3
2
3
3
3
3
2
2
3
3
2
2
3
2
3
2
3
3
3
1
3
3
2
2
1
3
2
3
2
2
2
3
3
2
2
2
3
3
3
2
2
2
2
3
2
3
2
3
2
2
3
1
2
2
3
2
2
2
2
3
2
2
2
2
3
2
3
1
2
1
3
2
3
2
3
2
3
2
2
3
2
3
2
3
2
3
2
2
2
2
3
2
2
2
3
2
3
1
2
3
3
2
2
3
2
3
3
3
3
2
3
3
3
3
1
2
2
2
2
2
1
2
3
...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 39ms
memory: 5672kb

input:

25000
20 82509
9 14 10 3 17 20 1 11 4 6 19 18 13 5 8 15 12 2 16 7
20 182141
2 1 18 12 3 19 5 10 6 9 17 13 8 16 7 14 20 15 11 4
20 442101
3 9 12 4 15 20 10 5 1 8 13 6 17 2 14 19 7 11 18 16
20 394185
18 10 19 3 5 1 14 13 9 2 12 4 16 15 8 20 17 7 6 11
20 166980
20 17 16 10 5 14 6 11 3 2 9 12 4 1 13 15 ...

output:

15
17
16
13
12
16
13
16
17
17
16
17
17
17
13
18
14
16
18
16
15
16
16
17
17
12
15
15
17
17
14
16
14
17
17
16
18
16
16
16
15
16
16
16
18
12
17
15
16
15
16
14
18
15
15
15
14
18
13
18
15
17
17
14
16
15
15
15
12
13
15
16
14
14
18
15
15
13
14
16
18
16
13
17
16
16
15
18
12
13
17
13
16
14
17
15
18
15
12
14
...

result:

ok 25000 numbers

Test #11:

score: 0
Accepted
time: 48ms
memory: 3632kb

input:

5000
100 306161
12 73 87 36 97 31 46 98 75 48 63 53 3 80 93 22 66 92 61 84 18 54 40 64 45 95 9 13 26 59 23 30 70 51 72 7 2 78 5 10 6 82 8 56 27 24 76 16 25 41 90 81 58 94 37 17 4 55 32 89 43 42 100 62 39 49 67 14 86 99 20 38 71 60 34 50 11 74 88 15 52 44 83 77 69 28 65 79 68 29 1 91 35 57 33 21 47 8...

output:

89
95
86
86
90
90
84
90
88
91
93
90
93
92
95
90
95
97
88
92
88
93
88
91
92
90
87
95
89
90
92
89
93
96
95
95
96
93
91
95
93
88
89
91
90
88
94
93
82
90
92
94
88
95
88
85
93
94
96
94
89
96
90
91
91
88
90
90
83
90
87
95
94
92
85
92
93
91
85
92
88
90
96
97
90
83
88
92
89
97
94
97
94
93
91
89
88
93
84
92
...

result:

ok 5000 numbers

Test #12:

score: 0
Accepted
time: 112ms
memory: 8460kb

input:

2
250000 428579
248668 155599 194637 33958 195350 111388 73108 122013 20865 138324 35552 86373 81856 197773 29494 225040 222921 2274 216341 152306 218039 235001 169433 26562 11648 164657 233867 233011 158427 165182 113806 107090 146738 221989 186397 131670 111042 204004 65140 159348 99198 190164 856...

output:

249454
249551

result:

ok 2 number(s): "249454 249551"

Test #13:

score: 0
Accepted
time: 139ms
memory: 10948kb

input:

1
500000 500000
200323 10145 176452 387759 57674 376309 106257 281569 154190 13537 419396 294390 286088 241280 367901 91976 300287 310956 58027 491859 430847 227221 181181 26524 476739 25343 83009 388661 459213 378505 113707 115770 155346 202887 405077 361306 201954 16016 485924 464238 343243 236494...

output:

499422

result:

ok 1 number(s): "499422"

Test #14:

score: -100
Time Limit Exceeded

input:

1
500000 500000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-05 10:16:42 | OpenSource Project