【题解】cometoj 两排房子⭐⭐⭐ 【双指针】

cometoj 两排房子

Input

Output

输出一行一个整数表示答案。

Examples

样例输入 1

3 3 1 3 3 4 5 6 2 4 4 5 5 7 样例输出 1

5

题解:

考虑一下较为朴素的双指针做法, 定义两个指针L, R分别表示当前遍历的第二排房子的最左/最右下标, 每次判断条件更新指针即可. 注意初始化时R为0

#include<bits/stdc++.h> using namespace std; #define ms(x, n) memset(x,n,sizeof(x)); typedef long long LL; const int INF = 1 << 30; const int MAXN = 2e5+10; int n, m, xl[MAXN], xr[MAXN], yl[MAXN], yr[MAXN]; int main() { ios::sync_with_stdio(false); cin >> n >> m; for(int i = 1; i <= n; ++i) cin >> xl[i] >> xr[i]; for(int i = 1; i <= m; ++i) cin >> yl[i] >> yr[i]; int L = 1, R = 0, ans = 0; //注意初始化 for(int i = 1; i <= n; ++i){ while(yr[L] < xl[i] && L <= m) ++L; while(yl[R+1] <= xr[i] && R+1 <= m) ++R; if(L <= R) ans += (R-L+1); } cout << ans << endl; return 0; }