結果

問題 No.1170 Never Want to Walk
コンテスト
ユーザー hishimochi
提出日時 2020-08-14 23:20:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,807 bytes
コンパイル時間 1,647 ms
コンパイル使用メモリ 173,876 KB
実行使用メモリ 13,640 KB
最終ジャッジ日時 2024-10-10 16:46:37
合計ジャッジ時間 7,512 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

//定数
const long long MOD1=1000000007;
const long long MOD2=998244353;
const long double PI=3.1415926535897932;
const long long MAXLL=9223372036854775807;
const long long INF=2305843009213693951;
const long long dx[]={0,1,0,-1,1,-1,1,-1};
const long long dy[]={1,0,-1,0,1,1,-1,-1};

//省略
#define ll long long
#define ull unsigned long long
#define ld long double
#define uld unsigned long double
#define pll pair<long long,long long>
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define vvvl vector<vector<vector<long long>>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vs vector<string>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vp vector<pair<long long,long long>>
#define umap unordered_map
#define uset unordered_set
#define Lqueue priority_queue<long long>
#define Squeue priority_queue<long long,vector<long long>,greater<long long>>
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

//マクロ
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rbf(a,x) for(auto& a:x)
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s);i<(long long)(n);i++)
#define bitrep(i,s,n) for(long long i=(s);i<(1LL<<(n));i++)
#define bitcheck(bit,i) (bit)&(1LL<<(i))
#define Maxe(x) *max_element((x).begin(),(x).end())
#define Mine(x) *min_element((x).begin(),(x).end())
#define Size(x) ((long long)(x).size())
#define Lin(s) getline(cin,(s))

//Yes,No
void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}
void YES(bool a){cout<<(a?"YES":"NO")<<endl;}

//MAX,MIN
template<class T,class U> auto max(T a,U b){return a>b?a:b;}
template<class T,class U> auto min(T a,U b){return a<b?a:b;}

//最大公約数,最小公倍数
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a,long long b){return a/gcd(a,b)*b;}

//切り上げ除算
long long cutup(long long a,long long b){return (a+b-1)/b;}

//累乗
template<typename t>
constexpr t my_pow(t a,long long b){
    if(b==0)return 1;
    if(a==0)return 0;
    t x=1;
    while(b>0){
        if(b&1LL)x*=a;
        a*=a;
        b>>=1LL;
    }
    return x;
}
#define pow my_pow

//chmin,chmax
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}

//組み合わせ O(r)
template<typename t>
constexpr t nCr(t n,long long r){
    if(r==0)return 1;
    if(n==0)return 0;
    if(n<r)return 0;
    t x=1;
    for(long long i=1;i<=r;i++){
        x*=n-i+1;
        x/=i;
    }
    return x;
}

struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};

//main関数
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,a,b;
    cin>>n>>a>>b;
    UnionFind UF(n);
    vl x(n+2);
    x[0]=-INF;
    x[n+1]=INF;
    rep2(i,1,n+1)cin>>x[i];
    int ind1=lower_bound(all(x),x[0]+a)-x.begin();
    int ind2=upper_bound(all(x),x[0]+b)-x.begin();
    ind2--;
    rep2(i,1,n+1){
        while(x[ind1]<x[i]+a)ind1++;
        while(x[ind2]<=x[i]+b)ind2++;
        ind2--;
        if(ind2<ind1)continue;
        rep2(j,ind1,ind2+1)UF.merge(i-1,j-1);
    }
    rep(i,n)cout<<UF.size(i)<<endl;
}
0