二分40pts求调
查看原帖
二分40pts求调
365777
halehu楼主2023/8/20 10:22
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5,M = 1005;
int n,m,c1,c2,s[N],t[N],vis[N],sum,k = 1,a[N],vis2[N],b[N],tot1,tot2;
vector <int> v[N];
int main(){
	scanf("%d%d%d%d",&n,&m,&c1,&c2);
	for(int i=1;i<=n;i++) scanf("%d",&s[i]),vis[s[i]] = 1;
	for(int i=1;i<=m;i++){
		scanf("%d",&t[i]),sum += vis[t[i]];
		if(vis[t[i]]) vis2[t[i]] = 1,b[++ tot2] = t[i];
	}
	for(int i=1;i<=n;i++) if(vis2[s[i]]) a[++ tot1] = s[i];
	for(int i=1;i<=tot1;i++) v[a[i]].push_back(i);
	int pos = 1;
	for(int i=1;i<=tot2;i++){
		int l = 1,r = v[b[i]].size();
		if(!r || v[b[i]][r - 1] < pos){
			pos = v[b[i]][0] + 1,++ k;
			continue;
		}
		while(l < r){
			int mid = (l + r) >> 1;
			if(v[b[i]][mid - 1] >= pos) r = mid;
			else l = mid + 1;
		}
		pos = v[b[i]][l - 1];
	}
    printf("%d %d\n",c1 * sum,c2 * k);
    return 0;
}
2023/8/20 10:22
加载中...