#include "sequence.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
typedef long long ll;
using namespace std;
int n, g, tree[1000100], a[500100], m[500100], p1, p2;
vector<int> app[500100], v1, v2;
void update(int i, int x) {
i+=g;
tree[i]=x;
i/=2;
while(i>0) {
tree[i]=tree[2*i]+tree[2*i+1];
i/=2;
}
}
int sum(int l, int r) {
if(l>r) return 0;
l+=g;
r+=g;
int rez=0;
while(l<=r) {
if(l%2) {
rez+=tree[l];
l++;
}
if(r%2==0) {
rez+=tree[r];
r--;
}
l/=2;
r/=2;
}
return rez;
}
int solve() {
g=1;
while(g<n) g*=2;
g--;
for(int i=1; i<=n; i++) {
app[a[i]].pb(i);
m[i]=app[a[i]].size();
}
int rez=0;
for(int i=1; i<=n; i++) update(i, 1);
for(int i=1; i<=n; i++) {
if(app[i].empty()) continue;
for(int j=0; j<app[i].size(); j++) {
update(app[i][j], 0);
}
if(sum(1, n)<0) return rez;
for(int j=0; j<app[i].size(); j++) {
update(app[i][j], -1);
}
for(int j=0; j<app[i].size(); j++) {
if(v1.empty()||sum(1, v1.back()-1)<sum(1, app[i][j]-1)) v1.pb(app[i][j]);
}
for(int j=app[i].size()-1; j>=0; j--) {
if(v2.empty()||sum(1, v2.back()-1)<sum(1, app[i][j]-1)) v2.pb(app[i][j]);
}
p1=0;
p2=v2.size()-1;
while(p2>=0) {
if(v1[p1]>v2[p2]) {
p2--;
continue;
}
if(sum(v1[p1], v2[p2])<=0) {
rez=max(rez, m[v2[p2]]-m[v1[p1]]+1);
p2--;
}
else p1++;
}
v1.clear();
v2.clear();
}
return rez;
}
Compilation message
sequence.cpp: In function 'int solve()':
sequence.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int j=0; j<app[i].size(); j++) {
| ~^~~~~~~~~~~~~~
sequence.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int j=0; j<app[i].size(); j++) {
| ~^~~~~~~~~~~~~~
sequence.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int j=0; j<app[i].size(); j++) {
| ~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccBIfYf5.o: in function `main':
grader.cpp:(.text.startup+0x2a4): undefined reference to `sequence(int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status