安全であるための条件は「\(i\) 番目の車より右にいるどの車とも座標が \(B_i\times K\) 以上離れている」ですが、全ての車と位置の比較をする必要はなく、自身のすぐ右にいる車との距離だけを確認すれば十分です。

つまり、もし \(A_1 \leq A_2 \leq \dots \leq A_N\) を満たすなら \(A_i+B_i\times K \leq A_{i+1}\) であるかどうかだけを確認すれば十分です。

よって、車を座標でソートして隣あう車の位置を確認することで、\(O(N\log N)\) でこの問題を解くことができます。

座標でソートすることにより並びが変わるので、車の番号を保持する必要などがあることに注意してください。

実装例(C++)

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

int main(){
	int n,k;
	cin >> n >> k;
	vector<array<int,3>>abi;  // (a, b, index) のリスト
	for(int i=0;i<n;i++){
		int a,b;
		cin >> a >> b;
		abi.push_back({a,b,i+1});
	}
	sort(abi.begin(),abi.end());

	vector<int>ans;
	// 隣り合う車の位置を確認
	for(int i=0;i<n-1;i++){
		if(!(abi[i][0] + (long long)abi[i][1]*k <= abi[i+1][0])){
			ans.push_back(abi[i][2]);
		}
	}

	sort(ans.begin(),ans.end());
	cout << ans.size() << endl;
	for(int i=0;i<ans.size();i++){
		if(i)cout << ' ';
		cout << ans[i];
	}
	cout << endl;
}

実装例(python)

N,K=map(int,input().split())
abi=[]  # (a, b, index) のリスト
for _ in range(N):
  a,b=map(int,input().split())
  abi.append((a,b,i))

abi.sort()

ans=[]
# 隣り合う車の位置を確認
for i in range(N-1):
  if not abi[i][0] + abi[i][1]*K <= abi[i+1][0]:
    ans.append(abi[i][2])

ans.sort()
print(len(ans))
print(*ans)