#include <bits/stdc++.h>
#include "sequence.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5e5+5;
struct node
{
int c[2], lzy[2];
node operator +(node t)
{
node ret;
ret.c[0]=min(c[0],t.c[0]);
ret.c[1]=max(c[1],t.c[1]);
ret.lzy[0]=ret.lzy[1]=0;
return ret;
}
};
vector<int> pos[N];
node segt[4*N];
int n;
void init()
{
for(int i = 0;i<4*n;i++)
segt[i]={0,0,0,0};
}
bool cmp(int a, int b)
{
return a<b;
}
void updlzy(int pos, int siz)
{
for(int i = 0;i<2;i++)
{
int &lzy = segt[pos].lzy[i];
if(lzy)
{
segt[pos].c[i]+=lzy;
if(siz>1)
segt[pos*2].lzy[i]+=lzy,
segt[pos*2+1].lzy[i]+=lzy;
lzy=0;
}
}
}
void upd(int lb, int rb, int val1, int val2, int l = 0, int r = n, int pos = 1)
{
updlzy(pos,r-l+1);
if(rb<l||r<lb)
return;
if(lb<=l&&r<=rb)
segt[pos].lzy[0]+=val1,
segt[pos].lzy[1]+=val2,
updlzy(pos,r-l+1);
else
{
int mid = (l+r)/2;
upd(lb,rb,val1,val2,l,mid,pos*2);
upd(lb,rb,val1,val2,mid+1,r,pos*2+1);
segt[pos]=segt[pos*2]+segt[pos*2+1];
}
}
pair<int,int> get1(int lb, int rb, int l = 0, int r = n, int pos = 1)
{
if(rb<l||r<lb)
return {1e9,-1e9};
updlzy(pos,r-l+1);
if(lb<=l&&r<=rb)
return {segt[pos].c[0],segt[pos].c[1]};
int mid = (l+r)/2;
auto t1 = get1(lb,rb,l,mid,pos*2), t2 = get1(lb,rb,mid+1,r,pos*2+1);
return {min(t1.fi,t2.fi),max(t1.se,t2.se)};
}
int sequence(int n1, vector<int> a)
{
n=n1;
for(int i = 0;i<n;i++)
pos[a[i]].pb(i+1);
init();
for(int i = 1;i<=n;i++)
upd(i,n,1,1);
vector<int> mil(n+1), mxl(n+1);
for(int i = 1;i<=n;i++)
{
for(auto x:pos[i])
mil[x]=get1(0,x-1).fi;
for(auto x:pos[i])
upd(x,n,-2,-2);
for(auto x:pos[i])
mxl[x]=get1(0,x-1).se;
}
init();
for(int i = 1;i<=n;i++)
upd(i,n,1,1);
int ans = 1;
for(int i = 1;i<=n;i++)
{
for(auto x:pos[i])
upd(x,n,-2,0);
for(int j = (int)pos[i].size()-ans-1;j>=0;j--)
{
int l = pos[i][j];
while(j+ans<pos[i].size())
{
int r = pos[i][j+ans];
auto segr = get1(r,n);
int lval = segr.fi-mxl[l], rval = segr.se-mil[l];
if(lval<=0&&0<=rval)
ans++;
else
break;
}
}
for(auto x:pos[i])
upd(x,n,0,-2);
}
return ans;
}
Compilation message
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:110:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | while(j+ans<pos[i].size())
| ~~~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
5 ms |
11988 KB |
Output is correct |
6 |
Correct |
5 ms |
11988 KB |
Output is correct |
7 |
Correct |
5 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12044 KB |
Output is correct |
10 |
Correct |
5 ms |
11988 KB |
Output is correct |
11 |
Correct |
7 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
5 ms |
11988 KB |
Output is correct |
6 |
Correct |
5 ms |
11988 KB |
Output is correct |
7 |
Correct |
5 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12044 KB |
Output is correct |
10 |
Correct |
5 ms |
11988 KB |
Output is correct |
11 |
Correct |
7 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
13 |
Correct |
8 ms |
12248 KB |
Output is correct |
14 |
Correct |
8 ms |
12244 KB |
Output is correct |
15 |
Correct |
8 ms |
12220 KB |
Output is correct |
16 |
Correct |
8 ms |
12232 KB |
Output is correct |
17 |
Correct |
8 ms |
12116 KB |
Output is correct |
18 |
Correct |
9 ms |
12244 KB |
Output is correct |
19 |
Correct |
8 ms |
12116 KB |
Output is correct |
20 |
Correct |
9 ms |
12244 KB |
Output is correct |
21 |
Correct |
8 ms |
12204 KB |
Output is correct |
22 |
Correct |
8 ms |
12204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
949 ms |
61120 KB |
Output is correct |
3 |
Correct |
974 ms |
61112 KB |
Output is correct |
4 |
Correct |
918 ms |
53316 KB |
Output is correct |
5 |
Correct |
975 ms |
60168 KB |
Output is correct |
6 |
Correct |
937 ms |
60172 KB |
Output is correct |
7 |
Correct |
918 ms |
53652 KB |
Output is correct |
8 |
Correct |
902 ms |
53808 KB |
Output is correct |
9 |
Correct |
910 ms |
53332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
953 ms |
53424 KB |
Output is correct |
3 |
Correct |
1030 ms |
53340 KB |
Output is correct |
4 |
Correct |
949 ms |
53292 KB |
Output is correct |
5 |
Correct |
986 ms |
53464 KB |
Output is correct |
6 |
Correct |
974 ms |
53432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1210 ms |
66836 KB |
Output is correct |
2 |
Correct |
1262 ms |
66860 KB |
Output is correct |
3 |
Correct |
1301 ms |
66364 KB |
Output is correct |
4 |
Correct |
1230 ms |
66372 KB |
Output is correct |
5 |
Correct |
1164 ms |
62912 KB |
Output is correct |
6 |
Correct |
1143 ms |
62924 KB |
Output is correct |
7 |
Correct |
1012 ms |
61740 KB |
Output is correct |
8 |
Correct |
1000 ms |
61412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
5 ms |
11988 KB |
Output is correct |
6 |
Correct |
5 ms |
11988 KB |
Output is correct |
7 |
Correct |
5 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12044 KB |
Output is correct |
10 |
Correct |
5 ms |
11988 KB |
Output is correct |
11 |
Correct |
7 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
13 |
Correct |
8 ms |
12248 KB |
Output is correct |
14 |
Correct |
8 ms |
12244 KB |
Output is correct |
15 |
Correct |
8 ms |
12220 KB |
Output is correct |
16 |
Correct |
8 ms |
12232 KB |
Output is correct |
17 |
Correct |
8 ms |
12116 KB |
Output is correct |
18 |
Correct |
9 ms |
12244 KB |
Output is correct |
19 |
Correct |
8 ms |
12116 KB |
Output is correct |
20 |
Correct |
9 ms |
12244 KB |
Output is correct |
21 |
Correct |
8 ms |
12204 KB |
Output is correct |
22 |
Correct |
8 ms |
12204 KB |
Output is correct |
23 |
Correct |
181 ms |
19916 KB |
Output is correct |
24 |
Correct |
179 ms |
19784 KB |
Output is correct |
25 |
Correct |
189 ms |
19924 KB |
Output is correct |
26 |
Correct |
165 ms |
18992 KB |
Output is correct |
27 |
Correct |
169 ms |
18872 KB |
Output is correct |
28 |
Correct |
163 ms |
18876 KB |
Output is correct |
29 |
Correct |
151 ms |
18620 KB |
Output is correct |
30 |
Correct |
141 ms |
18712 KB |
Output is correct |
31 |
Correct |
141 ms |
18660 KB |
Output is correct |
32 |
Correct |
135 ms |
20812 KB |
Output is correct |
33 |
Correct |
178 ms |
19724 KB |
Output is correct |
34 |
Correct |
200 ms |
19736 KB |
Output is correct |
35 |
Correct |
172 ms |
19668 KB |
Output is correct |
36 |
Correct |
175 ms |
19684 KB |
Output is correct |
37 |
Correct |
175 ms |
19700 KB |
Output is correct |
38 |
Correct |
181 ms |
19680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
5 ms |
11988 KB |
Output is correct |
6 |
Correct |
5 ms |
11988 KB |
Output is correct |
7 |
Correct |
5 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12044 KB |
Output is correct |
10 |
Correct |
5 ms |
11988 KB |
Output is correct |
11 |
Correct |
7 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
13 |
Correct |
8 ms |
12248 KB |
Output is correct |
14 |
Correct |
8 ms |
12244 KB |
Output is correct |
15 |
Correct |
8 ms |
12220 KB |
Output is correct |
16 |
Correct |
8 ms |
12232 KB |
Output is correct |
17 |
Correct |
8 ms |
12116 KB |
Output is correct |
18 |
Correct |
9 ms |
12244 KB |
Output is correct |
19 |
Correct |
8 ms |
12116 KB |
Output is correct |
20 |
Correct |
9 ms |
12244 KB |
Output is correct |
21 |
Correct |
8 ms |
12204 KB |
Output is correct |
22 |
Correct |
8 ms |
12204 KB |
Output is correct |
23 |
Correct |
949 ms |
61120 KB |
Output is correct |
24 |
Correct |
974 ms |
61112 KB |
Output is correct |
25 |
Correct |
918 ms |
53316 KB |
Output is correct |
26 |
Correct |
975 ms |
60168 KB |
Output is correct |
27 |
Correct |
937 ms |
60172 KB |
Output is correct |
28 |
Correct |
918 ms |
53652 KB |
Output is correct |
29 |
Correct |
902 ms |
53808 KB |
Output is correct |
30 |
Correct |
910 ms |
53332 KB |
Output is correct |
31 |
Correct |
953 ms |
53424 KB |
Output is correct |
32 |
Correct |
1030 ms |
53340 KB |
Output is correct |
33 |
Correct |
949 ms |
53292 KB |
Output is correct |
34 |
Correct |
986 ms |
53464 KB |
Output is correct |
35 |
Correct |
974 ms |
53432 KB |
Output is correct |
36 |
Correct |
1210 ms |
66836 KB |
Output is correct |
37 |
Correct |
1262 ms |
66860 KB |
Output is correct |
38 |
Correct |
1301 ms |
66364 KB |
Output is correct |
39 |
Correct |
1230 ms |
66372 KB |
Output is correct |
40 |
Correct |
1164 ms |
62912 KB |
Output is correct |
41 |
Correct |
1143 ms |
62924 KB |
Output is correct |
42 |
Correct |
1012 ms |
61740 KB |
Output is correct |
43 |
Correct |
1000 ms |
61412 KB |
Output is correct |
44 |
Correct |
181 ms |
19916 KB |
Output is correct |
45 |
Correct |
179 ms |
19784 KB |
Output is correct |
46 |
Correct |
189 ms |
19924 KB |
Output is correct |
47 |
Correct |
165 ms |
18992 KB |
Output is correct |
48 |
Correct |
169 ms |
18872 KB |
Output is correct |
49 |
Correct |
163 ms |
18876 KB |
Output is correct |
50 |
Correct |
151 ms |
18620 KB |
Output is correct |
51 |
Correct |
141 ms |
18712 KB |
Output is correct |
52 |
Correct |
141 ms |
18660 KB |
Output is correct |
53 |
Correct |
135 ms |
20812 KB |
Output is correct |
54 |
Correct |
178 ms |
19724 KB |
Output is correct |
55 |
Correct |
200 ms |
19736 KB |
Output is correct |
56 |
Correct |
172 ms |
19668 KB |
Output is correct |
57 |
Correct |
175 ms |
19684 KB |
Output is correct |
58 |
Correct |
175 ms |
19700 KB |
Output is correct |
59 |
Correct |
181 ms |
19680 KB |
Output is correct |
60 |
Correct |
1479 ms |
60992 KB |
Output is correct |
61 |
Correct |
1475 ms |
61116 KB |
Output is correct |
62 |
Correct |
1464 ms |
61112 KB |
Output is correct |
63 |
Correct |
1314 ms |
54392 KB |
Output is correct |
64 |
Correct |
1382 ms |
54412 KB |
Output is correct |
65 |
Correct |
1445 ms |
54368 KB |
Output is correct |
66 |
Correct |
994 ms |
53348 KB |
Output is correct |
67 |
Correct |
1047 ms |
53560 KB |
Output is correct |
68 |
Correct |
979 ms |
53176 KB |
Output is correct |
69 |
Correct |
960 ms |
66900 KB |
Output is correct |
70 |
Correct |
1557 ms |
60220 KB |
Output is correct |
71 |
Correct |
1533 ms |
60000 KB |
Output is correct |
72 |
Correct |
1430 ms |
59556 KB |
Output is correct |
73 |
Correct |
1408 ms |
59972 KB |
Output is correct |
74 |
Correct |
1407 ms |
59524 KB |
Output is correct |
75 |
Correct |
1434 ms |
59924 KB |
Output is correct |