#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e6
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
in extremise(const in &a, const in&b)
{
return {min(a.f, b.f), max(a.s, b.s)};
}
void increment(int delta, in &a)
{
if(a.f == INF)
return;
a.f+=delta;
a.s+=delta;
return;
}
struct extremal_tree
{
vector<in> tree;
void init(int n)
{
tree.assign(4*n+8, {INF, -INF});
return;
}
void upd(int v, int pos, int id, int l, int r)
{
if(l == r)
{
tree[id] = extremise(tree[id], {v, v});
return;
}
int m = (l+r)/2;
if(pos <= m)
upd(v, pos, 2*id, l, m);
else
upd(v, pos, 2*id+1, m+1, r);
tree[id] = extremise(tree[2*id], tree[2*id+1]);
return;
}
in val(int ql, int qr, int id, int l, int r)
{
if(r < ql || qr < l)
return {INF, -INF};
if(ql <= l && r <= qr)
return tree[id];
int m = (l+r)/2;
in a = val(ql, qr, 2*id, l, m);
in b = val(ql, qr, 2*id+1, m+1, r);
return extremise(a, b);
}
};
struct lazy_extremal_tree
{
vector<in> tree;
vector<int> lazy;
void init(int n)
{
tree.assign(4*n+8, {INF, -INF});
lazy.assign(4*n+8, 0);
return;
}
void push(int id)
{
increment(lazy[id], tree[2*id]);
increment(lazy[id], tree[2*id+1]);
lazy[2*id]+=lazy[id];
lazy[2*id+1]+=lazy[id];
lazy[id] = 0;
return;
}
void upd(int v, int pos, int id, int l, int r)
{
if(l == r)
{
tree[id] = extremise(tree[id], {v, v});
return;
}
int m = (l+r)/2;
if(pos <= m)
upd(v, pos, 2*id, l, m);
else
upd(v, pos, 2*id+1, m+1, r);
tree[id] = extremise(tree[2*id], tree[2*id+1]);
return;
}
void upd2(int delta, int ql, int qr, int id, int l, int r)
{
if(qr < l || r < ql)
return;
if(ql <= l && r <= qr)
{
lazy[id]+=delta;
increment(delta, tree[id]);
return;
}
push(id);
int m = (l+r)/2;
upd2(delta, ql, qr, 2*id, l, m);
upd2(delta, ql, qr, 2*id+1, m+1, r);
tree[id] = extremise(tree[2*id], tree[2*id+1]);
return;
}
in val(int ql, int qr, int id, int l, int r)
{
if(r < ql || qr < l)
return {INF, -INF};
if(ql <= l && r <= qr)
return tree[id];
push(id);
int m = (l+r)/2;
in a = val(ql, qr, 2*id, l, m);
in b = val(ql, qr, 2*id+1, m+1, r);
return extremise(a, b);
}
};
vector<int> compressor;
int compress(int n)
{
return lower_bound(compressor.begin(), compressor.end(), n)-compressor.begin();
}
int solve(int n, vector<in> &ac, vector<in> &bd)//no assuming compression!
{
extremal_tree work;
compressor.clear();
work.init(2*n);
vector<int> v;
//compress begin
for(auto [a, c]: ac)
v.pb(c);
for(auto [b, d]: bd)
v.pb(d);
sort(v.begin(), v.end());
compressor.pb(v[0]);
for(int k = 1; k < v.size(); k++)
{
if(v[k] != v[k-1])
compressor.pb(v[k]);
}
//compress over
vector<in> a;
vector<in> b;
for(int i = 0; i < n; i++)
a.pb({ac[i].f, i});
for(int i = 0; i < n; i++)
b.pb({bd[i].f, i});
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int ans = -INF;
int l = 0;
for(int i = 0; i < n; i++)
{
while((l < n) && (a[l].f <= b[i].f))
{
work.upd(a[l].s, compress(ac[a[l].s].s), 1, 0, 2*n);
l++;
}
auto [m, M] = work.val(0, compress(bd[b[i].s].s), 1, 0, 2*n);
if(m != INF)
ans = max(abs(m-b[i].s), ans);
if(M != -INF)
ans = max(abs(M-b[i].s), ans);
}
return ans;
}
int sequence(int n, vector<int> a)
{
lazy_extremal_tree work;
work.init(n);
vector<int> adj[n+1];
for(int i = 1; i <= n; i++)
adj[a[i-1]].pb(i);
for(int i = 0; i <= n; i++)
work.upd(-i, i, 1, 0, n);
int ans = 0;
for(int i = 1; i <= n; i++)
{
int m = adj[i].size();
for(int k: adj[i-1])
work.upd2(+1, k, n, 1, 0, n);
for(int k: adj[i])
work.upd2(+1, k, n, 1, 0, n);
vector<int> bb(m+2);
bb[0] = 0;
bb[m+1] = n+1;
for(int j = 1; j <= m; j++)
bb[j] = adj[i][j-1];
vector<in> ac(m+1), bd(m+1);
for(int j = 0; j <= m; j++)
{
auto [a, b] = work.val(bb[j], bb[j+1]-1, 1, 0, n);
ac[j] = {a+j, j-b};
bd[j] = {b+j, j-a};
}
int ok = solve(m+1, ac, bd);
ans = max(ans, ok);
}
return ans;
}
/*vector<int> c;
int W(int l, int r, int x)
{
int cnt = 0;
for(int i = l; i <= r; i++)
cnt+=(c[i] == x);
return cnt;
}
int median_freq(int l, int r)
{
vector<int> v;
int k = r-l;
for(int i = l; i <= r; i++)
v.pb(c[i]);
sort(v.begin(), v.end());
int t = k/2;
int tp = t+k%2;
return max(W(l, r, v[t]), W(l, r, v[tp]));
}
signed main()
{
fast();
int t;
cin >> t;
while(t--)
{
c.clear();
int n;
cin >> n;
vector<int> a(n);
for(int &k: a)
{
cin >> k;
c.pb(k);
}
int ans = sequence(n, a);
int tit = 0;
for(int l = 0; l < n; l++)
{
for(int r = l; r < n; r++)
tit = max(tit, median_freq(l, r));
}
if(ans != tit)
{
cout << "WTF !!!" << endl;
printf("Fake = %d, real = %d", ans, tit);
}
assert(ans==tit);
cout << "All good!" << endl;
}
return 0;
}*/
Compilation message
sequence.cpp: In function 'int solve(int, std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
sequence.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int k = 1; k < v.size(); k++)
| ~~^~~~~~~~~~
# |
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 |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
428 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 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 |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
428 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
4 ms |
604 KB |
Output is correct |
14 |
Correct |
3 ms |
604 KB |
Output is correct |
15 |
Correct |
3 ms |
628 KB |
Output is correct |
16 |
Correct |
3 ms |
600 KB |
Output is correct |
17 |
Correct |
3 ms |
856 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
3 ms |
604 KB |
Output is correct |
20 |
Correct |
3 ms |
604 KB |
Output is correct |
21 |
Correct |
3 ms |
604 KB |
Output is correct |
22 |
Correct |
3 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
652 ms |
52812 KB |
Output is correct |
3 |
Correct |
664 ms |
52812 KB |
Output is correct |
4 |
Correct |
747 ms |
54688 KB |
Output is correct |
5 |
Correct |
662 ms |
51792 KB |
Output is correct |
6 |
Correct |
637 ms |
51788 KB |
Output is correct |
7 |
Correct |
677 ms |
44792 KB |
Output is correct |
8 |
Correct |
687 ms |
44844 KB |
Output is correct |
9 |
Correct |
753 ms |
64396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
783 ms |
82240 KB |
Output is correct |
3 |
Correct |
777 ms |
63568 KB |
Output is correct |
4 |
Correct |
783 ms |
65600 KB |
Output is correct |
5 |
Correct |
754 ms |
79104 KB |
Output is correct |
6 |
Correct |
710 ms |
73180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
804 ms |
58704 KB |
Output is correct |
2 |
Correct |
812 ms |
58428 KB |
Output is correct |
3 |
Correct |
792 ms |
57940 KB |
Output is correct |
4 |
Correct |
818 ms |
57928 KB |
Output is correct |
5 |
Correct |
734 ms |
54520 KB |
Output is correct |
6 |
Correct |
724 ms |
54612 KB |
Output is correct |
7 |
Correct |
666 ms |
53572 KB |
Output is correct |
8 |
Correct |
665 ms |
53040 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 |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
428 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
4 ms |
604 KB |
Output is correct |
14 |
Correct |
3 ms |
604 KB |
Output is correct |
15 |
Correct |
3 ms |
628 KB |
Output is correct |
16 |
Correct |
3 ms |
600 KB |
Output is correct |
17 |
Correct |
3 ms |
856 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
3 ms |
604 KB |
Output is correct |
20 |
Correct |
3 ms |
604 KB |
Output is correct |
21 |
Correct |
3 ms |
604 KB |
Output is correct |
22 |
Correct |
3 ms |
604 KB |
Output is correct |
23 |
Correct |
114 ms |
8792 KB |
Output is correct |
24 |
Correct |
117 ms |
8540 KB |
Output is correct |
25 |
Correct |
115 ms |
8540 KB |
Output is correct |
26 |
Correct |
116 ms |
7516 KB |
Output is correct |
27 |
Correct |
112 ms |
7624 KB |
Output is correct |
28 |
Correct |
127 ms |
7688 KB |
Output is correct |
29 |
Correct |
112 ms |
9124 KB |
Output is correct |
30 |
Correct |
117 ms |
9388 KB |
Output is correct |
31 |
Correct |
132 ms |
17228 KB |
Output is correct |
32 |
Correct |
97 ms |
9660 KB |
Output is correct |
33 |
Correct |
118 ms |
9808 KB |
Output is correct |
34 |
Correct |
118 ms |
9588 KB |
Output is correct |
35 |
Correct |
116 ms |
9808 KB |
Output is correct |
36 |
Correct |
117 ms |
10064 KB |
Output is correct |
37 |
Correct |
122 ms |
9812 KB |
Output is correct |
38 |
Correct |
126 ms |
9840 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 |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
428 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
4 ms |
604 KB |
Output is correct |
14 |
Correct |
3 ms |
604 KB |
Output is correct |
15 |
Correct |
3 ms |
628 KB |
Output is correct |
16 |
Correct |
3 ms |
600 KB |
Output is correct |
17 |
Correct |
3 ms |
856 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
3 ms |
604 KB |
Output is correct |
20 |
Correct |
3 ms |
604 KB |
Output is correct |
21 |
Correct |
3 ms |
604 KB |
Output is correct |
22 |
Correct |
3 ms |
604 KB |
Output is correct |
23 |
Correct |
652 ms |
52812 KB |
Output is correct |
24 |
Correct |
664 ms |
52812 KB |
Output is correct |
25 |
Correct |
747 ms |
54688 KB |
Output is correct |
26 |
Correct |
662 ms |
51792 KB |
Output is correct |
27 |
Correct |
637 ms |
51788 KB |
Output is correct |
28 |
Correct |
677 ms |
44792 KB |
Output is correct |
29 |
Correct |
687 ms |
44844 KB |
Output is correct |
30 |
Correct |
753 ms |
64396 KB |
Output is correct |
31 |
Correct |
783 ms |
82240 KB |
Output is correct |
32 |
Correct |
777 ms |
63568 KB |
Output is correct |
33 |
Correct |
783 ms |
65600 KB |
Output is correct |
34 |
Correct |
754 ms |
79104 KB |
Output is correct |
35 |
Correct |
710 ms |
73180 KB |
Output is correct |
36 |
Correct |
804 ms |
58704 KB |
Output is correct |
37 |
Correct |
812 ms |
58428 KB |
Output is correct |
38 |
Correct |
792 ms |
57940 KB |
Output is correct |
39 |
Correct |
818 ms |
57928 KB |
Output is correct |
40 |
Correct |
734 ms |
54520 KB |
Output is correct |
41 |
Correct |
724 ms |
54612 KB |
Output is correct |
42 |
Correct |
666 ms |
53572 KB |
Output is correct |
43 |
Correct |
665 ms |
53040 KB |
Output is correct |
44 |
Correct |
114 ms |
8792 KB |
Output is correct |
45 |
Correct |
117 ms |
8540 KB |
Output is correct |
46 |
Correct |
115 ms |
8540 KB |
Output is correct |
47 |
Correct |
116 ms |
7516 KB |
Output is correct |
48 |
Correct |
112 ms |
7624 KB |
Output is correct |
49 |
Correct |
127 ms |
7688 KB |
Output is correct |
50 |
Correct |
112 ms |
9124 KB |
Output is correct |
51 |
Correct |
117 ms |
9388 KB |
Output is correct |
52 |
Correct |
132 ms |
17228 KB |
Output is correct |
53 |
Correct |
97 ms |
9660 KB |
Output is correct |
54 |
Correct |
118 ms |
9808 KB |
Output is correct |
55 |
Correct |
118 ms |
9588 KB |
Output is correct |
56 |
Correct |
116 ms |
9808 KB |
Output is correct |
57 |
Correct |
117 ms |
10064 KB |
Output is correct |
58 |
Correct |
122 ms |
9812 KB |
Output is correct |
59 |
Correct |
126 ms |
9840 KB |
Output is correct |
60 |
Correct |
904 ms |
52812 KB |
Output is correct |
61 |
Correct |
873 ms |
52800 KB |
Output is correct |
62 |
Correct |
880 ms |
52816 KB |
Output is correct |
63 |
Correct |
799 ms |
44880 KB |
Output is correct |
64 |
Correct |
808 ms |
44748 KB |
Output is correct |
65 |
Correct |
802 ms |
44748 KB |
Output is correct |
66 |
Correct |
764 ms |
55068 KB |
Output is correct |
67 |
Correct |
768 ms |
54820 KB |
Output is correct |
68 |
Correct |
773 ms |
103832 KB |
Output is correct |
69 |
Correct |
666 ms |
58536 KB |
Output is correct |
70 |
Correct |
895 ms |
58804 KB |
Output is correct |
71 |
Correct |
881 ms |
60024 KB |
Output is correct |
72 |
Correct |
841 ms |
60624 KB |
Output is correct |
73 |
Correct |
869 ms |
60392 KB |
Output is correct |
74 |
Correct |
848 ms |
62272 KB |
Output is correct |
75 |
Correct |
858 ms |
60044 KB |
Output is correct |