Submission #512440

#TimeUsernameProblemLanguageResultExecution timeMemory
512440new_accExam (eJOI20_exam)C++14
0 / 100
5 ms976 KiB
#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 L=19;
int a[N],b[N],jump[N][L+1],naj[N];
unordered_map<int,int>m;
int przedzial(int a,int b){
	if(a>b) swap(a,b);
	return max(jump[a][naj[b-a+1]],jump[b-(1<<naj[b-a+1])+1][naj[b-a+1]]);
}
void solve(){
	int n;
	cin>>n;
	rep(i,n) {cin>>a[i];m[a[i]]=i;}
	rep(i,n) cin>>b[i];
	for(int i=n-1;i>=0;i--){
		jump[i][0]=a[i];
		for(int j=1;i+(1<<j)-1<n;j++) jump[i][j]=max(jump[i][j-1],jump[i+(1<<(j-1))][j-1]);
	}
	int xd=0;
	for(int i=1;i<=n;i++){
		naj[i]=xd;
		if(i/2==(1<<xd)) xd++;
	}
	int res=0;
	rep(i,n){
		if(m.count(b[i])>0){
			int xd=m[b[i]];
			if(przedzial(i,xd)==b[i]) res++;
		}
	}
	cout<<res<<"\n";
}
int main(){
	solve();
}
#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...