ABC D求调 玄关
查看原帖
ABC D求调 玄关
902351
Little_x_starTYJ楼主2024/6/30 21:51
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
	char c;
	int x;
} a[200010];
vector<int> v, v1;
int ans;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, t;
	cin >> n >> t;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].c;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x;
		if (a[i].c == '1') {
			v1.push_back(a[i].x);
		} else {
			v.push_back(a[i].x);
		}
	}
	sort(v.begin(), v.end());
	sort(v1.begin(), v1.end());
	for (int i = 0; i < v.size(); i++) {
		int l = 0, r = v1.size() - 1;
		int k = 0;
		while (l < r) {
			int mid = l + r + 1 >> 1;
			if (v1[mid] > v[i]) {
				r = mid - 1;
			} else
				l = mid;
		}
		k = l;
		r = k, l = 0;
		while (l < r) {
			int mid = l + r >> 1;
			if (abs(v1[mid] - v[i]) > t * 2) {
				l = mid + 1;
			} else
				r = mid;
		}
		if (abs(v1[l] - v[i]) <= 2 * t)
			ans += l + 1;
		r = v1.size() - 1, l = k + 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (abs(v1[mid] - v[i]) > t * 2) {
				l = mid + 1;
			} else
				r = mid;
		}
		if (abs(v1[l] - v[i]) <= t * 2)
			ans += l - k;
	}
	cout << ans;
	return 0;
}

2024/6/30 21:51
加载中...