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 ;
}