C++ 解法, 执行用时: 66ms, 内存消耗: 1968K, 提交时间: 2021-11-19 20:12:44

#include <bits/stdc++.h>
using namespace std;

typedef long long s64;
const int N = 1e5 + 5, D = 998244353, L = 63;
s64 pow_mod(s64 x, int y = D - 2) {
	s64 ans = 1;
	while (y) {
		if (y & 1) ans = ans * x % D;
		x = x * x % D;
		y >>= 1;
	}
	return ans;
}
pair<int, s64> p[N];
char K[N];
s64 a[L];
int t[L];
void ins(s64 na, int nt) {
	for (int i = L - 1; i >= 0; --i)
		if ((na >> i) & 1) {
			if (!a[i]) {
				a[i] = na;
				t[i] = nt;
				break;
			}
			if (nt > t[i]) {
				swap(nt, t[i]);
				swap(a[i], na);
			}
			na ^= a[i];
		}
}
int n, len_K;
bool check(int l, int r, s64 s) {
	if (r - l + 1 < len_K) return 0;
	int m = r - l + 1, c = 0;
	for (int i = L - 1; i >= 0; --i)
		if (t[i] >= l) {
			--m;
			++c;
		}
	int p = len_K - m;
	if (p < 0) return 1;
	s64 ans = 0;
	int head = p - c;
	for (int i = L - 1; i >= 0; --i) {
		if (t[i] >= l) {
			++head;
			if (head >= 1 && K[head] == '1')
				ans = max(ans, a[i] ^ ans);
			else
				ans = min(ans, a[i] ^ ans);
		}
	}
	return ans <= s;
}

int main() {
#ifdef kcz
	freopen("1.in", "r", stdin); //freopen("1.out","w",stdout);
#endif
	cin >> n;
	for (int i = 1; i <= n; ++i) scanf("%lld%d", &p[i].second, &p[i].first);
	sort(p + 1, p + n + 1);
	scanf("%s", K + 1);
	len_K = strlen(K + 1);
	s64 s;
	cin >> s;
	int l = 1;
	int ans = 2e9;
	for (int r = 1; r <= n; ++r) {
		ins(p[r].second, r);
		while (check(l, r, s)) {
			ans = min(ans, p[r].first - p[l].first);
			++l;
		}
	}
	cout << ans << endl;
}