Submission #1213749

#TimeUsernameProblemLanguageResultExecution timeMemory
1213749WarinchaiExam (eJOI20_exam)C++20
65 / 100
117 ms105668 KiB
#include<bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; int a[200005]; int b[200005]; vector<int>id[200005]; vector<int>v; vector<pair<int,int>>op; int n; struct fenwick{ int info[100005]; void upd(int id,int val){ for(int i=id;i<=n;i+=i&-i)info[i]=max(info[i],val); } int fans(int id){ int ans=0; for(int i=id;i>0;i-=i&-i)ans=max(ans,info[i]); return ans; } }fw; int qr[5005][5005]; int dp[5005]; int mx[20][100005]; int lg[100005]; int fmx(int l,int r){ int x=lg[r-l+1]; //cerr<<"qr:"<<l<<' '<<r<<" "<<max(mx[x][l],mx[x][r-(1<<x)])<<"\n"; return max(mx[x][l],mx[x][r-(1<<x)+1]); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=1;i<=n;i++)cin>>a[i],v.push_back(a[i]); for(int i=1;i<=n;i++)cin>>b[i],v.push_back(b[i]); sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i=1;i<=n;i++){ int x=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1; a[i]=x; x=lower_bound(v.begin(),v.end(),b[i])-v.begin()+1; b[i]=x; } for(int i=1;i<=n;i++){ id[a[i]].push_back(i); } for(int i=1;i<=n;i++)mx[0][i]=a[i]; for(int i=1;i<20;i++)for(int j=1;j<=n;j++){ mx[i][j]=max(mx[i-1][j],mx[i-1][min(n,j+(1<<(i-1)))]); } lg[1]=0; for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1; for(int i=1;i<=n;i++){ for(auto x:id[b[i]]){ int mx=fmx(min(i,x),max(i,x)); if(mx>b[i])continue; qr[i][x]=1; } } //sort(op.begin(),op.end()); for(int i=1;i<=n;i++){ int pre=0; for(int j=1;j<=n;j++){ pre=max(pre,dp[j]); if(qr[i][j]==1){ dp[j]=pre+1; } } } int ans=0; for(int i=1;i<=n;i++)ans=max(ans,dp[i]); cout<<ans; 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...