好题一道。

我们可以开一个栈，然后倒序枚举一下，遇到一个倒着走的粒子，就压入栈。否则，这个正着走的粒子就与栈顶组合。显然，这样是对的。

然后用双指针或二分技术就好了。

#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
int n,m;
const int N=5e5+10;
int x[N],type[N];
int t[N],tim[N];
stack<int> st;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&type[i]);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		scanf("%d",&t[i]);
	}
	for(int i=n;i;i--){
		if(type[i]==-1){
			st.push(i);
		}else{
			if(st.empty()){
				continue;
			}
			int d=st.top();
			tim[i]=tim[d]=(x[d]-x[i]+1)/2;
			st.pop();
		}
	}
	for(int i=1;i<=n;i++){
		if(!tim[i]){
			tim[i]=2e9;
		}
	}
	sort(tim+1,tim+n+1);
	int j=0;
	for(int i=1;i<=m;i++){
		while(j<n&&tim[j+1]<=t[i]){
			j++;
		}
		printf("%d\n",n-j);
	}
}