自认为马蜂良好
  • 板块学术版
  • 楼主cqbzzlr
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/6/30 21:55
  • 上次更新2024/7/1 10:10:02
查看原帖
自认为马蜂良好
1238483
cqbzzlr楼主2024/6/30 21:55
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

#define IOS ios::sync_with_stdio(0);
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define SORT(x,y) sort(x+1,x+y+1)
#define UNQIUE(x,y) unqiue(x+1,x+y+1)
#define UPB(x,y,z) upper_bound(x+1,x+y+1,z)-x
#define LWB(x,y,z) lower_bound(x+1,x+y+1,z)-x
#define IT iterator

typedef long long ll;
const int N=2e5+5;
const int INF=0x3f3f3f3f;
const int eps=1e-6;

inline int max(int x,int y)
{
	if(x>y) return x;
	else return y;
}
inline int min(int x,int y)
{
	if(x<y) return x;
	else return y;
}
inline void swap(int &x,int &y)
{
	int t=x;
	x=y;
	y=t;
}
inline int pow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y%2) ans*=x;
		x*=x;
		y=y>>1;   
	}
	return ans;
}
int n,t;
string s;
int x[N];
int a[N],b[N];
int m1,m2;
int low1(int f)
{
	int l = 1,r = m1;
	while(l < r)
	{
//		printf("%d %d\n",l,r);
		int mid = (l + r + 1) >> 1;
		if(a[mid] - f <= t * 2) l = mid;
		else r = mid - 1;
	}
	int l1 = 0,r1 = m1;
	while(l1 < r1)
	{
//		printf("%d %d\n",l,r);
		int mid = (l1 + r1 + 1) >> 1;
		if(a[mid] < f) l1 = mid;
		else r1 = mid - 1;
	}	
	return l - l1;	
}
int low2(int f)
{
	int l = 1,r = m2;
	while(l < r)
	{
//		printf("%d %d\n",l,r);
		int mid = (l + r + 1) >> 1;
		if(f - b[mid] <= t * 2) l = mid;
		else r = mid - 1;
	}
	int l1 = 0,r1 = m2;
	while(l1 < r1)
	{
//		printf("%d %d\n",l,r);
		int mid = (l1 + r1 + 1) >> 1;
		if(b[mid] > f) l1 = mid;
		else r1 = mid - 1;
	}
	return l - l1;
}
inline void solve()
{
	cin >> n >> t >> s;
	rep(i,0,n - 1)
	{
		cin >> x[i];
		if(s[i] == '0')
		{
			m1++;
			a[m1] = x[i];
		}
		else
		{
			m2++;
			b[m2] = x[i];
		}
	}
	ll ans = 0;
	sort(a + 1,a + m1 + 1);
	sort(b + 1,b + m2 + 1);
//	puts("debug");
	rep(i,0,n - 1)
	{
//		printf("debug\n");
		if(s[i] == '0')
		{
//			printf("low2:%d ",low2(x[i]));
			ans += low2(x[i]);
		}
		else
		{
//		printf("low1:%d ",low1(x[i]));
			ans += low1(x[i]);
		}
	}
	cout << ans / 2;
}

signed main()
{
	IOS;
	int T=1;
	//cin>>T;
	rep(fain,1,T)
	{
		solve();
	}
}

样例二死活过不了求解,宣3关

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