제출 #908370

#제출 시각아이디문제언어결과실행 시간메모리
908370winter0101서열 (APIO23_sequence)C++17
82 / 100
2062 ms81212 KiB
#include<bits/stdc++.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_lazy{ int mx[maxn<<2],mn[maxn<<2],lazy[maxn<<2]; void resz(int n){ for1(i,1,4*n)mx[i]=mn[i]=lazy[i]=0; } void push(int id){ if (lazy[id]){ mx[id<<1]+=lazy[id]; mx[id<<1|1]+=lazy[id]; mn[id<<1]+=lazy[id]; mn[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){ mx[id]+=val; mn[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); mx[id]=max(mx[id<<1],mx[id<<1|1]); mn[id]=min(mn[id<<1],mn[id<<1|1]); } int get_max(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 mx[id]; int mid=(l+r)>>1; push(id); return max(get_max(id<<1,l,mid,u,v),get_max(id<<1|1,mid+1,r,u,v)); } int get_min(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 mn[id]; int mid=(l+r)>>1; push(id); return min(get_min(id<<1,l,mid,u,v),get_min(id<<1|1,mid+1,r,u,v)); } }; struct IT{ int st[maxn*4]; 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; if (mid>=u)update(id<<1,l,mid,u,val); else 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 val){ if (st[id]<val)return -1; if (l==r)return l; int mid=(l+r)>>1; int ans=walk(id<<1,l,mid,val); if (ans==-1)return walk(id<<1|1,mid+1,r,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_lazy st; st.resz(n); auto up=[&](int id,int val){ st.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]=st.get_max(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]=st.get_max(1,1,n,v,n)-pf[v],mn_r[v]=st.get_min(1,1,n,v,n)-pf[v]; else mx_r[v]=st.get_max(1,1,n,v,value[i][j+1]-1)-pf[v],mn_r[v]=st.get_min(1,1,n,v,value[i][j+1]-1)-pf[v]; } } st.resz(n); auto rup=[&](int id,int val){ st.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=st.get_max(1,1,n,v,v); if (j==0){ mx_l[v]=st.get_max(1,1,n,1,v)-suffix,mn_l[v]=st.get_min(1,1,n,1,v)-suffix; } else { mx_l[v]=st.get_max(1,1,n,value[i][j-1]+1,v)-suffix,mn_l[v]=st.get_min(1,1,n,value[i][j-1]+1,v)-suffix; } } } } 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(); IT st; 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)); int m=sz(value[i]); for1(j,1,4*m)st.st[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,pf[id]+1+mn_r[id]-2*v.id-2); if (pos!=-1&&pos<=v.id){ ans=max(ans,v.id-pos+1); } } } } return ans; } /*signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); freopen("temp.INP","r",stdin); //freopen(".OUT","w",stdout); int N; assert(1 == scanf("%d", &N)); std::vector<int> A(N); for (int i = 0; i < N; ++i) { assert(1 == scanf("%d", &A[i])); } int result = sequence(N, A); printf("%d\n", result); return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...