Submission #875918

#TimeUsernameProblemLanguageResultExecution timeMemory
875918maxFedorchukExam (eJOI20_exam)C++14
100 / 100
364 ms211232 KiB
#include <bits/stdc++.h> using namespace std; const long long MXN=1e5+10; const long long MX=5050; const long long INF=1e18; const long long lg=20; long long sc[MXN],nd[MXN]; long long spars[lg][MXN]; long long dp[MX][MX]; long long mas[MXN]; long long n; void cntspr() { for(long long i=1;i<=n;i++) { spars[0][i]=sc[i]; } for(long long i=1;i<lg;i++) { long long zd=(1LL<<i); long long pzd=zd/2; for(long long j=1;j<=(n-zd+1);j++) { spars[i][j]=max(spars[i-1][j],spars[i-1][j+pzd]); } } return; } long long zap(long long l,long long r) { long long sl=log2(r-l+1); long long zd=(1LL<<sl); return max(spars[sl][l],spars[sl][r-zd+1]); } void fun1() { for(long long i=1;i<=n;i++) { for(long long j=1;j<=n;j++) { if(sc[i]==nd[j] && zap(min(i,j),max(i,j))==nd[j]) { dp[i][j]=dp[i][j-1]+1; } else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } cout<<dp[n][n]<<"\n"; return; } void fun2() { map < long long , long long > mp; for(long long i=1;i<=n;i++) { mp[sc[i]]=i; } vector < long long > psl; for(long long i=1;i<=n;i++) { if(mp.find(nd[i])!=mp.end()) { if(zap(min(mp[nd[i]],i),max(mp[nd[i]],i))==nd[i]) { psl.push_back(mp[nd[i]]); } } } mas[0]=0; for(long long i=1;i<=n+2;i++) { mas[i]=INF; } long long res=0; for(auto u:psl) { long long l=0,r=n+2; while((l+1)<r) { long long mid=(l+r)/2; if(mas[mid]<=u) { l=mid; } else { r=mid; } } mas[r]=u; res=max(res,r); } cout<<res<<"\n"; return; } void fun3() { for(long long i=1;i<=n;i++) { if(sc[i]==nd[i]) { if(sc[i-1]!=nd[i-1]) { for(long long j=i-1;(j>=1 && sc[j]<nd[j]);j--) { sc[j]=nd[j]; } } if(sc[i+1]!=nd[i+1]) { for(long long j=i+1;(j<=n && sc[j]<nd[j]);j++) { sc[j]=nd[j]; } } } } long long res=0; for(long long i=1;i<=n;i++) { res+=(sc[i]==nd[i]); } cout<<res<<"\n"; return; } int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin>>n; for(long long i=1;i<=n;i++) { cin>>sc[i]; } for(long long i=1;i<=n;i++) { cin>>nd[i]; } cntspr(); if(n<=5000) { fun1(); return 0; } for(int i=1;i<=n;i++) { if(nd[i]!=nd[1]) { fun2(); return 0; } } fun3(); 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...