#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct node{
int mn, mx;
node(int mini=0, int maxi=0) : mn(mini), mx(maxi) {}
};
int n;
vector<vector<int>> pos;
vector<int> lazy;
vector<node> tr;
void change(int pos, int add) {
tr[pos].mn+=add;
tr[pos].mx+=add;
lazy[pos]+=add;
}
node pull(node L, node R) {
int MN, MX;
MN=min(L.mn, R.mn);
MX=max(L.mx, R.mx);
return node(MN, MX);
}
void push(int pos) {
change(2*pos+1, lazy[pos]);
change(2*pos+2, lazy[pos]);
lazy[pos]=0;
}
void update(int ll, int rr, int add, int pos=0, int l=0, int r=n-1) {
if(ll>rr) return;
if(ll==l && rr==r) {change(pos, add); return;}
push(pos); int mid=l+r>>1;
update(ll, min(rr, mid), add, 2*pos+1, l, mid);
update(max(mid+1, ll), rr, add, 2*pos+2, mid+1, r);
tr[pos]=pull(tr[2*pos+1], tr[2*pos+2]);
}
node get(int ll, int rr, int pos=0, int l=0, int r=n-1) {
if(ll>rr) return node(INF, -INF);
if(ll==l && rr==r) return tr[pos];
push(pos); int mid=l+r>>1;
return pull(get(ll, min(rr, mid), 2*pos+1, l, mid), get(max(mid+1, ll), rr, 2*pos+2, mid+1, r));
}
node build(int pos=0, int l=0, int r=n-1) {
lazy[pos]=0;
if(l==r) return tr[pos]=node(l+1, r+1);
int mid=l+r>>1;
return tr[pos]=pull(build(2*pos+1, l, mid), build(2*pos+2, mid+1, r));
}
int sequence(int N, vector<int> a) {
n=N;
pos.resize(n+1);
tr.resize(4*n);
lazy.resize(4*n);
for(int i=0; i<n; i++) pos[a[i]].push_back(i);
int ans=0;
tr[0]=build();
for(int val=1; val<=n; val++) {
int idx=0, SZ=pos[val].size();
for(int p : pos[val]) update(p, n-1, -1);
for(int i=0; i<SZ; i++) {
idx=min(SZ, max(i+ans, idx));
assert(i<=idx);
while(idx<SZ) {
int Min=get(pos[val][idx], n-1).mn;
if(pos[val][i]) Min-=max(0, get(0, pos[val][i]-1).mx);
int Max=get(pos[val][idx], n-1).mx;
if(pos[val][i]) Max-=min(0, get(0, pos[val][i]-1).mn);
int len=idx-i+1;
if(Max<(-len) || len<Min) break;
else idx++;
}
assert(idx<=SZ);
ans=max(ans, idx-i);
}
for(int p : pos[val]) update(p, n-1, -1);
}
return ans;
}
Compilation message
sequence.cpp: In function 'void update(int, int, int, int, int, int)':
sequence.cpp:32:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | push(pos); int mid=l+r>>1;
| ~^~
sequence.cpp: In function 'node get(int, int, int, int, int)':
sequence.cpp:40:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | push(pos); int mid=l+r>>1;
| ~^~
sequence.cpp: In function 'node build(int, int, int)':
sequence.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid=l+r>>1;
| ~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
311 ms |
49488 KB |
Output is correct |
3 |
Correct |
292 ms |
49584 KB |
Output is correct |
4 |
Correct |
347 ms |
41676 KB |
Output is correct |
5 |
Correct |
306 ms |
48720 KB |
Output is correct |
6 |
Correct |
281 ms |
48500 KB |
Output is correct |
7 |
Correct |
279 ms |
42048 KB |
Output is correct |
8 |
Correct |
318 ms |
42060 KB |
Output is correct |
9 |
Correct |
370 ms |
42416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
462 ms |
42496 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
400 ms |
55228 KB |
Output is correct |
2 |
Correct |
374 ms |
55120 KB |
Output is correct |
3 |
Correct |
392 ms |
54660 KB |
Output is correct |
4 |
Correct |
429 ms |
54716 KB |
Output is correct |
5 |
Correct |
398 ms |
51316 KB |
Output is correct |
6 |
Correct |
396 ms |
51316 KB |
Output is correct |
7 |
Correct |
386 ms |
50112 KB |
Output is correct |
8 |
Correct |
324 ms |
49556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |