#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int sum,L_max,L_min,R_max,R_min;
} s[1<<21];
node merge(node a, node b) {
node res;
res.sum=a.sum+b.sum;
res.R_max=max(b.R_max,a.R_max+b.sum);
res.R_min=min(b.R_min,a.R_min+b.sum);
res.L_max=max(a.L_max,b.L_max+a.sum);
res.L_min=min(a.L_min,b.L_min+a.sum);
return res;
}
int n,a[5000001];
void update(int l, int r, int idx, int x, int val) {
if (x>r || x<l) return;
if (l==r) {
if (val==1) s[idx]={1,1,0,1,0};
else if (val==-1) s[idx]={-1,0,-1,0,-1};
else s[idx]={0,0,0,0,0};
} else {
int mid=(l+r)/2;
update(l,mid,2*idx,x,val);
update(mid+1,r,2*idx+1,x,val);
s[idx]=merge(s[2*idx],s[2*idx+1]);
}
}
node query(int l, int r, int idx, int x, int y) {
if (x>r || y<l) return {0,0,0,0,0};
if (x<=l && r<=y) return s[idx];
int mid=(l+r)/2;
return merge(query(l,mid,2*idx,x,y),query(mid+1,r,2*idx+1,x,y));
}
vector<int> group[500001];
int maL1[500001],maL2[500001],maR1[500001],maR2[500001],sum[500001];
int sequence(int N, vector<int> A) {
n=N;
for (int i=0; i<n; ++i) a[i]=A[i], group[a[i]].push_back(i);
for (int i=0; i<n; ++i) update(0,n-1,1,i,-1);
for (int i=0; i<n; ++i) {
for (auto s : group[i]) {
if (s>0) maR2[s]=-query(0,n-1,1,0,s-1).R_min;
if (s<n-1) maL2[s]=-query(0,n-1,1,s+1,n-1).L_min;
}
for (auto s : group[i]) update(0,n-1,1,s,0);
for (auto s : group[i]) sum[s]=query(0,n-1,1,0,s).sum;
for (auto s : group[i]) update(0,n-1,1,s,1);
for (auto s : group[i]) {
if (s>0) maR1[s]=query(0,n-1,1,0,s-1).R_max;
if (s<n-1) maL2[s]=query(0,n-1,1,s+1,n-1).L_max;
}
}
int ans=0;
for (int i=0; i<n; ++i) {
for (int j=0; j<group[i].size(); ++j) {
int l=0,r=j;
while (l<r) {
int mid=(l+r)/2;
bool can=true;
//is it possible to chose sequence at least from mid to j
int ss=sum[group[i][j]]-sum[group[i][mid]], c=j-mid+1;
if (c+ss<0 && maR1[group[i][mid]]+maL1[group[i][j]]+c+ss<0) can=false;
if (c-ss<0 && maR2[group[i][mid]]+maL2[group[i][j]]+c-ss<0) can=false;
if (can) r=mid;
else l=mid+1;
}
ans=max(ans,j-l+1);
}
}
return ans;
}
Compilation message
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:68:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int j=0; j<group[i].size(); ++j) {
| ~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
8 ms |
12092 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
7 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12072 KB |
Output is correct |
10 |
Correct |
6 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
6 ms |
12084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
8 ms |
12092 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
7 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12072 KB |
Output is correct |
10 |
Correct |
6 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
6 ms |
12084 KB |
Output is correct |
13 |
Correct |
11 ms |
12244 KB |
Output is correct |
14 |
Correct |
9 ms |
12244 KB |
Output is correct |
15 |
Correct |
9 ms |
12244 KB |
Output is correct |
16 |
Correct |
11 ms |
12244 KB |
Output is correct |
17 |
Correct |
8 ms |
12240 KB |
Output is correct |
18 |
Correct |
9 ms |
12244 KB |
Output is correct |
19 |
Correct |
9 ms |
12180 KB |
Output is correct |
20 |
Correct |
9 ms |
12244 KB |
Output is correct |
21 |
Incorrect |
8 ms |
12244 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
1279 ms |
56100 KB |
Output is correct |
3 |
Correct |
1264 ms |
56208 KB |
Output is correct |
4 |
Correct |
1282 ms |
48356 KB |
Output is correct |
5 |
Correct |
1275 ms |
55244 KB |
Output is correct |
6 |
Correct |
1294 ms |
55144 KB |
Output is correct |
7 |
Correct |
1233 ms |
48788 KB |
Output is correct |
8 |
Incorrect |
1256 ms |
48868 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
1250 ms |
48516 KB |
Output is correct |
3 |
Correct |
1256 ms |
48352 KB |
Output is correct |
4 |
Correct |
1273 ms |
48320 KB |
Output is correct |
5 |
Correct |
1263 ms |
48528 KB |
Output is correct |
6 |
Incorrect |
1284 ms |
48372 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1497 ms |
61952 KB |
Output is correct |
2 |
Correct |
1477 ms |
62088 KB |
Output is correct |
3 |
Correct |
1478 ms |
61372 KB |
Output is correct |
4 |
Correct |
1503 ms |
61312 KB |
Output is correct |
5 |
Incorrect |
1378 ms |
58136 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
8 ms |
12092 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
7 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12072 KB |
Output is correct |
10 |
Correct |
6 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
6 ms |
12084 KB |
Output is correct |
13 |
Correct |
11 ms |
12244 KB |
Output is correct |
14 |
Correct |
9 ms |
12244 KB |
Output is correct |
15 |
Correct |
9 ms |
12244 KB |
Output is correct |
16 |
Correct |
11 ms |
12244 KB |
Output is correct |
17 |
Correct |
8 ms |
12240 KB |
Output is correct |
18 |
Correct |
9 ms |
12244 KB |
Output is correct |
19 |
Correct |
9 ms |
12180 KB |
Output is correct |
20 |
Correct |
9 ms |
12244 KB |
Output is correct |
21 |
Incorrect |
8 ms |
12244 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
8 ms |
12092 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
7 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12072 KB |
Output is correct |
10 |
Correct |
6 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
6 ms |
12084 KB |
Output is correct |
13 |
Correct |
11 ms |
12244 KB |
Output is correct |
14 |
Correct |
9 ms |
12244 KB |
Output is correct |
15 |
Correct |
9 ms |
12244 KB |
Output is correct |
16 |
Correct |
11 ms |
12244 KB |
Output is correct |
17 |
Correct |
8 ms |
12240 KB |
Output is correct |
18 |
Correct |
9 ms |
12244 KB |
Output is correct |
19 |
Correct |
9 ms |
12180 KB |
Output is correct |
20 |
Correct |
9 ms |
12244 KB |
Output is correct |
21 |
Incorrect |
8 ms |
12244 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |