#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) maL2[s]=-query(0,n-1,1,0,s-1).L_min;
if (s<n-1) maR2[s]=-query(0,n-1,1,s+1,n-1).R_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) maL1[s]=query(0,n-1,1,0,s-1).L_max;
if (s<n-1) maL2[s]=query(0,n-1,1,s+1,n-1).R_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 && maL1[group[i][mid]]+maR1[group[i][j]]+c+ss<0) can=false;
if (c-ss<0 && maL2[group[i][mid]]+maR2[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:67:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int j=0; j<group[i].size(); ++j) {
| ~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
12096 KB |
Output is correct |
4 |
Incorrect |
6 ms |
11996 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
12096 KB |
Output is correct |
4 |
Incorrect |
6 ms |
11996 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
1288 ms |
56152 KB |
Output is correct |
3 |
Correct |
1303 ms |
56080 KB |
Output is correct |
4 |
Correct |
1230 ms |
48360 KB |
Output is correct |
5 |
Correct |
1281 ms |
55256 KB |
Output is correct |
6 |
Correct |
1260 ms |
55176 KB |
Output is correct |
7 |
Correct |
1257 ms |
48904 KB |
Output is correct |
8 |
Incorrect |
1235 ms |
48908 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
1246 ms |
48504 KB |
Output is correct |
3 |
Incorrect |
1254 ms |
48404 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1479 ms |
61916 KB |
Output is correct |
2 |
Correct |
1507 ms |
61956 KB |
Output is correct |
3 |
Correct |
1490 ms |
61412 KB |
Output is correct |
4 |
Correct |
1479 ms |
61420 KB |
Output is correct |
5 |
Incorrect |
1365 ms |
58012 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
12096 KB |
Output is correct |
4 |
Incorrect |
6 ms |
11996 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
12096 KB |
Output is correct |
4 |
Incorrect |
6 ms |
11996 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |