算法
(排序) $O((n_1+n_2)\log (n_1+n_2))$
可以对 (开始时刻, (行号, 值))
作为事件进行升序排序
然后对于相邻两个事件,如果是不同行号且存在值相同的部分,就把对应的时间差加到答案里即可~~
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
ll L;
vector<int> N(2);
cin >> L >> N[0] >> N[1];
vector<pair<ll, P>> events;
rep(i, 2) {
ll t = 0;
rep(j, N[i]) {
int v; ll l;
cin >> v >> l;
events.emplace_back(t, P(i, v));
t += l;
}
}
sort(events.begin(), events.end());
events.emplace_back(L, P(0, 0));
vector<int> val(2);
ll pt = 0;
ll ans = 0;
for (auto [t, p] : events) {
if (val[0] == val[1]) ans += t-pt;
auto [i, v] = p;
val[i] = v;
pt = t;
}
cout << ans << '\n';
return 0;
}