ABC360D wa*1求调
  • 板块学术版
  • 楼主OIer_Tan
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/6/30 21:43
  • 上次更新2024/7/1 09:45:42
查看原帖
ABC360D wa*1求调
700210
OIer_Tan楼主2024/6/30 21:43

RT,用的是双指针,但是看不出来哪里假了。

有 hack 也行。

#include <bits/stdc++.h>

#ifndef CRT
#define endl '\n'
#endif

using namespace std ;

typedef long long ll ;
typedef unsigned long long ull ;
typedef long double ld ;

const ll N = 2e5 + 5 ;

ll n , a [N] , t , ans ;

string s ;

ll fd [N] , bd [N] , cnt1 , cnt2 ;

int main ()
{
	ios::sync_with_stdio ( 0 ) ;
	cin.tie ( 0 ) ;
	cout.tie ( 0 ) ;
	cin >> n >> t ;
	cin >>s ;
	s.insert ( 0 , " " ) ;
//	cout << s << endl ;
	for ( ll i = 1 ; i <= n ; i ++ )
	{
		cin >> a [i] ;
		if ( s [i] == '1' )
		{
			fd [++ cnt1] = a [i] ;
		}
		else
		{
			bd [++ cnt2] = a [i] ;
		}
	}
	sort ( fd + 1 , fd + cnt1 + 1 ) ;
	sort ( bd + 1 , bd + cnt2 + 1 ) ;
	ll i = 1 , j = 1 , bdlast = 0 ;
	for ( ; i <= cnt1 ; i ++ )
	{
		bdlast = lower_bound ( bd + 1 , bd + cnt2 + 1 , fd [i] ) - bd ;
		while ( bd [j] - fd [i] <= t * 2 && j <= cnt2 )
		{
			j ++ ;
		}
		j -- ;
		//cout << i << " " << bdlast << " " << j << endl ;
		ans += j - bdlast + 1 ;
	}
	cout << ans << endl ;
	return 0 ;
}
2024/6/30 21:43
加载中...