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

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Node {
	int x, v;
} a[200005];
int n, m, t[200005], ans, sum[200005], num[200005], cnt;
stack<int> st;
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i].x >> a[i].v;
		if (a[i].v == -1) {
			if (st.empty()) {
				ans ++;
			} else {
				int tmp = st.top();
				st.pop();
				num[++cnt] = (a[i].x - a[tmp].x) / 2;
				if ((a[i].x - a[tmp].x) % 2 == 1) {
					num[cnt] ++;
				}
				sum[cnt] = num[cnt];
			}
		} else {
			st.push(i);
		}
	}
	while (!st.empty()) {
		ans ++;
		st.pop();
	}
	sort(sum + 1, sum + 1 + cnt);
	cin >> m;
	for (int i = 1; i <= m; i ++) {
		cin >> t[i];
		if (t[i] >= sum[cnt]) {
			cout << ans << "\n";
			continue;
		}
		int j = upper_bound(sum + 1, sum + 1 + cnt, t[i]) - sum;
		cout << ans + (cnt - j + 1) * 2 << "\n";
	}
	return 0;
}