# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
750267 |
2023-05-29T08:50:45 Z |
blue |
Sequence (APIO23_sequence) |
C++17 |
|
1271 ms |
127472 KB |
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define sz(x) int(x.size())
const int inf = 10'000'000;
const int mx = 500'000;
int N;
vi A;
vi V;
struct sdata
{
int sm = 0;
int prefmin = 0;
int prefmax = 0;
int suffmin = 0;
int suffmax = 0;
sdata()
{
;
}
sdata(int V)
{
sm = V;
prefmin = min(V, 0);
suffmin = min(V, 0);
prefmax = max(V, 0);
suffmax = max(V, 0);
}
};
sdata combine(sdata a, sdata b)
{
sdata res;
res.sm = a.sm + b.sm;
res.prefmin = min(a.prefmin, a.sm + b.prefmin);
res.prefmax = max(a.prefmax, a.sm + b.prefmax);
res.suffmin = min(b.suffmin, b.sm + a.suffmin);
res.suffmax = max(b.suffmax, b.sm + a.suffmax);
return res;
}
struct segtree
{
int l;
int r;
sdata v;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r)
return;
int m = (l + r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void update(int I, int V)
{
if(l == r)
{
v = sdata(V);
}
else
{
if(I <= (l+r)/2)
left->update(I, V);
else
right->update(I, V);
v = combine(left->v, right->v);
}
}
sdata query(int L, int R)
{
if(R < L)
return sdata(0);
if(L <= l && r <= R)
return v;
else if(R <= (l+r)/2)
return left->query(L, R);
else if(L >= (l+r)/2 + 1)
return right->query(L, R);
else
return combine(left->query(L, R), right->query(L, R));
}
};
vvi val;
int sequence(int N_, vi A_)
{
N = N_;
A = vi{0};
for(int a : A_)
A.push_back(a);
vi lst[1+N];
for(int i = 1; i <= N; i++)
lst[A[i]].push_back(i);
segtree S(1, N);
for(int i = 1; i <= N; i++)
S.update(i, +1);
int res = 0;
for(int v = 1; v <= N; v++)
{
for(int i : lst[v])
S.update(i, 0);
for(int i : lst[v-1])
S.update(i, -1);
if(lst[v].empty())
continue;
// cerr << "\n\n\n";
// cerr << v << " : ";
// for(int u : lst[v])
// cerr << u << ' ';
// cerr << '\n';
// for(int i = 1; i <= N; i++)
// cerr << S.query(i, i).sm << ' ';
// cerr << '\n';
int H;
vi Z{0};
for(int i : lst[v])
Z.push_back(i);
H = sz(Z) - 1;
vector<sdata> dv(1 + H);
dv[0] = S.query(1, Z[1] - 1);
for(int i = 1; i < H; i++)
{
// cerr << i << " query = " << Z[i]+1 << ' ' << Z[i+1] - 1 << '\n';
dv[i] = S.query(Z[i] + 1, Z[i+1] - 1);
}
dv[H] = S.query(Z[H] + 1, N);
vi totsum(1 + H);
totsum[0] = 0;
for(int i = 1; i <= H; i++)
totsum[i] = totsum[i-1] + dv[i-1].sm;
/*
[1] l - 1 - totsum[l] + dv[l-1].suffmin <= r - dv[r].prefmin - totsum[r]
[2] l - 1 + totsum[l] - dv[l-1].suffmax <= r + totsum[r] + dv[r].prefmax
*/
// cerr << "hello!\n";
val = vvi(4, vi(1+H));
for(int i = 1; i <= H; i++)
{
val[0][i] = i - 1 - totsum[i] + dv[i-1].suffmin;
val[1][i] = i - dv[i].prefmin - totsum[i];
val[2][i] = i - 1 + totsum[i] - dv[i-1].suffmax;
val[3][i] = i + totsum[i] + dv[i].prefmax;
}
vpii lst1;
vpii lst2;
// cerr << "A\n";
for(int i = 1; i <= H; i++)
{
lst1.push_back({val[0][i], -i});
lst1.push_back({val[1][i], +i});
lst2.push_back({val[2][i], -i});
lst2.push_back({val[3][i], +i});
}
vi updpos(1+H), querpos(1+H);
sort(lst1.begin(), lst1.end());
sort(lst2.begin(), lst2.end());
// cerr << "B\n";
for(int i = 1; i <= sz(lst1); i++)
{
if(lst1[i-1].second < 0)
updpos[-lst1[i-1].second] = i;
else
querpos[lst1[i-1].second] = i;
}
vi bit(1+2*H, 1'000'000'000);
// cerr << "C\n";
for(pii pp : lst2)
{
if(pp.second < 0)
{
int i = -pp.second;
//update
for(int j = updpos[i]; j <= 2*H; j += j&-j)
bit[j] = min(bit[j], i);
}
else
{
int i = pp.second;
//query
for(int j = querpos[i]; j >= 1; j -= j&-j)
res = max(res, i - bit[j] + 1);
}
}
// cerr << "current res = " << res << '\n';
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
4 ms |
596 KB |
Output is correct |
14 |
Correct |
3 ms |
596 KB |
Output is correct |
15 |
Correct |
2 ms |
596 KB |
Output is correct |
16 |
Correct |
3 ms |
596 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
3 ms |
596 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
21 |
Correct |
3 ms |
596 KB |
Output is correct |
22 |
Correct |
3 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
682 ms |
90468 KB |
Output is correct |
3 |
Correct |
784 ms |
90476 KB |
Output is correct |
4 |
Correct |
443 ms |
95016 KB |
Output is correct |
5 |
Correct |
719 ms |
89520 KB |
Output is correct |
6 |
Correct |
665 ms |
89408 KB |
Output is correct |
7 |
Correct |
426 ms |
84152 KB |
Output is correct |
8 |
Correct |
445 ms |
84388 KB |
Output is correct |
9 |
Correct |
497 ms |
101696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
571 ms |
110256 KB |
Output is correct |
3 |
Correct |
583 ms |
104444 KB |
Output is correct |
4 |
Correct |
580 ms |
104480 KB |
Output is correct |
5 |
Correct |
597 ms |
118848 KB |
Output is correct |
6 |
Correct |
566 ms |
107780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1255 ms |
96188 KB |
Output is correct |
2 |
Correct |
1205 ms |
96172 KB |
Output is correct |
3 |
Correct |
1226 ms |
95620 KB |
Output is correct |
4 |
Correct |
1133 ms |
95556 KB |
Output is correct |
5 |
Correct |
892 ms |
92284 KB |
Output is correct |
6 |
Correct |
954 ms |
92352 KB |
Output is correct |
7 |
Correct |
735 ms |
91084 KB |
Output is correct |
8 |
Correct |
738 ms |
90768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
4 ms |
596 KB |
Output is correct |
14 |
Correct |
3 ms |
596 KB |
Output is correct |
15 |
Correct |
2 ms |
596 KB |
Output is correct |
16 |
Correct |
3 ms |
596 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
3 ms |
596 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
21 |
Correct |
3 ms |
596 KB |
Output is correct |
22 |
Correct |
3 ms |
596 KB |
Output is correct |
23 |
Correct |
169 ms |
14728 KB |
Output is correct |
24 |
Correct |
184 ms |
14656 KB |
Output is correct |
25 |
Correct |
188 ms |
14740 KB |
Output is correct |
26 |
Correct |
148 ms |
13776 KB |
Output is correct |
27 |
Correct |
130 ms |
13804 KB |
Output is correct |
28 |
Correct |
144 ms |
13724 KB |
Output is correct |
29 |
Correct |
99 ms |
15360 KB |
Output is correct |
30 |
Correct |
99 ms |
15296 KB |
Output is correct |
31 |
Correct |
76 ms |
20816 KB |
Output is correct |
32 |
Correct |
122 ms |
15648 KB |
Output is correct |
33 |
Correct |
170 ms |
15584 KB |
Output is correct |
34 |
Correct |
159 ms |
15444 KB |
Output is correct |
35 |
Correct |
146 ms |
15824 KB |
Output is correct |
36 |
Correct |
149 ms |
15812 KB |
Output is correct |
37 |
Correct |
139 ms |
15664 KB |
Output is correct |
38 |
Correct |
151 ms |
15704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
4 ms |
596 KB |
Output is correct |
14 |
Correct |
3 ms |
596 KB |
Output is correct |
15 |
Correct |
2 ms |
596 KB |
Output is correct |
16 |
Correct |
3 ms |
596 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
3 ms |
596 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
21 |
Correct |
3 ms |
596 KB |
Output is correct |
22 |
Correct |
3 ms |
596 KB |
Output is correct |
23 |
Correct |
682 ms |
90468 KB |
Output is correct |
24 |
Correct |
784 ms |
90476 KB |
Output is correct |
25 |
Correct |
443 ms |
95016 KB |
Output is correct |
26 |
Correct |
719 ms |
89520 KB |
Output is correct |
27 |
Correct |
665 ms |
89408 KB |
Output is correct |
28 |
Correct |
426 ms |
84152 KB |
Output is correct |
29 |
Correct |
445 ms |
84388 KB |
Output is correct |
30 |
Correct |
497 ms |
101696 KB |
Output is correct |
31 |
Correct |
571 ms |
110256 KB |
Output is correct |
32 |
Correct |
583 ms |
104444 KB |
Output is correct |
33 |
Correct |
580 ms |
104480 KB |
Output is correct |
34 |
Correct |
597 ms |
118848 KB |
Output is correct |
35 |
Correct |
566 ms |
107780 KB |
Output is correct |
36 |
Correct |
1255 ms |
96188 KB |
Output is correct |
37 |
Correct |
1205 ms |
96172 KB |
Output is correct |
38 |
Correct |
1226 ms |
95620 KB |
Output is correct |
39 |
Correct |
1133 ms |
95556 KB |
Output is correct |
40 |
Correct |
892 ms |
92284 KB |
Output is correct |
41 |
Correct |
954 ms |
92352 KB |
Output is correct |
42 |
Correct |
735 ms |
91084 KB |
Output is correct |
43 |
Correct |
738 ms |
90768 KB |
Output is correct |
44 |
Correct |
169 ms |
14728 KB |
Output is correct |
45 |
Correct |
184 ms |
14656 KB |
Output is correct |
46 |
Correct |
188 ms |
14740 KB |
Output is correct |
47 |
Correct |
148 ms |
13776 KB |
Output is correct |
48 |
Correct |
130 ms |
13804 KB |
Output is correct |
49 |
Correct |
144 ms |
13724 KB |
Output is correct |
50 |
Correct |
99 ms |
15360 KB |
Output is correct |
51 |
Correct |
99 ms |
15296 KB |
Output is correct |
52 |
Correct |
76 ms |
20816 KB |
Output is correct |
53 |
Correct |
122 ms |
15648 KB |
Output is correct |
54 |
Correct |
170 ms |
15584 KB |
Output is correct |
55 |
Correct |
159 ms |
15444 KB |
Output is correct |
56 |
Correct |
146 ms |
15824 KB |
Output is correct |
57 |
Correct |
149 ms |
15812 KB |
Output is correct |
58 |
Correct |
139 ms |
15664 KB |
Output is correct |
59 |
Correct |
151 ms |
15704 KB |
Output is correct |
60 |
Correct |
1270 ms |
90552 KB |
Output is correct |
61 |
Correct |
1271 ms |
90544 KB |
Output is correct |
62 |
Correct |
1260 ms |
90504 KB |
Output is correct |
63 |
Correct |
978 ms |
83524 KB |
Output is correct |
64 |
Correct |
942 ms |
83516 KB |
Output is correct |
65 |
Correct |
954 ms |
83648 KB |
Output is correct |
66 |
Correct |
549 ms |
95352 KB |
Output is correct |
67 |
Correct |
546 ms |
95120 KB |
Output is correct |
68 |
Correct |
433 ms |
127472 KB |
Output is correct |
69 |
Correct |
721 ms |
96196 KB |
Output is correct |
70 |
Correct |
1148 ms |
95304 KB |
Output is correct |
71 |
Correct |
1189 ms |
97284 KB |
Output is correct |
72 |
Correct |
1098 ms |
97464 KB |
Output is correct |
73 |
Correct |
1166 ms |
97248 KB |
Output is correct |
74 |
Correct |
1080 ms |
97912 KB |
Output is correct |
75 |
Correct |
1114 ms |
97336 KB |
Output is correct |