题解

圆圈表示特殊点 X表示必经点 S表示起点
左上角图表示找到经过X至少要经过最左最右必经点lr 使用数组排序二分查找
题目一共分四种情况(图片参考至某大佬) 代码将12和34合并为两种情况
最开始vec数组只保存题目所给特殊点 求出b线路最左最右必经点bl,br 之后加入起点s重新排序求出a最左最右必经点al,ar(情况1)
如果b站点没有点直接输出a区间长度(ar-al)*2+s点到ar或al距离(如果al ar包含s则为0)
如果b站点有必经点则al=min(al, bl) ar=max(ar, br) a区间不可能比b小
输出s到a距离+ab区间长+b区间小于a区间的部分(如图4上升后的←边)+2次跨越代价
数据好像水了补一个样例
10 3 1 2 4
6 0
7 0
9 1
8
输出16

AC代码

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAXR = 1e5 + 10;
int x[MAXR], y[MAXR];

int main()
{
#ifdef LOCAL
	freopen("C:/input.txt", "r", stdin) ;
#endif
	int n, r, m, k, s, p;
	cin >> n >> r >> m >> k >> s; //n区间长 r经过点 m特殊点 k跨越代价 s起点位置
	for (int i = 1; i <= r; i++)
		scanf("%d%d", &x[i], &y[i]);
	vector<int> vec; //特殊点
	vec.push_back(1), vec.push_back(n);
	for (int i = 1; i <= m; i++)
		scanf("%d", &p), vec.push_back(p);
	sort(vec.begin(), vec.end());
	int al = n, ar = 1, bl = n, br = 1, f = 0; //ab最左右特殊点 f站点b有点
	for (int i = 1; i <= r; i++) //找到b站点每个必经点需要的最左最右特殊点
		if (y[i])
		{
			bl = min(bl, *(upper_bound(vec.begin(), vec.end(), x[i]) - 1)); //第一个小于等于x[i]的
			br = max(br, *(lower_bound(vec.begin(), vec.end(), x[i]))); //第一个大于等于
			f = 1;
		}
	vec.push_back(s), sort(vec.begin(), vec.end()); //s可以作为a的转向点
	for (int i = 1; i <= r; i++) //找a站点
		if (!y[i])
		{
			al = min(al, *(upper_bound(vec.begin(), vec.end(), x[i]) - 1));
			ar = max(ar, *(lower_bound(vec.begin(), vec.end(), x[i])));
		}
	al = min(al, bl), ar = max(ar, br); //a的范围至少要大于b
	if (!f)
		cout << (max(0, al - s) + max(0, s - ar) + ar - al) * 2 << endl; //s到a+a区间长*2
	else
		cout << (max(0, al - s) + max(0, s - ar)) * 2 + //s到a
		ar - al + br - bl + //ab区间长
		bl - al + ar - br + //a超出b
		k * 2 << endl; //跨越

	return 0;
}