题解：P11511 [ROIR 2017 Day 2] 大型直线对撞机

好题一道。

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

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

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