ABC294 E

原题题面

题意

我们有一个行数为 \(2\) 列数为 \(L\) 的网格。让 \((i,j)\) 表示从上面 \((i\in\lbrace1,2\rbrace)\) 起第 \(i\) 行和从左边 \((1\leq j\leq L)\) 起第 \(j\) 列的正方形。\((i,j)\) 上写有一个整数 \(x _ {i,j}\)。

求有多少个整数\(j\)使得\(x _ {1,j}=x _ {2,j}\).

这里，\(x _ {i,j}\) 的描述是将 $(x _ {1,1},x _ {1,2},\ldots,x _ {1,L}) $ 和 $ (x _ {2,1},x _ {2,2},\ldots,x _ {2,L})$ 分别压缩成长度为 \(N _ 1\)和\(N _ 2\)的序列：\(((v _ {1,1},l _ {1,1}),\ldots,(v _ {1,N _ 1},l _ {1,N _ 1}))\) 和 \(((v _ {2,1},l _ {2,1}),\ldots,(v _ {2,N _ 2},l _ {2,N _ 2}))\)。

这里，序列 \(A\) 的运行长度压缩是由 \(A\) 的元素 \(v _ i\) 和正整数 \(l _ i\) 组成的成对序列 \((v _ i,l _ i)\)，如下所示。

1. 在每对不同的相邻元素之间拆分 \(A\)。
2. 2. 对于分割后的每个序列 \(B _ 1,B _ 2,\ldots,B _ k\) ，设 \(v _ i\) 是 \(B _ i\) 的元素，\(l _ i\) 是 \(B _ i\) 的长度。

思路

可以用两个指针分别指向第 \(1、2\) 行当前这一块的最后一个元素，再用两个变量分别记录第 \(1、2\) 行指针搜走过的地方即可

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int a1[N],b1[N],a2[N],b2[N];
signed main(){
    int l,n,m;cin >> l >> n >> m ;
	for(int i=1;i<=n;i++)cin>>a1[i]>>b1[i];
	for(int i=1;i<=m;i++)cin>>a2[i]>>b2[i];
	int i=1,j=1,l1=b1[1],l2=b2[1],ans=0;
	while(i<=n && j<=m){
		if(a1[i]==a2[j]){
			int x=l1-b1[i],y=l2-b2[j];
			ans+=max(0ll,min(l1,l2)-max(x,y));
		}
		if(l1>=l2) l2+=b2[++j];
		else l1+=b1[++i];
	}
	cout<<ans;
	return 0;
}