Submission #1213657

#TimeUsernameProblemLanguageResultExecution timeMemory
1213657WarinchaiExam (eJOI20_exam)C++20
36 / 100
1099 ms137136 KiB
#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 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...