Submission #512609

#	Time	Username	Problem	Language	Result	Execution time	Memory
512609		new_acc	Exam (eJOI20_exam)	C++14	100 / 100	148 ms	12432 KiB

exam

#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(ll a = 0; a < (b); a++)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const int SS=1<<19;
int a[N],b[N],seg[SS*2+10];
pair<int,int> naj[N];
void Insert(int a,int ind){
	for(ind+=SS;ind>0;ind>>=1) seg[ind]=max(seg[ind],a);
}
int Query(int pocz,int kon){
	int res=0;
	for(pocz+=SS-1,kon+=SS+1;(pocz>>1)!=(kon>>1);pocz>>=1,kon>>=1){
		if(!(pocz&1)) res=max(res,seg[pocz+1]);
		if(kon&1) res=max(res,seg[kon-1]);
	}
	return res;
}
unordered_map<int,int>m;
void solve(){
	int n;
	cin>>n;
	rep(i,n) cin>>a[i];
	rep(i,n) cin>>b[i];
	rep(i,n) Insert(a[i],i);
	rep(i,n){
		m[a[i]]=i;
		if(m.count(b[i])>0 and Query(m[b[i]],i)==b[i]) naj[i].fi=m[b[i]];
		else naj[i].fi=-1;
	}
	m.clear();
	for(int i=n-1;i>=0;i--){
		m[a[i]]=i;
		if(m.count(b[i])>0 and Query(i,m[b[i]])==b[i]) naj[i].se=m[b[i]];
		else naj[i].se=-1;
	}
	rep(i,SS*2+10) seg[i]=0;
	rep(i,n){
		int g=0,g2=0;
		if(naj[i].fi!=-1) g=Query(0,naj[i].fi);
		if(naj[i].se!=-1) g2=Query(0,naj[i].se);
		if(naj[i].fi!=-1) Insert(g+1,naj[i].fi);
		if(naj[i].se!=-1) Insert(g2+1,naj[i].se);

	}
	cout<<Query(0,n)<<"\n";
}
int main(){
	solve();
}

• Subtask 1: 14 / 14
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22