提出詳細

提出id	提出時刻	ユーザー名	問題	言語	判定状況	判定	実行時間
114868	2023-10-24 09:24:20	Fysty	J	cpp	11/11	AC	7

#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;

ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll tmp=1;
    for(ll cur=a;b;b>>=1,cur=cur*cur%m) if(b&1) tmp=tmp*cur%m;
    return tmp;
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)

const int N=100005;
int p[N],sz[N],cnt[N];

int fp(int x){return x==p[x]?x:p[x]=fp(p[x]);}
void unite(int u,int v)
{
    u=fp(u),v=fp(v);
    if(u==v) return;
    if(sz[u]<sz[v]) swap(u,v);
    sz[u]+=sz[v];
    p[v]=u;
}

int x[N];

void solve()
{
    int n,m,k,len;
    cin>>n>>m>>k>>len;
    vector<int> b(n);
    rep(i,n) cin>>b[i];
    rep1(i,m)
    {
        cin>>x[i];
    }
    rep1(i,m)
    {
        p[i]=i;
        sz[i]=1;
        cnt[i]=0;
    }
    rep(i,k)
    {
        int u,v;
        cin>>u>>v;
        unite(u,v);
    }
    sort(b.begin(),b.end());
    rep1(i,m)
    {
        int pos=lower_bound(b.begin(),b.end(),x[i])-b.begin();
        bool has=0;
        if(pos<n&&b[pos]-len<=x[i]) has=1;
        if(pos-1>=0&&b[pos-1]+len>=x[i]) has=1;
        if(!has) continue;
        cnt[fp(i)]++;
    }
    ll ans=0;
    rep1(i,m) if(fp(i)==i)
    {
        if(cnt[i]>0) ans++;
    }
    cout<<ans<<"\n";
}

signed main()
{
    MottoHayaku
    int t;
    //cin>>t;
    t=1;
    while(t--)
    {
        solve();
    }
}

case1.txt AC 2
case2.txt AC 2
case3.txt AC 3
case4.txt AC 6
case5.txt AC 7
case6.txt AC 7
case9.txt AC 7
case10.txt AC 7
case11.txt AC 7
case13.txt AC 7
sample1.txt AC 7
7 AC7 AC