Submission #1202878

#TimeUsernameProblemLanguageResultExecution timeMemory
1202878irmuunSequence (APIO23_sequence)C++17
40 / 100
596 ms80644 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ff first #define ss second #define all(s) s.begin(),s.end() #define rall(s) s.rbegin(),s.rend() const int N=5e5+5; int n,a[N],lo,hi; vector<int>pos[N]; struct segtree{ int mx[4*N],mn[4*N],lazy[4*N]; void add(int v,int x){ mx[v]+=x; mn[v]+=x; lazy[v]+=x; } void push(int v){ if(lazy[v]==0) return; add(v<<1,lazy[v]); add(v<<1|1,lazy[v]); lazy[v]=0; } void merge(int v){ mx[v]=max(mx[v<<1],mx[v<<1|1]); mn[v]=min(mn[v<<1],mn[v<<1|1]); } void update(int v,int l,int r,int L,int R,int val){ if(R<L||r<L||R<l) return; if(L<=l&&r<=R){ add(v,val); return; } push(v); int m=(l+r)>>1; update(v<<1,l,m,L,R,val); update(v<<1|1,m+1,r,L,R,val); merge(v); } void query(int v,int l,int r,int L,int R){ if(R<L||r<L||R<l) return; if(L<=l&&r<=R){ lo=min(lo,mn[v]); hi=max(hi,mx[v]); return; } push(v); int m=(l+r)>>1; query(v<<1,l,m,L,R); query(v<<1|1,m+1,r,L,R); } }; int sequence(int N,vector<int>A){ n=N; for(int i=1;i<=n;i++){ a[i]=A[i-1]; pos[a[i]].pb(i); } segtree more,less; for(int i=1;i<=n;i++){ more.update(1,1,n,i,n,-1); } for(int i=1;i<=n;i++){ less.update(1,1,n,i,n,-1); } int ans=0; for(int x=1;x<=n;x++){ for(int p:pos[x]){ more.update(1,1,n,p,n,+2); } int j=0; for(int i=0;i<pos[x].size();i++){ while(j<i){ int v1,v2; hi=-1e9,more.query(1,1,n,pos[x][i],n); v1=hi; lo=0,more.query(1,1,n,1,pos[x][j]-1); v1-=lo; lo=1e9,less.query(1,1,n,pos[x][i],n); v2=lo; hi=0,less.query(1,1,n,1,pos[x][j]-1); v2-=hi; if(v1*v2>0) j++; else break; } ans=max(ans,i-j+1); } for(int p:pos[x]){ less.update(1,1,n,p,n,+2); } } return ans; }
#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...