#include<bits/stdc++.h>
using namespace std;
int a[200005];
int b[200005];
vector<int>id[200005];
vector<int>v;
vector<pair<int,int>>op;
struct segtree{
int mx[400005];
void upd(int st,int en,int i,int pos,int val){
if(st>pos||en<pos)return;
if(st==en)return void(mx[i]=val);
int m=(st+en)/2;
upd(st,m,i*2,pos,val);
upd(m+1,en,i*2+1,pos,val);
mx[i]=max(mx[i*2],mx[i*2+1]);
}
int fans(int st,int en,int i,int l,int r){
if(st>r||en<l)return 0;
if(st>=l&&en<=r)return mx[i];
int m=(st+en)/2;
return max(fans(st,m,i*2,l,r),fans(m+1,en,i*2+1,l,r));
}
void build(int st,int en,int i){
if(st==en)return void(mx[i]=0);
int m=(st+en)/2;
build(st,m,i*2);
build(m+1,en,i*2+1);
mx[i]=0;
}
}tr;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;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++){
tr.upd(1,n,1,i,a[i]);
}
for(int i=1;i<=n;i++){
id[a[i]].push_back(i);
}
for(int i=1;i<=n;i++){
for(auto x:id[b[i]]){
int mx=tr.fans(1,n,1,min(i,x),max(i,x));
if(mx>b[i])continue;
op.push_back({i,-x});
}
}
tr.build(1,n,1);
for(auto [x,y]:op){
int val=tr.fans(1,n,1,1,-y)+1;
tr.upd(1,n,1,-y,val);
}
cout<<tr.fans(1,n,1,1,n);
}
# | 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... |