AcWing 3288. 稀疏向量
原题链接
简单
作者:
Gadv
,
2023-12-06 16:52:19
,
所有人可见
,
阅读 41
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 500010;
int n, m;
PII a[N], b[N];
int main()
{
scanf("%*d%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &a[i].x, &a[i].y);
for (int i = 0; i < m; i ++ ) scanf("%d%d", &b[i].x, &b[i].y);
LL res = 0;
//双指针 感觉这样更好理解一些
for (int i = 0, j = 0; i < n && j < m; )
{
if(a[i].x!=b[j].x){
if(a[i].x<b[j].x) i++;
else j++;
}else{
res += (LL)a[i].y * b[j].y;
i++;
j++;
}
}
printf("%lld\n", res);
return 0;
}