Day \(\text{叁拾肆}\)。
DS 写不动了，标题也取不动了www。
类似 Day 1 CF1270H Number of Components，每个连通块中选出一个代表的点。令一个连通块内所有点按照 \(v_{i,j}=\{a_i+b_j,i,j\}\) 排序，对最小的 \(v_{i,j}\) 计数。于是相当于求多少个格子不能走到另一个（非严格）三位偏序它的位置。
令 \(p_i=\max\limits_{j<i,a_j\le a_i}j\)，\(q_i=\min\limits_{j<i,a_j<a_i}j\)，如果极值不存在可以特判，那么 \(v_{i,j}\) 被计数当且仅当它不能走到第 \(p_i\) 行或第 \(q_i\) 行，因为显然有 \(a_{p_i}+b_j<a_i+b_j\)。
大眼观察，发现 \((i,j)\) 能走到第 \(p_i\) 行当且仅当能走到 \((p_i,j)\)：首先充分性是显然的，然后考虑证明必要性：
不妨设 \(p_i<i-1\)。如果能从 \((i,j)\) 走到第 \(p_i\) 行，最优秀的贪心方案是先从 \((i,j)\) 走到一个点 \((i,j')\)，满足 \((i,j')\) 是 \((i,j)\) 在第 \(i\) 行能走到的 \(b_j\) 最小的点（显然不会先移动第一维，因为 \(\forall k\in [p_i+1,i),a_k>a_i\)），然后从 \((i,j')\) 一举走到 \((p_i,j')\)，然后不难发现由于 \(a_{p_i}\le a_i\)，所以 \((p_i,j')\) 是一定能走到 \((p_i,j)\) 的。
又由于我们现在对 \(v_{i,j}\) 计数，所以 \(j\) 一定是 \((i,j)\) 在第 \(i\) 行能走到的最小的 \(j\)，也就是 \(j'=j\)。所以我们只需要判断是否能直接从 \((i,j)\) 走到 \((p_i,j)\)，即 \(\max\limits_{k\in [p_i,i]}a_k+b_j\le x\)。对列同理，于是用单调栈求出 \(p_i,q_i\)，最后变成若干个限制的问题，化简后二维数点即可。
复杂度 \(O(n\log w)\)。
// Problem: E. Gregor and the Two Painters
// Contest: Codeforces - Codeforces Round 736 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1548/E
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;
const int N = 2e5 + 200;
const int M = 25;
int n, m, k, tp, a[N], b[N], st[N], tr[N], mx[N];
int f[N][M][2], ma[N], mb[N];
vector<int> ia, ib;
int qmx(int l, int r, int op) {
if (l > r) return k + 1;
int len = __lg(r - l + 1);
return max(f[l][len][op], f[r - (1 << len) + 1][len][op]);
}
#define lb(x) (x & -x)
void upd(int x, int y) { if (x < 0) return; for (int i = x; i <= k; i += lb(i)) tr[i] += y; }
int qry(int x) { if (x < 0) return 0; int res = 0; for (int i = x; i; i -= lb(i)) res += tr[i]; return res; }
void solve() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
cin >> a[i], a[i] = min(a[i], k), f[i][0][0] = a[i];
for (int i = 1; i <= m; i++)
cin >> b[i], b[i] = min(b[i], k), f[i][0][1] = b[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j][0] = max(f[i][j - 1][0], f[i + (1 << j - 1)][j - 1][0]);
for (int j = 1; (1 << j) <= m; j++)
for (int i = 1; i + (1 << j) - 1 <= m; i++)
f[i][j][1] = max(f[i][j - 1][1], f[i + (1 << j - 1)][j - 1][1]);
for (int i = 1; i <= n; i++) ma[i] = k + 1;
for (int i = 1; i <= m; i++) mb[i] = k + 1;
mx[0] = k + 1;
for (int i = 1; i <= n; i++) {
while (tp && a[st[tp]] > a[i])
tp--, mx[tp] = max(mx[tp], mx[tp + 1]);
ma[i] = min(ma[i], max(mx[tp], a[i])), st[++tp] = i, mx[tp] = a[i];
}
tp = 0;
for (int i = n; i; i--) {
while (tp && a[st[tp]] >= a[i])
tp--, mx[tp] = max(mx[tp], mx[tp + 1]);
ma[i] = min(ma[i], max(mx[tp], a[i])), st[++tp] = i, mx[tp] = a[i];
}
tp = 0;
for (int i = 1; i <= m; i++) {
while (tp && b[st[tp]] > b[i])
tp--, mx[tp] = max(mx[tp], mx[tp + 1]);
mb[i] = min(mb[i], max(mx[tp], b[i])), st[++tp] = i, mx[tp] = b[i];
}
tp = 0;
for (int i = m; i; i--) {
while (tp && b[st[tp]] >= b[i])
tp--, mx[tp] = max(mx[tp], mx[tp + 1]);
mb[i] = min(mb[i], max(mx[tp], b[i])), st[++tp] = i, mx[tp] = b[i];
}
for (int i = 1; i <= n; i++) ia.pb(i);
for (int i = 1; i <= m; i++) ib.pb(i);
sort(ia.begin(), ia.end(), [](int &x, int &y) {
return k - a[x] > k - a[y];
});
sort(ib.begin(), ib.end(), [](int &x, int &y) {
return mb[x] > mb[y];
});
ll res = 0;
auto j = ib.begin();
for (auto i : ia) {
while (j != ib.end() && mb[*j] > k - a[i])
upd(b[*j], 1), j = next(j);
res += qry(k - a[i]) - qry(k - ma[i]);
}
cout << res << '\n';
}
bool Med;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
#ifdef FILE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}