#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)5e5 + 10;
vector<int> pos[N];
int A[N];
int n;
struct Node{
int low;
int high;
int lazy;
};
Node T[N * 4 + 512];
void build(int node, int cl, int cr){
T[node].low = T[node].high = T[node].lazy = 0;
if(cl == cr){
T[node].low = T[node].high = cl;
T[node].lazy = 0;
return;
}
int mid = (cl + cr) / 2;
build(node * 2, cl, mid);
build(node * 2 + 1, mid + 1, cr);
T[node].low=min(T[node*2].low, T[node*2+1].low);
T[node].high=max(T[node*2].high,T[node*2+1].high);
}
void push(int node, int cl, int cr){
T[node].high += T[node].lazy;
T[node].low += T[node].lazy;
if(cl != cr){
T[node * 2].lazy += T[node].lazy;
T[node * 2 + 1].lazy += T[node].lazy;
}
T[node].lazy = 0;
}
void update_segm(int node, int cl, int cr, int tl, int tr, int d){
push(node, cl, cr);
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
T[node].lazy = d;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
update_segm(node * 2, cl, mid, tl, tr, d);
update_segm(node * 2 + 1, mid + 1, cr, tl, tr, d);
T[node].low=min(T[node*2].low, T[node*2+1].low);
T[node].high=max(T[node*2].high,T[node*2+1].high);
}
pii get_val(int node, int cl, int cr, int tl, int tr){
push(node, cl, cr);
if(cr < tl || cl > tr) return mp((int)1e9, -(int)1e9);
if(cl >= tl && cr <= tr){
return mp(T[node].low, T[node].high);
}
int mid = (cl + cr) / 2;
pii L = get_val(node * 2, cl, mid, tl, tr);
pii R = get_val(node * 2 + 1, mid + 1, cr, tl, tr);
return mp(min(L.fi, R.fi), max(L.se, R.se));
}
mt19937 gene(chrono::steady_clock::now().time_since_epoch().count());
int numo(int m){
return ((int)gene() % m + m) % m;
}
bool check(int cnt){
build(1, 0, n);
int bal;
int l, r;
pii suf;
pii lE;
pii rE;
pii lef;
int take;
for(int cand = 1; cand <= n; cand ++ ){
for(auto x : pos[cand]){
update_segm(1, 0, n, x, n, -1);
}
for(int j = 0 ; j + cnt - 1 < pos[cand].size(); j ++ ){
l = pos[cand][j];
r = pos[cand][j + cnt - 1];
lE = get_val(1, 0, n, l - 1, l - 1);
rE = get_val(1, 0, n, r, r);
bal = rE.fi - lE.fi;
suf = get_val(1, 0, n, r, n);
lef = get_val(1, 0, n, 0, l - 1);
suf.fi -= rE.fi;
suf.se -= rE.se;
lef = mp(-lef.se, -lef.fi);
lef.fi += lE.fi;
lef.se += lE.fi;
bal += lef.fi + suf.fi;
take = max(0, (-cnt) - bal);
if(bal <= cnt && take <= (lef.se - lef.fi) + (suf.se - suf.fi)){
return true;
}
}
for(auto x : pos[cand]){
update_segm(1, 0, n, x, n, -1);
}
}
return false;
}
int sequence(int _n, vector<int> a) {
n = _n;
for(int i = 0 ; i < n; i ++ ){
A[i + 1] = a[i];
pos[A[i + 1]].push_back(i + 1);
}
int l = 1, r = n + 1;
int mid;
while(l + 1 < r){
mid = l + (r - l) / 2;
if(check(mid)){
l = mid;
}
else{
r = mid;
}
}
for(int iter = l + 25; iter >= l ; iter -- ){
if(iter <= n && check(iter)) return iter;
}
return l;
}
Compilation message
sequence.cpp: In function 'bool check(int)':
sequence.cpp:97:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int j = 0 ; j + cnt - 1 < pos[cand].size(); j ++ ){
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
7 ms |
12044 KB |
Output is correct |
3 |
Correct |
7 ms |
12004 KB |
Output is correct |
4 |
Correct |
8 ms |
11988 KB |
Output is correct |
5 |
Correct |
8 ms |
12068 KB |
Output is correct |
6 |
Correct |
7 ms |
11972 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
8 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
10 ms |
11988 KB |
Output is correct |
11 |
Correct |
7 ms |
11988 KB |
Output is correct |
12 |
Correct |
8 ms |
11988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
7 ms |
12044 KB |
Output is correct |
3 |
Correct |
7 ms |
12004 KB |
Output is correct |
4 |
Correct |
8 ms |
11988 KB |
Output is correct |
5 |
Correct |
8 ms |
12068 KB |
Output is correct |
6 |
Correct |
7 ms |
11972 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
8 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
10 ms |
11988 KB |
Output is correct |
11 |
Correct |
7 ms |
11988 KB |
Output is correct |
12 |
Correct |
8 ms |
11988 KB |
Output is correct |
13 |
Correct |
38 ms |
12172 KB |
Output is correct |
14 |
Correct |
39 ms |
12116 KB |
Output is correct |
15 |
Correct |
38 ms |
12116 KB |
Output is correct |
16 |
Correct |
47 ms |
12132 KB |
Output is correct |
17 |
Correct |
45 ms |
12084 KB |
Output is correct |
18 |
Correct |
35 ms |
12188 KB |
Output is correct |
19 |
Correct |
37 ms |
12116 KB |
Output is correct |
20 |
Correct |
35 ms |
12116 KB |
Output is correct |
21 |
Correct |
40 ms |
12116 KB |
Output is correct |
22 |
Correct |
40 ms |
12136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Execution timed out |
2080 ms |
40120 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12044 KB |
Output is correct |
2 |
Execution timed out |
2064 ms |
32348 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2079 ms |
45772 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
7 ms |
12044 KB |
Output is correct |
3 |
Correct |
7 ms |
12004 KB |
Output is correct |
4 |
Correct |
8 ms |
11988 KB |
Output is correct |
5 |
Correct |
8 ms |
12068 KB |
Output is correct |
6 |
Correct |
7 ms |
11972 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
8 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
10 ms |
11988 KB |
Output is correct |
11 |
Correct |
7 ms |
11988 KB |
Output is correct |
12 |
Correct |
8 ms |
11988 KB |
Output is correct |
13 |
Correct |
38 ms |
12172 KB |
Output is correct |
14 |
Correct |
39 ms |
12116 KB |
Output is correct |
15 |
Correct |
38 ms |
12116 KB |
Output is correct |
16 |
Correct |
47 ms |
12132 KB |
Output is correct |
17 |
Correct |
45 ms |
12084 KB |
Output is correct |
18 |
Correct |
35 ms |
12188 KB |
Output is correct |
19 |
Correct |
37 ms |
12116 KB |
Output is correct |
20 |
Correct |
35 ms |
12116 KB |
Output is correct |
21 |
Correct |
40 ms |
12116 KB |
Output is correct |
22 |
Correct |
40 ms |
12136 KB |
Output is correct |
23 |
Execution timed out |
2070 ms |
17620 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
7 ms |
12044 KB |
Output is correct |
3 |
Correct |
7 ms |
12004 KB |
Output is correct |
4 |
Correct |
8 ms |
11988 KB |
Output is correct |
5 |
Correct |
8 ms |
12068 KB |
Output is correct |
6 |
Correct |
7 ms |
11972 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
8 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
10 ms |
11988 KB |
Output is correct |
11 |
Correct |
7 ms |
11988 KB |
Output is correct |
12 |
Correct |
8 ms |
11988 KB |
Output is correct |
13 |
Correct |
38 ms |
12172 KB |
Output is correct |
14 |
Correct |
39 ms |
12116 KB |
Output is correct |
15 |
Correct |
38 ms |
12116 KB |
Output is correct |
16 |
Correct |
47 ms |
12132 KB |
Output is correct |
17 |
Correct |
45 ms |
12084 KB |
Output is correct |
18 |
Correct |
35 ms |
12188 KB |
Output is correct |
19 |
Correct |
37 ms |
12116 KB |
Output is correct |
20 |
Correct |
35 ms |
12116 KB |
Output is correct |
21 |
Correct |
40 ms |
12116 KB |
Output is correct |
22 |
Correct |
40 ms |
12136 KB |
Output is correct |
23 |
Execution timed out |
2080 ms |
40120 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |