#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define ll long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
const int maxn = 1e6 +10 , N = 1e5 +1 , maxq = 202 , inf = 1e9 , maxk = 2022 , mod =1e9+7 ;
int a[maxn] , n;
struct node{
int mxp , mnp , mxs , mns , sm ;
node(){
mxp = mxs = 0 ;
mnp = mns = 0 ;
sm =0 ;
}
};
node seg[4*maxn] ;
node mrg(node a , node b){
node r ;
r.mxp = max(a.mxp , b.mxp + a.sm) ;
r.mnp = min(a.mnp , b.mnp + a.sm) ;
r.mxs = max(b.mxs , a.mxs + b.sm);
r.mns = min(b.mns , a.mns + b.sm) ;
r.sm = a.sm + b.sm ;
return r ;
}
void upd(int x , int w, int p = 1, int l = 1 , int r = n){
if(l == r){
seg[p].mxp = seg[p].mxs = max(0 , w);
seg[p].mnp = seg[p].mns = min(0 , w) ;
seg[p].sm = w ;
return ;
}
int pl = p<<1,pr=p<<1|1 , mid = (l+r)/2 ;
if(mid>= x){
upd(x,w,pl,l,mid);
}else{
upd(x,w,pr,mid+1,r);
}
seg[p] = mrg(seg[pl] , seg[pr]) ;
}
node z ;
void query(int le ,int ri ,int p = 1, int l = 1, int r= n){
int pl = p<<1,pr=p<<1|1 , mid = (l+r)/2 ;
if(le > ri){
z.mxp = z.mxs = z.mns = z.mnp = 0 ;z.sm =0 ;
return ;
}
if(le <= l && r <= ri){
z = mrg(z , seg[p]) ;
return;
}
if(mid >= ri){
query(le,ri,pl,l,mid);
return ;
}
if(mid < le){
query(le,ri,pr,mid+1,r);
return ;
}
query(le,ri,pl,l,mid) ;query(le,ri,pr,mid+1,r);
}
vector <int> vec[maxn] ;
void bui(int p = 1, int l = 1, int r= n){
int mid = (l+r)/2 , pl=p<<1, pr=p<<1|1;
if(l == r){
seg[p].sm = seg[p].mxp = seg[p].mxs = 1 ;
seg[p].mnp = seg[p].mns = 0 ;
return ;
}
bui(pl,l,mid);
bui(pr,mid+1,r);
seg[p] = mrg(seg[pl] , seg[pr]);
}
node nw ;
int ch(int x){
bui();
rep(i ,1 ,n){
if(sz(vec[i]) < x){
for(int j : vec[i]){
upd(j , -1) ;
}
continue ;
}
rep(j , 0 ,x-1){
upd(vec[i][j] , 0) ;
}
rep(j , 0 ,sz(vec[i])-x){
int l = vec[i][j] , r = vec[i][j+x-1] ;
z=nw;query(1 , l);node a1 = z;
z=nw;query(r , n);node a2 = z ;
z=nw;query(l,r);int sum = z.sm ;
if((sum >= 0 && sum+a1.mns+a2.mnp <= x) || (sum <= 0 && -(sum + a1.mxs + a2.mxp) <= x))return 1 ;
upd(vec[i][j] , -1) ;
if(j!=sz(vec[i])-x){
upd(vec[i][j+x] , 0) ;
}
}
per(j , sz(vec[i])-1 , 0){
upd(vec[i][j] , -1) ;
}
}
return 0 ;
}
int sequence(int N, vector<int> A) {
n = N ;
rep(i , 1,n){
a[i] = A[i-1] ;
vec[a[i]].pb(i) ;
if(a[i] > n)cout << 1/0 ;
}
int mx = 0 ;
rep(i , 1 , n){
mx= max(mx ,sz(vec[i])) ;
}
int l = 1 , r= mx+1 ;
while(r-l > 1){
int mid = (l+r)/2 ;
if(ch(mid) == 1) l = mid ;
else r = mid ;
}
return l;
}
Compilation message
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:122:26: warning: division by zero [-Wdiv-by-zero]
122 | if(a[i] > n)cout << 1/0 ;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
103004 KB |
Output is correct |
2 |
Correct |
20 ms |
103004 KB |
Output is correct |
3 |
Correct |
20 ms |
103184 KB |
Output is correct |
4 |
Correct |
20 ms |
103004 KB |
Output is correct |
5 |
Correct |
19 ms |
102976 KB |
Output is correct |
6 |
Correct |
20 ms |
103252 KB |
Output is correct |
7 |
Correct |
20 ms |
103188 KB |
Output is correct |
8 |
Correct |
19 ms |
103256 KB |
Output is correct |
9 |
Correct |
20 ms |
103180 KB |
Output is correct |
10 |
Correct |
20 ms |
103004 KB |
Output is correct |
11 |
Correct |
20 ms |
103004 KB |
Output is correct |
12 |
Correct |
20 ms |
103004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
103004 KB |
Output is correct |
2 |
Correct |
20 ms |
103004 KB |
Output is correct |
3 |
Correct |
20 ms |
103184 KB |
Output is correct |
4 |
Correct |
20 ms |
103004 KB |
Output is correct |
5 |
Correct |
19 ms |
102976 KB |
Output is correct |
6 |
Correct |
20 ms |
103252 KB |
Output is correct |
7 |
Correct |
20 ms |
103188 KB |
Output is correct |
8 |
Correct |
19 ms |
103256 KB |
Output is correct |
9 |
Correct |
20 ms |
103180 KB |
Output is correct |
10 |
Correct |
20 ms |
103004 KB |
Output is correct |
11 |
Correct |
20 ms |
103004 KB |
Output is correct |
12 |
Correct |
20 ms |
103004 KB |
Output is correct |
13 |
Correct |
21 ms |
103256 KB |
Output is correct |
14 |
Correct |
22 ms |
103260 KB |
Output is correct |
15 |
Correct |
22 ms |
103212 KB |
Output is correct |
16 |
Correct |
22 ms |
103004 KB |
Output is correct |
17 |
Correct |
23 ms |
103188 KB |
Output is correct |
18 |
Correct |
21 ms |
103256 KB |
Output is correct |
19 |
Correct |
22 ms |
103248 KB |
Output is correct |
20 |
Correct |
21 ms |
103456 KB |
Output is correct |
21 |
Correct |
23 ms |
103260 KB |
Output is correct |
22 |
Correct |
22 ms |
103212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
103004 KB |
Output is correct |
2 |
Correct |
101 ms |
121896 KB |
Output is correct |
3 |
Correct |
229 ms |
122196 KB |
Output is correct |
4 |
Correct |
1305 ms |
112248 KB |
Output is correct |
5 |
Correct |
170 ms |
121168 KB |
Output is correct |
6 |
Correct |
117 ms |
121172 KB |
Output is correct |
7 |
Correct |
822 ms |
113232 KB |
Output is correct |
8 |
Correct |
1450 ms |
113172 KB |
Output is correct |
9 |
Correct |
975 ms |
112800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
103004 KB |
Output is correct |
2 |
Correct |
850 ms |
113156 KB |
Output is correct |
3 |
Correct |
1708 ms |
112328 KB |
Output is correct |
4 |
Correct |
1206 ms |
112772 KB |
Output is correct |
5 |
Correct |
1505 ms |
113132 KB |
Output is correct |
6 |
Execution timed out |
2052 ms |
112316 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
249 ms |
127568 KB |
Output is correct |
2 |
Correct |
234 ms |
128084 KB |
Output is correct |
3 |
Correct |
142 ms |
127572 KB |
Output is correct |
4 |
Correct |
136 ms |
127532 KB |
Output is correct |
5 |
Correct |
222 ms |
124120 KB |
Output is correct |
6 |
Correct |
292 ms |
124124 KB |
Output is correct |
7 |
Correct |
271 ms |
122924 KB |
Output is correct |
8 |
Correct |
184 ms |
122436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
103004 KB |
Output is correct |
2 |
Correct |
20 ms |
103004 KB |
Output is correct |
3 |
Correct |
20 ms |
103184 KB |
Output is correct |
4 |
Correct |
20 ms |
103004 KB |
Output is correct |
5 |
Correct |
19 ms |
102976 KB |
Output is correct |
6 |
Correct |
20 ms |
103252 KB |
Output is correct |
7 |
Correct |
20 ms |
103188 KB |
Output is correct |
8 |
Correct |
19 ms |
103256 KB |
Output is correct |
9 |
Correct |
20 ms |
103180 KB |
Output is correct |
10 |
Correct |
20 ms |
103004 KB |
Output is correct |
11 |
Correct |
20 ms |
103004 KB |
Output is correct |
12 |
Correct |
20 ms |
103004 KB |
Output is correct |
13 |
Correct |
21 ms |
103256 KB |
Output is correct |
14 |
Correct |
22 ms |
103260 KB |
Output is correct |
15 |
Correct |
22 ms |
103212 KB |
Output is correct |
16 |
Correct |
22 ms |
103004 KB |
Output is correct |
17 |
Correct |
23 ms |
103188 KB |
Output is correct |
18 |
Correct |
21 ms |
103256 KB |
Output is correct |
19 |
Correct |
22 ms |
103248 KB |
Output is correct |
20 |
Correct |
21 ms |
103456 KB |
Output is correct |
21 |
Correct |
23 ms |
103260 KB |
Output is correct |
22 |
Correct |
22 ms |
103212 KB |
Output is correct |
23 |
Correct |
74 ms |
105876 KB |
Output is correct |
24 |
Correct |
68 ms |
105816 KB |
Output is correct |
25 |
Correct |
70 ms |
105812 KB |
Output is correct |
26 |
Correct |
160 ms |
104780 KB |
Output is correct |
27 |
Correct |
135 ms |
104796 KB |
Output is correct |
28 |
Correct |
186 ms |
104796 KB |
Output is correct |
29 |
Correct |
241 ms |
104392 KB |
Output is correct |
30 |
Correct |
221 ms |
104456 KB |
Output is correct |
31 |
Correct |
193 ms |
104912 KB |
Output is correct |
32 |
Correct |
29 ms |
106588 KB |
Output is correct |
33 |
Correct |
118 ms |
105484 KB |
Output is correct |
34 |
Correct |
187 ms |
105524 KB |
Output is correct |
35 |
Correct |
115 ms |
105644 KB |
Output is correct |
36 |
Correct |
285 ms |
105652 KB |
Output is correct |
37 |
Correct |
288 ms |
105672 KB |
Output is correct |
38 |
Correct |
288 ms |
105712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
103004 KB |
Output is correct |
2 |
Correct |
20 ms |
103004 KB |
Output is correct |
3 |
Correct |
20 ms |
103184 KB |
Output is correct |
4 |
Correct |
20 ms |
103004 KB |
Output is correct |
5 |
Correct |
19 ms |
102976 KB |
Output is correct |
6 |
Correct |
20 ms |
103252 KB |
Output is correct |
7 |
Correct |
20 ms |
103188 KB |
Output is correct |
8 |
Correct |
19 ms |
103256 KB |
Output is correct |
9 |
Correct |
20 ms |
103180 KB |
Output is correct |
10 |
Correct |
20 ms |
103004 KB |
Output is correct |
11 |
Correct |
20 ms |
103004 KB |
Output is correct |
12 |
Correct |
20 ms |
103004 KB |
Output is correct |
13 |
Correct |
21 ms |
103256 KB |
Output is correct |
14 |
Correct |
22 ms |
103260 KB |
Output is correct |
15 |
Correct |
22 ms |
103212 KB |
Output is correct |
16 |
Correct |
22 ms |
103004 KB |
Output is correct |
17 |
Correct |
23 ms |
103188 KB |
Output is correct |
18 |
Correct |
21 ms |
103256 KB |
Output is correct |
19 |
Correct |
22 ms |
103248 KB |
Output is correct |
20 |
Correct |
21 ms |
103456 KB |
Output is correct |
21 |
Correct |
23 ms |
103260 KB |
Output is correct |
22 |
Correct |
22 ms |
103212 KB |
Output is correct |
23 |
Correct |
101 ms |
121896 KB |
Output is correct |
24 |
Correct |
229 ms |
122196 KB |
Output is correct |
25 |
Correct |
1305 ms |
112248 KB |
Output is correct |
26 |
Correct |
170 ms |
121168 KB |
Output is correct |
27 |
Correct |
117 ms |
121172 KB |
Output is correct |
28 |
Correct |
822 ms |
113232 KB |
Output is correct |
29 |
Correct |
1450 ms |
113172 KB |
Output is correct |
30 |
Correct |
975 ms |
112800 KB |
Output is correct |
31 |
Correct |
850 ms |
113156 KB |
Output is correct |
32 |
Correct |
1708 ms |
112328 KB |
Output is correct |
33 |
Correct |
1206 ms |
112772 KB |
Output is correct |
34 |
Correct |
1505 ms |
113132 KB |
Output is correct |
35 |
Execution timed out |
2052 ms |
112316 KB |
Time limit exceeded |
36 |
Halted |
0 ms |
0 KB |
- |