// yuki 989 N×Mマス計算(K以上) // 2020.2.16 bal4u #include #include #include typedef long long ll; #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } void out(ll n) { // 非負整数の表示(出力) int i; char b[30]; if (!n) pc('0'); else { i = 0; while (n) b[i++] = n % 10 + '0', n /= 10; while (i--) pc(b[i]); } pc('\n'); } void Usort(int *a, int n) { int i, k; #define B 8 #define BMSK 255 // (1<<8)-1 int t1[1 << B], t2[1 << B]; int *tmp = malloc(n * sizeof(int)); for (k = 0; k < 8; ++k) { // for 64ビット memset(t1, 0, sizeof(t1)), memset(t2, 0, sizeof(t2)); for (i = 0; i < n; ++i) t1[(a[i] >> k*B) & BMSK]++; for (i = 0; i < BMSK; ++i) t1[i+1] += t1[i]; i = n; while (i--) tmp[--t1[(a[i] >> k*B) & BMSK]] = a[i]; k++; for (i = 0; i < n; ++i) t2[(tmp[i] >> k*B) & BMSK]++; for (i = 0; i < BMSK; ++i) t2[i+1] += t2[i]; i = n; while (i--) a[--t2[(tmp[i] >> k*B) & BMSK]] = tmp[i]; } free(tmp); // for (i = 0; i < n; ++i) printf("[%d] %lld\n", i, a[i]); #undef B } int B[100005]; int M; // バイナリサーチ。見つからなければ、一つ大きい要素を返す。つまり、 >= x int bs(int x) { int m, l = 0, r = M; while (l < r) { m = (l+r) >> 1; if (B[m] < x) l = m + 1; else r = m; } return l; } int main() { int i, j, N, K, op, A; ll ans; N = in(), M = in(), K = in(); op = (gc() == '+'), gc(); for (i = 0; i < M; ++i) B[i] = in(); Usort(B, M); ans = 0; for (j = 0; j < N; ++j) { A = in(); if (op) ans += M - bs(K-A); else if (K % A) ans += M - bs(K/A+1); else ans += M - bs(K/A); } out(ans); return 0; }