Gecko [ tsuru-no-tsurugi.tokyo ]

Linux tsuru-no-tsurugi 5.15.0-186-generic #196-Ubuntu SMP Sat Jun 20 16:09:34 UTC 2026 x86_64
Apache/2.4.52 (Ubuntu)
Server IP : 192.168.0.18 & Your IP : 216.73.217.105
Domains : Cant Read [ /etc/named.conf ]
User : www-data

Name	Size	Permission	Date
a.cpp	1.41 KB	-rwxr-x---	2024-08-28 22:35
cerror.txt	0 B	-rwxr-x---	2024-08-28 22:35
error.txt	0 B	-rwxr-x---	2024-08-28 22:35
submit_info.txt	199 B	-rwxr-x---	2024-08-28 22:35

Rename

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

struct UnionFind {
  std::vector<int> e;
  UnionFind(int n) : e(n, -1) {}
  int find(int u) { return e[u] < 0 ? u : e[u] = find(e[u]); }
  void join(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return;
    if (e[u] > e[v]) std::swap(u, v);
    e[u] += e[v]; e[v] = u;
    return;
  }
};

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin.exceptions(std::cin.failbit);

int N, M, X, P;
  std::cin >> N >> M >> X >> P;

std::vector<int> B(N), T(M+1);
  for (int i = 0; i < N; ++i)
    std::cin >> B[i];
  for (int i = 1; i <= M; ++i)
    std::cin >> T[i];

UnionFind uf(M+1);

for (int u, v, i = 0; i < X; ++i) {
    std::cin >> u >> v;
    uf.join(u, v);
  }

std::sort(B.begin(), B.end());
  std::vector<int> ord(M);
  std::iota(ord.begin(), ord.end(), 1);
  std::sort(ord.begin(), ord.end(), [&](int a, int b) { return T[a] < T[b]; });

std::vector<int> cnt(M+1, 0);
  for (int i = 0, j = 0; j < M; ++j) {
    while (i < N and B[i] - P <= T[ord[j]]) ++i;
    cnt[ord[j]] += i;
  }
  for (int i = 0, j = 0; j < M; ++j) {
    while (i < N and B[i] + P < T[ord[j]]) ++i;
    cnt[ord[j]] -= i;
  }

std::vector<int> need(M+1, 0);
  for (int i = 1; i <= M; ++i)
    if (cnt[i] > 0) need[uf.find(i)] = 1;

std::cout << std::accumulate(need.begin(), need.end(), 0) << '\n';

return 0;
}