#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=2e3+5;
int n, a[nx], res;
struct persist
{
struct node
{
int f;
node *l, *r;
node(int f): f(f), l(0), r(0){}
};
typedef node* pnode;
pnode rt[nx];
void build(int l, int r, pnode &k)
{
k=new node(0);
if (l==r) return;
int md=(l+r)/2;
build(l, md, k->l);
build(md+1, r, k->r);
}
void update(int l, int r, pnode &k, pnode t, int idx)
{
k=new node(*t);
if (l==r) return k->f++, void();
int md=(l+r)/2;
if (idx<=md) update(l, md, k->l, t->l, idx);
else update(md+1, r, k->r, t->r, idx);
k->f=k->l->f+k->r->f;
}
int query(int l, int r, pnode k, pnode t, int key)
{
if (l==r) return k->f-t->f;
int md=(l+r)/2;
if ((k->l->f-t->l->f)>=key) return query(l, md, k->l, t->l, key);
else return query(md+1, r, k->r, t->r, key-(k->l->f-t->l->f));
}
} s;
int sequence(int N, std::vector<int> A) {
n=N;
for (int i=1; i<=n; i++) a[i]=A[i-1];
s.build(1, n, s.rt[0]);
for (int i=1; i<=n; i++) s.update(1, n, s.rt[i], s.rt[i-1], a[i]);
for (int i=1; i<=n; i++)
{
for (int j=1; j<=i; j++)
{
if ((i-j+1)%2) res=max(res, s.query(1, n, s.rt[i], s.rt[j-1], ((i-j+2)/2)));
else res=max({res, s.query(1, n, s.rt[i], s.rt[j-1], (i-j+1)/2), s.query(1, n, s.rt[i], s.rt[j-1], (i-j+1/2)+1)});
}
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
472 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
472 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
63 ms |
1116 KB |
Output is correct |
14 |
Correct |
66 ms |
1320 KB |
Output is correct |
15 |
Correct |
47 ms |
1116 KB |
Output is correct |
16 |
Correct |
47 ms |
1116 KB |
Output is correct |
17 |
Incorrect |
43 ms |
1112 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Runtime error |
44 ms |
8492 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Runtime error |
38 ms |
8284 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
44 ms |
8288 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
472 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
63 ms |
1116 KB |
Output is correct |
14 |
Correct |
66 ms |
1320 KB |
Output is correct |
15 |
Correct |
47 ms |
1116 KB |
Output is correct |
16 |
Correct |
47 ms |
1116 KB |
Output is correct |
17 |
Incorrect |
43 ms |
1112 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
472 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
63 ms |
1116 KB |
Output is correct |
14 |
Correct |
66 ms |
1320 KB |
Output is correct |
15 |
Correct |
47 ms |
1116 KB |
Output is correct |
16 |
Correct |
47 ms |
1116 KB |
Output is correct |
17 |
Incorrect |
43 ms |
1112 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |