シュミレーションを実装する問題.
上下のマスが一致してるか判定しないといけない箇所は, 高々\(N_{0} + N_{1}\) 個のみ.
実装
上下それぞれについて,run length の情報を deque に入れておく. 取り出して,min(上下の長さ) だけ,今調べている長さを進める.
進めた結果,run length の length が \(0\) でなかった場合,deque の先頭に戻す.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll l; cin >> l;
vll n(2); cinv(n);
rep(s,2){
rep(i,n[s]){
ll v, len ; cin >> v >> len;
a[s].push_back({len, v});
}
}
ll ans = 0;
while(a[0].size()){
vll l(2), v(2);
rep(s,2) {
tie(l[s], v[s]) = a[s].front();
a[s].pop_front();
}
ll lmi = min(l[0], l[1]);
if(v[0] == v[1]){
ans += lmi;
}
rep(s,2) {
l[s] -= lmi;
if(l[s] != 0){
a[s].push_front({l[s], v[s]});
}
}
}
assert(a[1].size() == 0);
cout << ans << endl;
return 0;
}