이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "sequence.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=5e5+9;
struct IT_max{
vector<int>st,lazy;
void resz(int n){
st.clear(),lazy.clear();
st.resize(4*n+9);
lazy.resize(4*n+9);
}
void push(int id){
if (lazy[id]){
st[id<<1]+=lazy[id];
st[id<<1|1]+=lazy[id];
lazy[id<<1]+=lazy[id];
lazy[id<<1|1]+=lazy[id];
lazy[id]=0;
}
}
void update(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st[id]+=val;
lazy[id]+=val;
return;
}
push(id);
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
st[id]=max(st[id<<1],st[id<<1|1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return -maxn;
if (u<=l&&r<=v)return st[id];
push(id);
int mid=(l+r)>>1;
return max(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
}
};
struct IT_min{
vector<int>st,lazy;
void resz(int n){
st.clear(),lazy.clear();
st.resize(4*n+9);
lazy.resize(4*n+9);
}
void push(int id){
if (lazy[id]){
st[id<<1]+=lazy[id];
st[id<<1|1]+=lazy[id];
lazy[id<<1]+=lazy[id];
lazy[id<<1|1]+=lazy[id];
lazy[id]=0;
}
}
void update(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st[id]+=val;
lazy[id]+=val;
return;
}
push(id);
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
st[id]=min(st[id<<1],st[id<<1|1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return maxn;
if (u<=l&&r<=v)return st[id];
push(id);
int mid=(l+r)>>1;
return min(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
}
};
struct IT{
vector<int>st;
void resz(int n){
st.resize(4*n+9);
}
void update(int id,int l,int r,int u,int val){
if(l>u||r<u)return;
if (l==r){
st[id]=val;
return;
}
int mid=(l+r)>>1;
update(id<<1,l,mid,u,val);
update(id<<1|1,mid+1,r,u,val);
st[id]=max(st[id<<1],st[id<<1|1]);
}
int walk(int id,int l,int r,int u,int val){
if (st[id]<val)return -1;
if (l>u)return -1;
if (l==r)return l;
int mid=(l+r)>>1;
int ans=walk(id<<1,l,mid,u,val);
if (ans==-1)return walk(id<<1|1,mid+1,r,u,val);
return ans;
}
};
int n;
int a[maxn];
vector<int>value[maxn];
int mx_l[maxn],mn_l[maxn],mn_r[maxn],mx_r[maxn];
int pf[maxn];
void pre(){
IT_max st1;
IT_min st2;
st1.resz(n),st2.resz(n);
auto up=[&](int id,int val){
st1.update(1,1,n,id,n,val);
st2.update(1,1,n,id,n,val);
};
for1(i,1,n)up(i,-1);
for1(i,1,n){
for (auto v:value[i]){
up(v,2);
}
for (auto v:value[i]){
pf[v]=st1.get(1,1,n,v,v);
}
for1(j,0,sz(value[i])-1){
int v=value[i][j];
if (j==sz(value[i])-1)mx_r[v]=st1.get(1,1,n,v,n)-pf[v],mn_r[v]=st2.get(1,1,n,v,n)-pf[v];
else mx_r[v]=st1.get(1,1,n,v,value[i][j+1]-1)-pf[v],mn_r[v]=st2.get(1,1,n,v,value[i][j+1]-1)-pf[v];
}
}
st1.resz(n),st2.resz(n);
auto rup=[&](int id,int val){
st1.update(1,1,n,1,id,val);
st2.update(1,1,n,1,id,val);
};
for1(i,1,n)rup(i,-1);
for1(i,1,n){
for (auto v:value[i])rup(v,2);
for1(j,0,sz(value[i])-1){
int v=value[i][j];
int suffix=st1.get(1,1,n,v,v);
if (j==0){
mx_l[v]=st1.get(1,1,n,1,v)-suffix,mn_l[v]=st2.get(1,1,n,1,v)-suffix;
}
else {
mx_l[v]=st1.get(1,1,n,value[i][j-1]+1,v)-suffix,mn_l[v]=st2.get(1,1,n,value[i][j-1]+1,v)-suffix;
}
}
}
}
int get(int l,int r,int x){
int ans=0;
for1(i,l,r)ans+=(a[i]==x);
return ans;
}
int cal(int l,int r){
vector<int>xd;
for1(i,l,r)xd.pb(a[i]);
sort(all(xd));
int k=r-l+1;
return max(get(l,r,xd[(k-1)/2]),get(l,r,xd[k/2]));
}
int gg(int l,int r,int x){
int ans=0;
for1(i,l,r){
if (a[i]<=x)ans++;
else ans--;
}
return ans;
}
struct type{
int id,val;
bool fl;
bool operator < (const type &p){
if (val==p.val)return fl<p.fl;
return val<p.val;
}
};
int sequence(int N, std::vector<int> A) {
n=N;
for1(i,1,n)a[i]=A[i-1];
for1(i,1,n)value[a[i]].pb(i);
int ans=0;
pre();
for1(i,1,n){
vector<type>t;
for1(j,0,sz(value[i])-1){
int v=value[i][j];
t.pb({j+1,pf[v]-mx_l[v],0});
t.pb({j+1,pf[v]+1+mx_r[v],1});
}
sort(all(t));
IT st;
st.resz(sz(value[i]));
int m=sz(value[i]);
for1(j,1,m)st.update(1,1,m,j,-n*10);
for (auto v:t){
int id=value[i][v.id-1];
if (v.fl==0){
st.update(1,1,m,v.id,pf[id]-mn_l[id]-2*v.id);
}
else {
int pos=st.walk(1,1,m,v.id,pf[id]+1+mn_r[id]-2*v.id-2);
if (pos!=-1){
ans=max(ans,v.id-pos+1);
}
}
}
}
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... |