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

水星湖 · 2025-01-05 21:52:25 · 题解

我们把 e^+ 看作左括号，e^- 看作右括号，这形成了一个括号序列。显然第 i 个和第 j(i<j) 个粒子会相撞当且仅当两个括号在括号序列中匹配，且可以认为它们会在 \left[\frac{x_j-x_i+1}{2}\right] 时刻相撞。算出每个电子相撞时间后咋做就都行了。

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

namespace z {

#define int long long
const int N = 5e5 + 5;
#define x first
#define v second
pair<int, int> a[N];
stack<int> s;
int t[N];
void main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) 
        cin >> a[i].x >> a[i].v;
    memset(t, 0x3f, sizeof(t));
    for(int i = 1; i <= n; i++) {
        if(a[i].v == 1) s.push(i);
        else {
            if(s.empty()) continue;
            int j = s.top(); s.pop();
            t[i] = t[j] = (a[i].x - a[j].x + 1) / 2;
        }
    }
    sort(t + 1, t + n + 1);
    int j = 0, m, ans = n; cin >> m;
    while(m--) {
        int tt;
        cin >> tt;
        while(j < n && t[j + 1] <= tt) j++, ans--;
        cout << ans << '\n';
    }
}

#undef int

}

int main()
{
    z::main();
    return 0;
}