이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)
const int N = 5e5 + 5;
const int inf = 2e9;
int n;
vector <int> pos[N];
struct ST{
ii st[4*N], zero = {inf, -inf};
int lazy[4*N];
ii merge(ii a, ii b){
return {min(a.first, b.first), max(a.second, b.second)};
}
void down(int id){
lazy[id<<1] += lazy[id], lazy[id<<1|1] += lazy[id];
st[id<<1].first += lazy[id], st[id<<1].second += lazy[id];
st[id<<1|1].first += lazy[id], st[id<<1|1].second += lazy[id];
lazy[id] = 0;
}
void Upd(int id, int l, int r, int x, int y, int val){
if(r < x or y < l) return;
if(x <= l and r <= y){
lazy[id] += val;
st[id].first += val, st[id].second += val;
return;
}
down(id);
int m = (l+r)>>1;
Upd(id<<1, l, m, x, y, val), Upd(id<<1|1, m+1, r, x, y, val);
st[id] = merge(st[id<<1], st[id<<1|1]);
}
ii query(int id, int l, int r, int x, int y){
if(r < x or y < l) return zero;
if(x <= l and r <= y) return st[id];
down(id);
int m = (l+r)>>1;
return merge(query(id<<1, l, m, x, y), query(id<<1|1, m+1, r, x, y));
}
int val(int pos){
if(pos == 0) return 0;
return query(1, 1, n, pos, pos).first;
}
void upd(int node, int val){
Upd(1, 1, n, node, n, val);
}
}st[2];
int sign(int x){
if(x == 0) return x;
return x / abs(x);
}
bool check(int x, int y){
int VL1 = st[0].val(x-1), VR1 = st[0].val(y), sum1 = VR1 - VL1;
int VL2 = st[1].val(x-1), VR2 = st[1].val(y), sum2 = VR2 - VL2;
int maL = 0, maR = 0;
int miL = 0, miR = 0;
if(x != 1){
ii C1 = st[0].query(1, 1, n, 1, x-1);
ii C2 = st[1].query(1, 1, n, 1, x-1);
maL = max(0, max(VL1, VL1 - C1.first));
miL = min(0, min(VL2, VL2 - C2.second));
}
if(y != n){
ii C1 = st[0].query(1, 1, n, y+1, n);
ii C2 = st[1].query(1, 1, n, y+1, n);
maR = max(0, C1.second - VR1);
miR = min(0, C2.first - VR2);
}
return sign(sum1 + maL + maR) * sign (sum2 + miL + miR) <= 0;
}
int sequence(int Ni, vector<int> A) {
n = Ni;
f(i,0,n){
pos[A[i]].push_back(i+1);
}
f(i,1,n+1){
st[0].upd(i, 1);
st[1].upd(i, 1);
}
int ans = 1;
f(i,1,n+1){
int len = pos[i].size();
for(int x: pos[i]){
st[1].upd(x, -2);
}
int r = -1;
f(j,0,len){
r = max(r, j);
while(r < len and check(pos[i][j], pos[i][r])) r++;
r--;
ans = max(ans, r - j + 1);
}
for(int x: pos[i]){
st[0].upd(x, -2);
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |