제출 #512440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
512440		new_acc	Exam (eJOI20_exam)	C++14	0 / 100	5 ms	976 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 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();
}

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